#4362. Graph

内存限制:256 MiB 时间限制:10 Sec

题目描述

给出一张n个点的有向图G(V,E)。对于任意两个点u,v(u可以等于v),u向v的连边数为:
∑OUT(u,i) * IN(v,i),其中1<=i<=K
其中k和数组out,in均已知,现在给出m个询问,每次询问给出三个参数u,v,d,你需要回答从节点
u出发,经过不超过d条边到达节点v的路径有多少种。答案模10^9+7。

输入格式

第一行两个整数n,k。
接下来n行,第i行有2k个整数,前k个整数描述outi,后k个数描述ini。
接下来一行一个整数m。
接下来m行,每行三个整数u,v,d(0<=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

数据范围与提示

1<=N<=1000

1<=K<=20

1<=M<=50