Pku3529 Matrix Analysis
题目描述
给定一个M*N的系数矩阵A和一个M*N的初始矩阵B，我们定义矩阵序列SB={Bk}，满足序列第一项B1等于B，对于其他项则满足下式：
其中上式b的右上角的数表示上标，即其在矩阵序列中的位置。
你需要回答Q次询问，每次询问矩阵序列中第k项的第i行第j列的数mod 1000000007。
提示，1000000007是一个质数
数据范围：
M,N<=20,Q<=1000
输入格式
The input consists of a single test case and is given in the following format:
| m | n | t | |
| a11 | a12 | ⋯ | a1n |
| a21 | a22 | ⋯ | a2n |
| ⋮ | ⋮ | ⋱ | ⋮ |
| am1 | am2 | ⋯ | amn |
| b11 | b12 | ⋯ | b1n |
| b21 | b22 | ⋯ | b2n |
| ⋮ | ⋮ | ⋱ | ⋮ |
| bm1 | bm2 | ⋯ | bmn |
| i1 | j1 | k1 | |
| i2 | j2 | k2 | |
| ⋮ | ⋮ | ⋮ | |
| it | jt | kt |
Bounds on the values are: 1 ≤ m, n ≤ 20; 1 ≤ t ≤ 1000; 0 ≤ aij, bij ≤ 10; 1 ≤ it ≤ m; 1 ≤ jt ≤ n; 1 ≤ kt ≤ 109.
输出格式
For each t, output bitjtkt mod 1,000,000,007.
2 2 5
1 2
2 1
1 1
1 1
1 1 2
1 2 2
2 1 2
2 2 2
1 1 3
1
2
2
9
1