Pku3529 Matrix Analysis

给定一个 $M\times N$ 的系数矩阵 $A$ 和一个 $M\times N$ 的初始矩阵 $B$。定义矩阵序列 $S_B=\{B_k\}$，其中 $B_1=B$。

对于任意 $k>1$、$1\le i\le M$、$1\le j\le N$，定义：

$$b_{ij}^{k}=b_{ij}^{k-1}+\sum_{p=1}^{i-1}a_{pj}b_{pj}^{k}+\sum_{q=1}^{j-1}a_{iq}b_{iq}^{k}.$$

当求和范围为空时，对应的和为 $0$。其中，$b_{ij}^{k}$ 表示矩阵序列中第 $k$ 个矩阵的第 $i$ 行、第 $j$ 列元素。

你需要回答 $Q$ 次询问。每次询问给出 $i$、$j$、$k$，求 $b_{ij}^{k}\bmod (10^9+7)$。

模数 $10^9+7$ 是一个质数。

输入格式

第一行包含三个整数 $M$、$N$、$Q$。

接下来 $M$ 行，每行包含 $N$ 个整数，表示系数矩阵 $A$。

随后 $M$ 行，每行包含 $N$ 个整数，表示初始矩阵 $B$。

接下来 $Q$ 行，每行包含三个整数 $i_t$、$j_t$、$k_t$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示：

$$b_{i_tj_t}^{k_t}\bmod (10^9+7).$$

样例输入

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

数据范围

• $1\le M,N\le 20$；
• $1\le Q\le 1000$；
• $0\le a_{ij},b_{ij}\le 10$；
• $1\le i_t\le M$；
• $1\le j_t\le N$；
• $1\le k_t\le 10^9$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

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