Little Q is a teacher for the light-speed spaceship course at Interstellar Elementary School. She is preparing to purchase $n$ distinct energy stones from the school's interstellar energy store. Each energy stone has one unit of energy and a unique positive integer ID between $1$ and $n$. She wants to distribute them among $m$ students to help them practice piloting light-speed spaceships.

During distribution, each energy stone is assigned to exactly one student, and it is allowed for a student to receive no energy stones. Let $c_i$ denote the total number of energy stones assigned to the $i$-th student, satisfying $\sum_{i=1}^m c_i = n$ and $c_i \ge 0$. Two distribution schemes are considered essentially different if and only if there exists a student who is assigned a different set of energy stone IDs in the two schemes. For example, with two energy stones and two students, assigning energy stone 1 to student 1 and energy stone 2 to student 2 is considered essentially different from assigning energy stone 1 to student 2 and energy stone 2 to student 1, because the set of energy stone IDs assigned to student 1 in the first scheme is $\{1\}$, while in the second scheme it is $\{2\}$.

However, every student wants to have more energy stones for their light-speed spaceship than the other students. Therefore, if a student is assigned more energy stones than another student, they will have greater satisfaction.

Initially, each student's satisfaction is $1$. After distributing $n$ energy stones, the satisfaction of the $i$-th student is calculated as follows: * Consider each student $j$ other than $i$ in turn. If $c_i > c_j$, the satisfaction of $i$ becomes $A_{i,j}$ times its original value; if $c_i = c_j$, the satisfaction of $i$ becomes $B_{i,j}$ times its original value; if $c_i < c_j$, the satisfaction of $i$ remains unchanged. It is guaranteed that $1 < B_{i,j} < A_{i,j} \le 10^9$.

For the $i$-th student, let their satisfaction after distributing $n$ energy stones be the final value after considering all $m-1$ other students. Little Q defines the weight of a distribution scheme as the product of the satisfactions of the $m$ students after distributing the $n$ energy stones. Little Q wants to know the sum of the weights of all essentially different distribution schemes modulo $317$. Since she is a light-speed spaceship teacher and not a light-speed calculation teacher, she hopes you, an expert in light-speed calculation, can quickly tell her the result modulo $317$.

Furthermore, since Little Q has not tested the specific performance of the light-speed spaceships, the energy requirements may change when the performance of the spaceships varies. Therefore, she will ask $q$ queries about the total number of energy stones $n$ she might purchase. For each $n$, you need to tell her the sum of the weights of all distribution schemes modulo $317$ if she were to purchase $n$ energy stones.

Input

The input is read from standard input. The first line contains a positive integer $m$ ($1 \le m \le 12$), representing the total number of students. The next $m$ lines contain the $m \times m$ matrix $A$, where each line contains $m$ positive integers. The value in the $i$-th row and $j$-th column represents $A_{i,j}$, where $A_{i,j} = 0$ when $i = j$, and $1 < A_{i,j} \le 10^9$ when $i \neq j$. The next $m$ lines contain the $m \times m$ matrix $B$, where each line contains $m$ positive integers. The value in the $i$-th row and $j$-th column represents $B_{i,j}$, where $B_{i,j} = 0$ when $i = j$, and $1 < B_{i,j} < A_{i,j}$ when $i \neq j$. The next line contains a positive integer $q$ ($1 \le q \le 100$), representing the number of queries. The next $q$ lines each contain a positive integer $n$ ($1 \le n \le 10^{18}$), representing the query for the answer to the original problem when the total number of energy stones is $n$.

Output

Output to standard output. Output $q$ lines, each containing an integer between $0$ and $316$, representing the sum of the weights of the energy stone distribution schemes modulo $317$.

Examples

Input 1

3
0 7 5
5 0 7
4 6 0
0 4 4
3 0 4
3 2 0
4
1
2
10
1000000000000000000

Output 1

37
303
46
148

Note

For $n=1$, there are $3$ essentially different distribution schemes, which correspond to assigning the unique energy stone to student $1, 2,$ or $3$. The weights of these schemes are $280, 420, 288$ respectively. The sum of the weights of all distribution schemes is $988$, and the result modulo $317$ is $37$.

For $n=2$, there are $9$ essentially different distribution schemes. For each pair of positive integers $(i, j)$ satisfying $1 \le i, j \le 3$, assigning energy stone $1$ to student $i$ and energy stone $2$ to student $j$ corresponds to one scheme. The weights of the schemes are given in the table below, where the number in the $i$-th row and $j$-th column represents the weight of the scheme where energy stone $1$ is assigned to student $i$ and energy stone $2$ is assigned to student $j$:

The sum of the weights of all schemes is $3156$, and the result modulo $317$ is $303$.