题目描述

给定一张 $n$ 个点的有向图 $G=(V,E)$。

对于任意两个点 $u,v(1\le u,v\le n)$，$u$ 向 $v$ 的连边数为：$\sum_{i=1}^k \operatorname{out}(u,i)\times \operatorname{in}(v,i)$。

现在给出 $m$ 个询问，每次询问给出三个参数 $u,v,d$，你需要回答从节点 $u$ 出发，经过不超过 $d$ 条边到达节点 $v$ 的路径有多少种。答案对 $10^9+7$ 取模。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，对于第 $(i+1)$ 行 $2k$ 个整数，前 $k$ 个整数表示 $\operatorname{out}(i,j)$，后 $k$ 个数描述 $\operatorname{in}(i,j)$。

第 $n+2$ 行一行一个整数 $m$ 表示询问次数。

接下来 $m$ 行，每行三个整数 $u,v,d(0\le d<2^31)$，描述一组询问。

输出格式

对于每个询问，输出一行一个整数，描述答案。

5 2
2 5 4 3
7 9 2 4
0 1 5 2
6 3 9 2
2147483647 1000000001 233522788488
10
1 1 0
2 2 1
2 4 5
4 3 10
3 4 50
1 5 1000

1
51
170107227
271772358
34562176
890241289

提示

对于 $100\%$ 的数据，$1\le n\le 1000$，$\1le k\le 20$，$1\le m\le 50$。

题目来源

没有写明来源