UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2684. Pku3529 Matrix Analysis

Statistics 下载数据

Description

       给定一个M*N的系数矩阵A和一个M*N的初始矩阵B,我们定义矩阵序列SB={Bk},满足序列第一项B1等于B,对于其他项则满足下式:

其中上式b的右上角的数表示上标,即其在矩阵序列中的位置。

       你需要回答Q次询问,每次询问矩阵序列中第k项的第i行第j列的数mod 1000000007

       提示,1000000007是一个质数

数据范围:

       M,N<=20,Q<=1000

Input

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 ≤ itm; 1 ≤ jtn; 1 ≤ kt ≤ 109.

Output

For each t, output bitjtkt mod 1,000,000,007.

Sample Input

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

Sample Output

1
2
2
9
1

Hint

Source