#2218. 「HEOI2014」林中路径

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

现在 Marisa 拿到了一张森林的地图,但因为 Marisa 非常笨,她并不知道自己的家和 Alice 的家在哪一个路口,因此她会询问你 Q 次,每次询问假如 Marisa 的家的位置在 S 而 Alice 的家的位置在 T 时的答案。     一条路径 A 的定义是指一个长度为 P P 可以为任意正整数或零)的边的序列 A_{m_0},A_{m_1},A_{m_2},\ldots,A_{m_{P-1}} ,其中对于任意 1 \leq i < P ,有 A_{m_{i-1}} 的结束节点是 A_{m_i} 的起始节点。 
两条路径 A B 完全相同是指两条路径的长度均为 T 并且对任意 0 \leq i<P ,有 A_{m_i}=B_{m_i}

输入格式

输入数据第一行包含四个整数 N,M,K,Q ,含义如题所述。 
接下来 M 行,每行两个整数 X,Y ,表示从第 X 个路口到第 Y 个路口有一条单向小道。路口的标号为 1,2,3,…,N ,在输入数据第 i+1 行的边的标号为 i
接下来 Q 行,每行两个整数 S T ,含义如题所述。

输出格式

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

样例

样例输入 1

2 0 1 1
1 2

样例输出 1

0

样例解释 1

S T 不存在路径。

样例输入 2

2 2 2 1
1 2
2 1
1 1

样例输出 2

4

样例解释 2

样例二解释 Marisa 可以重复经过一个路口,即使这个路口就是 Alice 的家或 Marisa 的家。

样例输入 3

2 2 100 1
1 2
2 1
1 2

样例输出 3

166650

样例输入 4

2 3 100 2
1 2
1 2
2 1
2 2
2 1

样例输出 4

632506153

数据范围与提示

对于 100\% 的数据, 2 \leq N \leq 100,\ 0 \leq M \leq 10^6,\ 0 \leq K \leq 10^9,\ 0 \leq Q \leq 10^5,\ 1 \leq X,Y,S,T \leq N

备注:样例输出 4 原有两行,故不确定保留下的输出是否正确。5/3/17