MATEX  Matrix Exponentiation
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 3kBC code got 654321 points, with 31MB of memory usage. (Lot of stuff!)
(Timing edited 20170211, 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
Uniformrandom 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 MATrixEXponentiationspeed.
Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file.
hide comments
Martin Radev:
20161107 23:56:58
Pretty hard to get to the top. I reached 140000 pts. I guess I need a faster way to read and write io.


Martin Radev:
20161101 10:54:15
I really wonder how one has managed to get >100000 points on this one.

Added by:  Francky 
Date:  20130227 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 