D. Sousse
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The city of Sousse is a popular touristic destination, it has n important locations connected by m directed streets.

A popular tourist activity is to take a "walk" through the city: starting at some location and moving along a sequence of directed streets to reach another location. The length of the walk is the number of streets traversed.

For statistical purposes, the city wants to know the total number of possible walks in the city that use at most L streets. This includes walks between any starting point $$$u$$$ and any ending point $$$v$$$ (including walks of length $$$0$$$, where the tourist stays at the same location).

Since the numbers can be huge, they should be reported modulo $$$M=10^9+7=1000000007$$$.

Given the directed graph of $$$n$$$ locations and $$$m$$$ streets, calculate a single integer: the total number of walks of length between $$$0$$$ and $$$L$$$ (inclusive) over all ordered pairs of locations $$$(u, v)$$$, modulo $$$M$$$.

Input
  • The first line contains three integers $$$1 \le n \le 120$$$, $$$1 \le m \le n^2$$$ and $$$0\le L \le 10^{18},$$$ with
    • $$$n$$$: The number of locations
    • $$$m$$$: The number of streets.
    • $$$L$$$: The maximum length of walk.
  • The next $$$m$$$ lines contain each two integer $$$1 \le u,v \le n,$$$ with $$$u\rightarrow v$$$ a one-way street from $$$u$$$ to $$$v$$$
Output

Print a single integer: the total number of walks of length at most $$$L$$$ over all ordered pairs $$$(u, v)$$$, modulo $$$M=1000000007$$$.

Examples
Input
5 7 100
1 2
1 3
2 3
3 4
1 4
4 5
2 5
Output
22
Input
7 6 1
1 2
1 3
2 4
2 5
3 6
3 7
Output
13
Input
5 5 1000
1 2
2 3
3 4
4 5
5 1
Output
5005
Note
  • The Graph may contain loops
  • It is guaranteed that between any two vertices $$$u$$$ and $$$v$$$, there is at most one edge.