#P3583. 杰杰的女性朋友

    ID: 2784 传统题 1000ms 256MiB 尝试: 316 已通过: 104 难度: 7 上传者: 标签>难度分类提高线性代数与代数矩阵快速幂矩阵乘法低秩矩阵幂降维CF2200

杰杰的女性朋友

杰杰的女性朋友

题目描述

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

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

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

杰杰所在的世界有 nn 个城市,从 11 到 nn 进行编号。道路是有向的,同一对城市之间可以有多条道路,也允许自环。

每个城市 uu 有 kk 个入点权 inu,1,…,inu,k\mathrm{in}_{u,1},\ldots,\mathrm{in}_{u,k} 和 kk 个出点权 ouu,1,…,ouu,k\mathrm{ou}_{u,1},\ldots,\mathrm{ou}_{u,k}。对于任意城市 u,vu,v,从 uu 指向 vv 的道路条数为

$$\sum_{j=1}^{k}\mathrm{ou}_{u,j}\,\mathrm{in}_{v,j}.$$

杰杰有 mm 次询问,每次询问由三元组 (u,v,d)(u,v,d) 构成,询问从 uu 城市通过不超过 dd 条道路到达 vv 城市的方案数。

为了温柔的杰杰和他的女性朋友的美好未来,帮助他解答这个问题吧。

输入格式

第一行读入两个正整数 n,kn,k,含义如题所示。
接下来 nn 行每行 2k2k 个整数,第 ii 行代表第 ii 个城市,前 kk 个整数代表 ii 号城市的出点权,后 kk 个整数代表 ii 号城市的入点权:$ou_{i,1},ou_{i,2},\cdots,ou_{i,k},in_{i,1},in_{i,2},\cdots,in_{i,k}$。
接下来一个整数 mm,表示 mm 个询问。
接下来 mm 行,每行三个整数:u,v,du,v,d,询问从 uu 城市通过不超过 dd 条道路到达 vv 城市的方案数。

将每个方案所经过的道路,按顺序写成一个序列(序列可以为空)。不同的道路即使起点和终点相同,也分别计数。允许重复经过城市或道路;只有起点和终点相同时,才有一个不经过任何道路的方案。

输出格式

每次询问输出一行一个方案数。由于答案可能太大,输出其除以 109+710^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%100\% 的数据满足 n≤103n\le 10^3,k≤20k\le 20,m≤50m\le 50;

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