2684 - Pku3529 Matrix Analysis

   给定一个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: mnt a11a12?a1n a21a22?a2n ???? am1am2?amn b11b12?b1n b21b22?b2n ???? bm1bm2?bmn i1j1k1 i2j2k2 ??? itjtkt

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.