Description

给定一个MN的系数矩阵A和一个MN的初始矩阵B，我们定义矩阵序列SB={B ~k~ }，满足序列第一项B~1~等于B，对于其他项则满足下式：

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

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

   提示，1000000007是一个质数

数据范围：

   M,N<=20,Q<=1000

Format

Input

The input consists of a single test case and is given in the following format:

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^ .

Output

For each t , output b~i~t~j~t~~^k~t~^ mod 1,000,000,007.

Samples

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