#3583. 杰杰的女性朋友

题目描述

杰杰是魔法界的一名传奇人物。他对魔法具有深刻的洞察力，惊人的领悟力，以及令人叹为观止的创造力。自从他从事魔法竞赛以来，短短几年时间，就已经成为世界公认的实力最强的魔法选手之一。更让人惊叹的是，他几乎没有借助外界力量，完全凭借自己的努力达到了普通人难以企及的高度。在最近的世界魔法奥林匹克竞赛上，他使用高超的魔法本领，一路过关斩将，在最后时刻一举击败了前冠军"旅行者"，获得了魔法界最高的荣耀：女神奖杯！女神奖杯可不是一个普通的奖杯，她能够帮杰杰实现一个愿望。
杰杰本着实事求是的态度，审时度势，向女神奖杯提出了自己的愿望：想要一个女性朋友。

杰杰的愿望实现了，可是女性朋友却和他不在一个城市。杰杰想要知道：如果要到达女性朋友的所在城市，有多少种方案供他选择？
杰杰所在的世界有n个城市，从1到n进行编号。任意两个城市都通过有向道路连接。每个城市u有k个入点权：in[u][1],in[u][2]...in[u][k]，有k个出点权：ou[u][1],ou[u][2]...ou[u][k]。对于任意两个城市(u,v)（u可以等于v），u到v的道路条数为(ou[u][1]*in[v][1]+ou[u][2]*in[v][2]+...+ou[u][k]*in[v][k])条。杰杰有m次询问，每次询问由三元组(u,v,d)构成，询问从u城市通过不超过d条道路到达v城市的方案数。
为了温柔的杰杰和他的女性朋友的美好未来，帮助他解答这个问题吧。

输入格式

第一行读入两个正整数n，k，含义如题所示。接下来n行每行2k个整数，第i行代表第i个城市，前k个整数代表i号城市的出点权，后k个整数代表i号城市的入点权：
ou[i][1],ou[i][2],…,ou[i][k],in[i][1],in[i][2],…,in[i][k]
接下来一个整数m，表示m个询问。
接下来m行，每行三个整数:u,v,d，询问从u城市通过不超过d条道路到达v城市的方案数。
将每个方案所经过的道路，按顺序写成一个序列（序列可以为空）。两个方案不同，当且仅当他们的道路序列不完全相同。

输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以1000000007后的余数。

样例

样例输入

5 2  

2 5 4 3  

7 9 2 4  

0 1 5 2  

6 3 9 2  

2147483647 1000000001 233522 788488  

10  

1 1 0  

2 2 1  

2 4 5  

4 3 10  

3 4 50  

1 5 1000  

3 5 1000000000  

1 2 500000000  

4 5 2147483647  

3 1 2147483647  

样例输出

1  

51  

170107227  

271772358  

34562176  

890241289  

8516097  

383966304  

432287042  

326522835  

数据范围与提示

数据规模和约定

n<=1000

k<=20

m<=50

保证1<=u, v<=n, 其它所有读入为不超过2147483647的非负整数