Many problems can be solved with matrix exponentiation. This task can be 'easily' solved with a O(log(N)) algorithm. You'll have to work on the constant to get more points. We'll work with a 'small' matrix and constant modulo. This task should help you to try some speed improvements for problems like R Numbers, Grid Tiling, and the great Flibonakki...
You don't need to solve the whole input, just as many cases as you can. Not all, it could be impossible. You will get one point per case.
There will be one input file and the matrix will have a size W = 18, unlike in the sample.
For your information, my fastest 3kB-C code got 654321 points, with 31MB of memory usage. (Lot of stuff!)
(Timing edited 2017-02-11, after compiler changes)

Input

The first line contains an integer number W : the size of the squared matrix.
The W next lines contains W integers Mij : the coefficients of the matrix, line by line. In each the 838383 next lines there are three integers I, J, N.
You don't have to read the whole input, just as many as you can solve...

Output

For as many test cases you can, on a single line, print the coefficient on the Ith line, Jth column of the matrix M^N (M to the power N). As the answer could be a big number, output the answer modulo 1000000007.

Example

Input:
5
32 82 7 66 30
57 1 28 2 89
53 66 6 35 61
45 87 88 24 20
35 22 23 80 93
1 1 1
1 5 2
5 1 3
5 5 99
[...]

Output:
32
12795
2714937
764817976

Explanations

For the first case: M^1 =

32 82  7 66 30
57  1 28  2 89
53 66  6 35 61
45 87 88 24 20
35 22 23 80 93

For the second case: M^2=

10089  9570  9060  6505 12795
 6570  8655  2818 11912 11824
 9486  9195  6738  9560 14203
12843 12113  5851  8400 16801
10448 13416 10178 12519 14660

For the third case: M^3=

2089068 2282253 1259668 2181834 3027095
1802809 2029855 1625446 1781368 2477165
2112086 2375941 1532239 2245976 3026032
2377555 2551827 1589794 2622329 3550751
2714937 2953573 1948704 2545886 3742082

Constraints

W = 18
1 ≤ I,J ≤ W
1 ≤ Mij ≤ 10^9
1 ≤ N ≤ 10^18

Uniform-random input in the range.

Score

As in the example, if you can output the 4 first correct answers, your score will be 4 points. No need to solve all the input, the minimum is 1 ; every solver in 'any' language will be able to check his MATrix-EXponentiation-speed.

Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file.