题目描述

给定一个MN的系数矩阵A和一个MN的初始矩阵B，我们定义矩阵序列SB={B_{k}}，满足序列第一项B_{1}等于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|| :-:|:-:|:-:|:-:| a_{11}a_{12}⋯a_{1n} a_{21}a_{22}⋯a_{2n} ⋮⋮⋱⋮ a_{m}{1}a{m}{2}⋯a{mn} b_{11}b_{12}⋯b_{1n} b_{21}b_{22}⋯b_{2n} ⋮⋮⋱⋮ b_{m}{1}b{m}{2}⋯b{mn} i_{1}j_{1}k_{1} | i_{2}j_{2}k_{2} | ⋮⋮⋮ | i_{t}j_{t}k_{t} | mnt | a_{11}a_{12}⋯a_{1n} a_{21}a_{22}⋯a_{2n} ⋮⋮⋱⋮ a_{m}{1}a{m}{2}⋯a{mn} b_{11}b_{12}⋯b_{1n} b_{21}b_{22}⋯b_{2n} ⋮⋮⋱⋮ b_{m}{1}b{m}{2}⋯b{mn} i_{1}j_{1}k_{1} | i_{2}j_{2}k_{2} | ⋮⋮⋮ | i_{t}j_{t}k_{t} | Bounds on the values are: 1 ≤ m, n ≤ 20; 1 ≤ t ≤ 1000; 0 ≤ a_{ij}, b_{ij} ≤ 10; 1 ≤ i_{t} ≤ m; 1 ≤ j_{t} ≤ n; 1 ≤ k_{t} ≤ 10^{9}.

输出格式

For each t, output b_{i_{t}j_{t}}^{k_{t}} 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

提示

没有写明提示

题目来源

没有写明来源