#P3610. [Heoi2014]林中路径

    ID: 2817 传统题 5000ms 256MiB 尝试: 271 已通过: 116 难度: 7 上传者: 标签>难度分类提高+/省选-线性代数与代数矩阵快速幂矩阵加减法CF2200

[Heoi2014]林中路径

[HEOI2014] 林中路径

题目描述

Alice 和 Marisa 都住在一个巨大的由 NN 个路口与 MM 条单向小道构成的森林中。Marisa 非常喜欢到 Alice 家里去玩,但是 Alice 并不喜欢这位鲁莽的来客。Alice 非常擅长观察, 因此每当她发现 Marisa 走了一条与之前完全相同的路径来到她家时,她就会装作不在家, Marisa 就只好败兴而归。Marisa 发现了这个秘密,因此她决定每次走不同的路径到 Alice 家。

Marisa 体力有限,她不想走超过 KK 条边到达 Alice 家,并且,每当她走 tt(t≤Kt\le K)条边 到达 Alice 家时,她需要付出 t2t^2 的体力。Marisa 想知道,在 Alice 无论如何都不想接见她之前(即 Marisa 无法走一条长度不超过 KK 的与之前不同的路径),她走完所有这些不同的路径,总共会消耗多少体力。

现在 Marisa 拿到了一张森林的地图,但因为 Marisa 非常笨,她并不知道自己的家和 Alice 的家在哪一个路口,因此她会询问你 QQ 次,每次询问假如 Marisa 的家的位置在 SS 而 Alice 的家的位置在 TT 时的答案。

一条长度为 PP 的路径由依次经过的 PP 条有向边组成,前一条边的终点须是后一条边的起点。路径允许重复经过任意路口,也允许重复经过同一条边。长度为 00 的路径停留在起点。

两条路径完全相同,当且仅当它们经过的边数相等,且每个位置经过的边编号均相同。连接同一对路口的不同边仍各有自己的编号。

输入格式

输入数据第一行包含四个整数 NN , MM , KK , QQ ,含义如题所述。

接下来 MM 行,每行两个整数 XX , YY ,表示从第 XX 个路口到第 YY 个路口有一条单向小道。路口的标号为 1,2,3,…,N1,2,3,…,N ,输入中第 ii 条小道的编号为 ii。

接下来 QQ 行,每行两个整数 SS 和 TT,含义如题所述。

输出格式

对于每个询问,输出一行,表示这次询问的答案。由于 Marisa 接受不了非常大的数, 你只需要输出答案模 109+710^9+7 的值。

样例 #1

2 0 1 1
1 2
0

样例 #2

2 2 2 1
1 2
2 1
1 1
4

样例 #3

2 2 100 1
1 2
2 1
1 2
166650

样例 #4

2 3 100 2
1 2
1 2
2 1
2 2
2 1
632506153
518794755

数据范围

对于 20%20\% 的数据,N≤5N\leq 5,M≤10M\leq 10,K≤3K\leq 3,Q≤10Q\leq 10。

对于 40%40\% 的数据,N≤30N\leq 30,M≤900M\leq 900,K≤100K\leq 100,Q≤100Q\leq 100。

对于 60%60\% 的数据,N≤50N\leq 50,M≤2,500M\leq 2,500,K≤10,000,000K\leq 10,000,000,Q≤1,000Q\leq 1,000。

对于 100%100\% 的数据,2≤N≤1002\leq N\leq 100,0≤M≤100,0000\leq M\leq 100,000,0≤K≤1,000,000,0000\leq K\leq 1,000,000,000,0≤Q≤10,0000\leq Q\leq 10,000,1≤X,Y,S,T≤N1\leq X,Y,S,T\leq N。

样例解释

样例 1 中,从 SS 到 TT 不存在合法路径。

样例 2 中,Marisa 可以重复经过一个路口,即使这个路口是 Alice 的家或她自己的家。