Problem G
Gallivanting Glades

Photo by Matthias Ripp, CC-BY-2.0

Gunter lives in a small village on the outskirts of a magic forest. Every morning, after finishing his chores, he has a little bit of time left before the school bus arrives. Naturally, he likes to use this time to go on walks in the magic forest. Gunter (and the school bus) are very precise, so he always has exactly the same amount of time for his walks. Each morning, he picks a route through the forest that will bring him back to his house at precisely the time the school bus arrives. This makes him wonder—how many different routes through the forest could he take?

The magic forest consists of a number of magic glades connected by magic paths. However, in a magic forest things like “distance” and “time” do not have their usual meanings; each magic path takes exactly one second to traverse in either direction, and going through a magic glade from one path to another takes no time at all. Also, one second inside the magic forest takes one femtosecond in the real world, so Gunter may have quite a lot of time for his walk.

Stopping to rest in the magic forest can be dangerous (Gunter might fall asleep and never wake up), so the only valid routes are ones where Gunter keeps moving constantly. Other than that, there are no restrictions on the routes Gunter can choose. For example, there is nothing wrong with traversing the same glade or path more than once, or with traversing a path and then immediately turning around and traversing it in the opposite direction.

Input

The first line of input contains two space-separated integers $N$ and $P$, where $N$ is the number of magic glades in the forest ($1 \leq N \leq 100$), and $P$ is the number of magic paths ($0 \leq P \leq 10^5$).

Next follow $P$ lines describing the magic paths, where each line contains two space-separated integers giving the endpoints of the path (the glades are numbered from $0$ to $N-1$). Gunter’s house is right next to glade $0$.

Finally, there is a line containing a single integer $T$ specifying the number of seconds in the magic forest Gunter has for his walk ($1 \leq T \leq 10^{18}$).

Output

Output the number of distinct routes through the forest which start and end at glade $0$ and take exactly $T$ seconds for Gunter to traverse. Since this number may be very large, output it modulo $10^9 + 7$.

4 5
0 1
1 2
3 2
0 3
1 0
4

34

4 5
0 1
1 2
3 2
0 3
1 0
5

0

1 1
0 0
1

2