Домашнее задание по математике
Да, ваш учитель дал вам ещё одно сложное домашнее задание по математике, и вам нужно его выполнить до установленного срока.
Это задание связано с операцией деления и предполагает практику деления на небольшие числа. Вам необходимо определить количество неотрицательных чисел, состоящих ровно из 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).