Description

Alice and Marisa both live in a huge forest consisting of $N$ vertices and $M$ directed edges. Marisa loves visiting Alice, but Alice does not like this reckless guest. Alice is very observant, so whenever she notices that Marisa has taken a path to her home that is exactly the same as a previous one, she pretends not to be at home, and Marisa has to go back disappointed. Marisa has discovered this secret, so she decides to take a different path to Alice’s home each time.

Marisa has limited stamina. She does not want to walk more than $K$ edges to reach Alice’s home, and each time she reaches Alice’s home after walking $t$ edges (where $t \le K$), she must spend $t^2$ stamina. Marisa wants to know how much total stamina she will spend before Alice refuses to see her no matter what (that is, when Marisa can no longer find a path of length at most $K$ that is different from all the previous ones).

Now Marisa has a map of the forest, but because she is very clumsy, she does not know which vertices are her home and Alice’s home. Therefore, she will ask you $Q$ times; in each query, you are asked to determine the answer if Marisa’s home is at $S$ and Alice’s home is at $T$.

A path $A$ of length $P$ (where $P$ can be any nonnegative integer) is defined as a sequence of edges $A_{m_0}, A_{m_1}, A_{m_2}, \dots, A_{m_{P-1}}$, such that for any $1 \le i < P$, the ending vertex of $A_{m_{i-1}}$ is the starting vertex of $A_{m_i}$.

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

Input Format

The first line contains four integers $N$, $M$, $K$, $Q$, as described above.

The next $M$ lines each contain two integers $X$, $Y$, indicating a directed edge from vertex $X$ to vertex $Y$. Vertices are numbered $1, 2, 3, \dots, N$. The edge on the $(i+1)$-th line has index $i$. The following $Q$ lines each contain two integers $S$ and $T$, as described above.

Output Format

For each query, output one line with the answer. Since Marisa cannot accept very large numbers, you only need to output the answer modulo $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

Hint

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

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

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

For $100\%$ of the testdata, $2 \le N \le 100$, $0 \le M \le 100,000$, $0 \le K \le 1,000,000,000$, $0 \le Q \le 10,000$, $1 \le X, Y, S, T \le N$.

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

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

Explanation for Sample 2: Marisa may pass through a vertex multiple times, even if that vertex is Alice’s home or Marisa’s home.

Translated by ChatGPT 5