Problem Description

Alice and Marisa live in a vast forest composed of $N$ intersections and $M$ one-way paths. Marisa enjoys visiting Alice's home, but Alice dislikes this impolite guest. Alice is very observant; whenever she notices Marisa taking the exact same path to her house, she pretends to be out, and Marisa has to return disappointed. Marisa has discovered this secret and decides to always take a different path to Alice's house.

Marisa's stamina is limited; she does not want to walk more than $K$ edges to reach Alice's house. Moreover, each time she walks $t$ ($t \leq K$) edges to reach Alice's house, she expends $t^2$ stamina. Marisa wants to know how much stamina she will consume before Alice refuses to see her no matter what (i.e., when Marisa cannot find a new path of length no more than $K$).

Marisa has obtained a map of the forest but is unsure about the locations of her and Alice's homes. Therefore, she will ask you $Q$ queries, each asking for the answer if Marisa's home is at intersection $S$ and Alice's home is at intersection $T$.

A path $A$ is defined as a sequence of $P$ edges ($P$ can be any positive integer or zero) $A_{m_0}, A_{m_1}, A_{m_2}, \ldots, A_{m_{P-1}}$, where for any $1 \leq i < P$, the ending node of $A_{m_{i-1}}$ is the starting node of $A_{m_i}$.

Two paths $A$ and $B$ are identical if they have the same length $P$ and for any $0 \leq i < P$, $A_{m_i} = B_{m_i}$.

Input Format

The first line of input contains four integers $N$, $M$, $K$, and $Q$, as described in the problem.

The next $M$ lines each contain two integers $X$ and $Y$, indicating a one-way path from intersection $X$ to intersection $Y$. Intersections are numbered from $1$ to $N$, and the edge on the $i+1$-th line is numbered $i$.

The next $Q$ lines each contain two integers $S$ and $T$, as described in the problem.

Output Format

For each query, output a line containing the answer for that query, modulo $10^9+7$.

Sample Input and Output

Input Sample #1

2 0 1 1
1 2

Output Sample #1

0

Input Sample #2

2 2 2 1
1 2
2 1
1 1

Output Sample #2

4

Input Sample #3

2 2 100 1
1 2
2 1
1 2

Output Sample #3

166650

Input Sample #4

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

Output Sample #4

632506153
518794755

Notes/Hints

For $20\%$ of the data, $N \leq 5$, $M \leq 10$, $K \leq 3$, $Q \leq 10$.

For $40\%$ of the data, $N \leq 30$, $M \leq 900$, $K \leq 100$, $Q \leq 100$.

For $60\%$ of the data, $N \leq 50$, $M \leq 2,500$, $K \leq 10,000,000$, $Q \leq 1,000$.

For $100\%$ of the data, $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

Explanation of Sample 1: There is no path from $S$ to $T$.

Explanation of Sample 2: Marisa can revisit an intersection, even if it is Alice's or Marisa's home.

见题面 Input 部分

见题面 Output 部分