During the pandemic, the most exciting outdoor activity one can do is walk around the local park, alone. All this alone-time inspired you to wonder about the following problem.

The park has \(n\) interesting locations numbered from \(1\) to \(n\). You can move between any two locations only if there is a trail between them. The structure of the park is a connected undirected graph. The number of steps needed to move from location \(i\) to an adjacent location \(j\) is \(c_{i, j}\). Of course \(c_{i, j}\) is equal to \(c_{j, i}\) since the distance is the same in both directions.

You can ''walk'' from location \(x\) to some other location \(y\) by moving through a series of adjacent locations. You can revisit locations and repeat trails. The length of this ''walk'' is the sum of steps you made walking between all the locations. See notes for an example.

Given a graph representation of the park, your job is to answer two types of questions:

• What is the number of walks from location \(x\) to location \(y\) with exactly \(k\) steps?
• What is the number of walks from location \(x\) to location \(y\) with at most \(k\) steps?

Input Specification

The first line of input contains an integer \(n\) \((2 \leq n \leq 100)\), the number of locations

The next \(n\) lines contain the \(n\) by \(n\) adjacency matrix (\(c\)) of the park where \(c_{i, j}\) \(=\) \(c_{j, i}\) and \(1 \leq c_{i, j} \leq 100\). If \(c_{i, j}\) \(=\) \(-1\) that means there is no direct trail between the two locations. The graph is guaranteed to be connected.

The next line contains an integer \(q\) \((1 \leq q \leq 10^5)\), the number of questions.

The next \(q\) line contains four integers \(t\) \((1 \leq t \leq 2)\) and \(k\) \((1 \leq k \leq 100)\), the type of question and the number of steps and \(x\) and \(y\) \((1 \leq x, y \leq n)\), the starting and ending location. See description above.

Output Specification

For each question output a single integer on a separate line, the answer to the question. Since this number can get large, output it modulo \(10^9+7\).

Scoring

<latex> \begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 10 & \text{The sum of answers across all questions is at most 2000000} \cr \hline 2 & 20 & \text{$c_{i, j}$ is at most $1$ (unweighted graph)} \cr \hline 3 & 30 & \text{$n$ is at most $30$, $c_{i, j}$ is at most $30$ and $k$ is at most $30$} \cr \hline 4 & 40 & \text{No additional constraint} \cr \hline \end{array} </latex>

Sample Input

3
-1 2 1
2 -1 1
1 1 -1
2
1 3 1 3
2 3 1 3

Sample Output

3
4

Notes

In the example test case above, the three ways to walk from location 1 to location 3 in exactly 3 steps are:

• 1 -> 2 -> 3
• 1 -> 3 -> 1 -> 3
• 1 -> 3 -> 2 -> 3