Problem 697: legat

Lensu was challenged by Buzdi and Cosmin to play a game called "Legat". This game takes place in a palace with $N$ rooms, numbered from 1 to $N$ , connected by $M$ one-way doors, such that you cannot return to a room you've already visited during the game. This game consists of $N$ rounds, which proceed as follows:

In round i, Lensu will be placed in a starting room different from those in the previous i - 1 rounds and will be blindfolded.
He can pass through at most $L$ doors.
During the game, Lensu can say "STOP", at which point, if he is in room $N$ , he wins and the game ends. If he is not in room $N$ , he will proceed to the next round.

If Lensu does not win after $N$ rounds, he loses the game.

Task

Lensu wants to place a bet with Buzdi and Cosmin. To know how much to bet, he wants to determine the probability of winning the game.

Input data

The first line contains the natural numbers $N$ , $M$ , and $L$ . The next $M$ lines each contain two natural numbers x y, separated by a space, indicating that there is a door leading from room x to room y.

Output data

Print a single natural number $P$ , representing the probability that Lensu wins the game. This number will be printed modulo $1,000,000,007$ .

Constraints and clarifications

$2 \leq N \leq 100,000$
$1 \leq M \leq 500,000$
$1 \leq L \leq 100$
$P = \frac{number of favorable cases}{number of possible cases}$
Probability $P$ is a fraction $\frac{a}{b}$ expressed as $a \times b^{-1}$ , where $b^{-1}$ is the modular inverse of $b$ modulo $1,000,000,007$ .
Lensu does not necessarily play optimally; he only knows how many doors he has opened.
For 21 points, $2 \leq N \leq 100, 1 \leq M \leq 200$

Example

stdin

stdout

305555558

Explanation

There are 11 scenarios where he reaches room 8 and says "STOP" by passing through at most 3 doors. In each scenario, he will pass in order through the rooms:

$(8)$
$(2, 8)$
$(3, 8)$
$(1, 3, 8)$
$(6, 2, 8)$
$(4, 2, 8)$
$(2, 3, 8)$
$(6, 2, 3, 8)$
$(4, 2, 3, 8)$
$(7, 4, 2, 8)$
$(1, 6, 2, 8)$

The total number of scenarios in which he passes through at most 3 doors and says "STOP" in one of the rooms is 36. Thus, the probability that Lensu wins is $\frac{11}{36}$ , and $\frac{11}{36}$ modulo $1,000,000,007$ = $305555558$ .

legat