#4362. Graph

题目描述

给出一张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