eolymp
bolt
Try our new interface for solving problems
Problems

Math Homework

Math Homework

Time limit 1 second
Memory limit 64 MiB

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.

Input data

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 (1T1000). Followed by T lines, each line represents one test case, and consists of an integer N (1N10^18) 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.

Output data

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 1000000007 (10^9 + 7).

Examples

Input example #1
4
2 222201
1 111001
1 111111
2 222222
Output example #1
13
1
1
100
Source Arab Collegiate Programming Contest 2012