#2684. Pku3529 Matrix Analysis

题目描述

** **给定一个MN的系数矩阵A和一个MN的初始矩阵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 |
---|---|---|---
a 11 | a 12 | ⋯ | a 1 n
a 21 | a 22 | ⋯ | a 2 n
⋮ | ⋮ | ⋱ | ⋮
_a m_1 | _a m_2 | ⋯ | a mn
b 11 | b 12 | ⋯ | b 1 n
b 21 | b 22 | ⋯ | b 2 n
⋮ | ⋮ | ⋱ | ⋮
_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 ≤ 109.

输出格式

For each t , output b itjtkt 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  

数据范围与提示