BZPRO

#2684. Pku3529 Matrix Analysis

内存限制：128 MiB 时间限制：3 Sec
提交 提交记录 讨论

题目描述

       给定一个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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository