400384: GYM100155 J Math Homework

Yes, your teacher gave you another hard math homework, and you have to finish it before its deadline.

This homework is about the division operation, and it's a practice for the division by small numbers. You are asked to count the non-negative numbers which consist of exactly N digits (leading zeros are allowed), and they satisfy some division requirements, for example let's say you want to count the numbers which consist of 2 digits and they are divisible by 6 and not divisible by 5, these are the numbers which satisfy these requirements: 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 and 96.

Note that zero is divisible by any positive number (check the third sample test case).

So, you decided to write a program to solve this homework for you, because N can be really large.

Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1  ≤  T  ≤  10). Followed by T lines, each line represents one test case, and consists of an integer N (1  ≤  N  ≤  10¹⁸) which is the length of the numbers you are asked to count (again, leading zeros are allowed) followed by a space then a string of 6 digits (each digit is '0', '1' or '2'), the ith digit (the left most digit is the digit number 1) is '0' if the numbers shouldn't be divisible by i, and it's '1' if the numbers should be divisible by i, and it's '2' if the numbers can be divisible or not divisible by i.

For each test case, print on a single line one integer, the count of the numbers you are asked to count as described above, since the result may be very large, print it modulo 1,000,000,007 (10⁹ + 7).

4
2 222201
1 111001
1 111111
2 222222

13
1
1
100