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* ≤ 1018) 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 (109 + 7).
## Input
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* ≤ 1018) 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
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 (109 + 7).
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ N_k \in \mathbb{Z} $ with $ 1 \le N_k \le 10^{18} $ be the number of digits.
- Let $ D_k = d_{k,1}d_{k,2}d_{k,3}d_{k,4}d_{k,5}d_{k,6} \in \{0,1,2\}^6 $ be a constraint string, where:
- $ d_{k,i} = 0 $: numbers must **not** be divisible by $ i $,
- $ d_{k,i} = 1 $: numbers must be **divisible** by $ i $,
- $ d_{k,i} = 2 $: no constraint on divisibility by $ i $.
Let $ \mathcal{S}_k $ be the set of all $ N_k $-digit numbers (with leading zeros allowed) over $ \{0,1,\dots,9\}^{N_k} $, interpreted as integers in $ [0, 10^{N_k} - 1] $.
**Constraints**
1. $ 1 \le T \le 10 $
2. $ 1 \le N_k \le 10^{18} $ for all $ k $
3. $ d_{k,i} \in \{0,1,2\} $ for all $ i \in \{1,2,3,4,5,6\} $
**Objective**
For each test case $ k $, compute:
$$
\left| \left\{ x \in [0, 10^{N_k} - 1] \,\middle|\, \forall i \in \{1,2,3,4,5,6\},\
\begin{cases}
i \nmid x & \text{if } d_{k,i} = 0 \\
i \mid x & \text{if } d_{k,i} = 1 \\
\text{no constraint} & \text{if } d_{k,i} = 2
\end{cases}
\right\} \right| \mod 1000000007
$$