Bessie’s Escape

Bessie has been kidnapped by aliens and is now imprisoned on an alien spaceship. The spaceship contains \(N\) rooms numbered from \(1\) to \(N\) (with \(1\le N\le 60\)), and some one‐way doors connect certain pairs of rooms. (Note that, due to bizarre alien technology, a door may even lead from a room back to itself.) Furthermore, no two doors share the same ordered pair of start and end rooms.

Bessie also possesses a remote control with buttons numbered from \(1\) to \(K\) (\(1\le K\le 60\)). To earn her freedom, she must complete a strange task. The aliens will choose two rooms \(s\) and \(t\) (\(1\le s,t\le N\)) and two button numbers \(b_s\) and \(b_t\) (\(1 a\le b_s,b_t\le K\)). Bessie starts in room \(s\) and immediately presses button \(b_s\).

Then, in every room, after having pressed exactly one button, she must either choose one of the available doors to leave for another room (the door may lead to the same room) or stop her actions. However, her button presses must obey the following rule:

• Once Bessie presses a button with number \(x\), that button becomes illegal to press again until she presses a button with a larger number; in other words, repeating the same button consecutively is forbidden unless a button with a greater number is pressed in between.

Bessie will be set free only if, when she stops, she is in room \(t\) and her last pressed button is \(b_t\> (and she has never pressed an illegal button).

Your task is: for each query (each providing values of \(s, t, b_s, b_t\)), compute the number of distinct sequences of room transitions and button presses that lead to Bessie's release. Since the answer could be very large, output it modulo \(10^9+7\).

The input starts with the spaceship configuration followed by the queries. The spaceship configuration is given as follows:

N M K Q
u1 v1
...
 uM vM

Each of the next \(Q\) lines contains four integers \(s, t, b_s, b_t\> representing a query.

inputFormat

The first line contains four integers \(N, M, K, Q\) separated by spaces, where \(N\) is the number of rooms, \(M\) is the number of doors, \(K\) is the number of buttons, and \(Q\) is the number of queries.

The following \(M\) lines each contain two integers \(u\) and \(v\) indicating that there is a one‐way door from room \(u\) to room \(v\>.

Each of the next \(Q\) lines contains four integers \(s, t, b_s, b_t\> representing a query.

outputFormat

For each query, output a single line containing the number of valid sequences modulo \(10^9+7\>.

sample

3 3 3 1
1 2
2 3
1 3
1 3 1 2

2