题目描述

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},…,A_{m_{T-1}}$，其中对于任意 $1 \leq i ＜ P$，有 $A_{m_{i-1}}$ 的结束节点是 $Am_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 接受不了非常大的数， 你只需要输出答案模 $10^9+7$ 的值。

2 0 1 1 
1 2

0

2 2 2 1 
1 2 
2 1 
1 1

4

2 2 100 1 
1 2 
2 1 
1 2

166650

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

632506153
518794755

提示

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

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

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

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

g++ paths.cpp –o paths –Wl,--stack=268435456 –O2 

样例一解释 从 $S$ 到 $T$ 不存在路径

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