Задача №112677. Если б только знать пароль…
Пользоваться машинкой перемещения в пространстве не так просто, как может показаться. Недостаточно просто нажать на кнопку, чтобы оказаться на другой планете: для этого предварительно нужно ввести пароль. Это придумано для того, чтобы землянин, случайно нашедший такую машинку, не отправился куда-нибудь на задворки Вселенной.
Пароль для машинки перемещения состоит из цифр 1, 2,3, ..., 9 и имеет длину \(N\) (1 ≤ \(N\) ≤ 500). При этом пароль не должен содержать ни одной плохой подстроки. Подстрока пароля длины \(K\) (1 ≤ \(K\) ≤ 6) называется плохой, если одновременно выполняются следующие условия:
*сумма всех её цифр равна \(S\),
*произведение всех её цифр равно \(P\),
*результат побитовой операции XOR всех её цифр равен \(X\).
Вам даны числа \(N\), \(K\), \(S\), \(P\), \(X\). Определите, сколько существует различных паролей для машинки перемещения, удовлетворяющих описанным условиям. Выведите ответ по модулю \(10^9\)+7.
В первой строке входного файла через пробел даны целые числа \(N\), \(K\), \(S\), \(P\), \(X\) (0 ≤ \(S\), \(P\), \(X\) ≤ 1000000).
В выходной файл выведите количество паролей для машинки перемещения по модулю \(10^9\)+7.
1 1 1 1 1
8
3 2 2 1 0
712