Домашнє завдання з математики
Ваш учитель знову дав вам складне домашнє завдання з математики, яке потрібно виконати вчасно.
Це завдання стосується операції ділення і передбачає практику ділення на невеликі числа. Вам потрібно визначити кількість невід'ємних чисел, що складаються рівно з N цифр (провідні нулі дозволені), які задовольняють певним умовам подільності. Наприклад, якщо ви хочете знайти числа, що складаються з 2 цифр, які діляться на 6, але не діляться на 5, то такими числами будуть: 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 і 96.
Зверніть увагу, що нуль ділиться на будь-яке додатне число (див. третій приклад тесту).
Отже, ви вирішили написати програму, щоб автоматизувати виконання цього завдання, оскільки N може бути дійсно великим.
Вхідні дані
Ваша програма буде протестована на одному або декількох тестах. Перша рядок вводу містить одне ціле число T, кількість тестів (1 ≤ T ≤ 1000). Далі слідують T рядків, кожен з яких представляє один тест і складається з цілого числа N (1 ≤ N ≤ 10^18), яке є довжиною чисел, які вам потрібно порахувати (провідні нулі дозволені), за яким слідує пробіл і рядок з 6 цифр (кожна цифра — це '0', '1' або '2'). i-та цифра (найліва цифра — це цифра номер 1) дорівнює '0', якщо числа не повинні ділитися на i, '1', якщо числа повинні ділитися на i, і '2', якщо числа можуть ділитися або не ділитися на i.
Вихідні дані
Для кожного тесту виведіть в окремому рядку одне ціле число — кількість чисел, які вам потрібно порахувати, як описано вище. Оскільки результат може бути дуже великим, виведіть його за модулем 1000000007 (10^9 + 7).