题目描述

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

杰杰本着实事求是的态度，审时度势，向女神奖杯提出了自己的愿望：想要一个女性朋友。

杰杰的愿望实现了，可是女性朋友却和他不在一个城市。杰杰想要知道：如果要到达女性朋友的所在城市，有多少种方案供他选择？

杰杰所在的世界有 $n$ 个城市，从 $1$ 到 $n$ 进行编号。任意两个城市都通过有向道路连接。

每个城市 $u$ 有 $k$ 个入点权：$in_{u,1},in_{u,2},\cdots,in_{u,k}$，有 $k$ 个出点权：$ou_{u,1},ou_{u,2},\cdots,ou_{u,k}$。对于任意两个城市 $(u,v)$（$u$ 可以等于 $v$），$u$ 到 $v$ 的道路条数为 $(ou_{u,1}\times in_{v,1}+ou_{u,2}\times in_{v,2}+\cdots+ou_{u,k}\times 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},\cdots,ou_{i,k},in_{i,1},in_{i,2},\cdots,in_{i,k}$。
接下来一个整数 $m$，表示 $m$ 个询问。
接下来 $m$ 行，每行三个整数：$u,v,d$，询问从 $u$ 城市通过不超过 $d$ 条道路到达 $v$ 城市的方案数。

将每个方案所经过的道路，按顺序写成一个序列（序列可以为空）。两个方案不同，当且仅当他们的道路序列不完全相同。

输出格式

对于每个询问，输出一个方案数。由于答案可能太大，输出其除以 $10^9+7$ 后的余数。

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

数据规模与约定

对于 $100\%$ 的数据满足 $n\le 10^3$，$k\le 20$，$m\le 50$;

保证 $1\le u, v\le n$，其它所有读入为不超过 $2147483647$ 的非负整数。

题目来源

By 佚名提供