Домашнє завдання з математики#6531

Домашнє завдання з математики

1 секунда

64 мегабайти

Легка

Ваш учитель знову дав вам складне домашнє завдання з математики, яке потрібно виконати вчасно.

Це завдання стосується операції ділення і передбачає практику ділення на невеликі числа. Вам потрібно визначити кількість невід'ємних чисел, що складаються рівно з $N$ цифр (провідні нулі дозволені), які задовольняють певним умовам подільності. Наприклад, якщо ви хочете знайти числа, що складаються з $2$ цифр, які діляться на $6$ , але не діляться на $5$ , то такими числами будуть: $06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84$ 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 і $96$ .

Зверніть увагу, що нуль ділиться на будь-яке додатне число (див. третій приклад тесту).

Отже, ви вирішили написати програму, щоб автоматизувати виконання цього завдання, оскільки $N$ може бути дійсно великим.

Вхідні дані

Ваша програма буде протестована на одному або декількох тестах. Перший рядок вводу містить одне ціле число $T$ , кількість тестів ( $1 \leq T \leq 1000$ 1 \le T \le 1000). Далі слідують $T$ рядків, кожен з яких представляє один тест і складається з цілого числа $N$ ( $1 \leq N \leq 1 0^{18}$ 1 \le N \le 10^{18}), яке є довжиною чисел, які вам потрібно порахувати (провідні нулі дозволені), за яким слідує пробіл і рядок з 6 цифр (кожна цифра — це ' $0$ ', ' $1$ ' або ' $2$ '). $i$ -та цифра (найліва цифра — це цифра номер $1$ ) дорівнює ' $0$ ', якщо числа не повинні ділитися на $i$ , ' $1$ ', якщо числа повинні ділитися на $i$ , і ' $2$ ', якщо числа можуть ділитися або не ділитися на $i$ .

Вихідні дані

Для кожного тесту виведіть в окремому рядку одне ціле число — кількість чисел, які вам потрібно порахувати, як описано вище. Оскільки результат може бути дуже великим, виведіть його за модулем $1000000007$ ( $1 0^{9} + 7$ 10^9 + 7).

Приклади

Приклад 1