Math Homework

Dongil got a hard math assignment and it is due tomorrow, so barely any time is left.

The assignment is division practice. The goal is to learn the process of dividing an $N$ digit number by a small number. An $N$ digit number here may start with 0, and a number written with leading zeros still counts as an $N$ digit number.

Every question on the assignment has the same shape.

How many two digit integers are divisible by 6 and not divisible by 5?

The answers to that question are 06, 12, 18, 24, 36, 42, 48, 54, 66, 72, 78, 84 and 96, so there are 13 of them.

Note that 0 is divisible by every positive integer.

Too many numbers satisfy the conditions for Dongil to list them one by one, so he decided to find only how many there are.

The first line contains the number of test cases $T$. ($1 \le T \le 1000$)

Each of the next $T$ lines contains an integer $N$ and a string of length 6, separated by a space.

$N$ means the numbers to count have $N$ digits. ($1 \le N \le 10^{18}$)

The string consists only of the characters 0, 1 and 2. If its $i$-th character is 0, the number must not be divisible by $i$. If it is 1, the number must be divisible by $i$. If it is 2, divisibility by $i$ does not matter. ($1 \le i \le 6$)

For each test case, print on one line the number of $N$ digit numbers that satisfy the conditions, modulo 1,000,000,007.