Main Campus Walk 3

The information science building of Soongsil University sits across the road from the rest of the campus. Computer science students therefore call the campus the main side and the information science building the info side. Junyoung is a computer science student, so he stays shut in the info side and envies the main side, where the flowers are in full bloom. One day he decides to take a walk on the main side.

The campus map has $n$ buildings and $m$ roads, and each road joins two adjacent buildings. Walking one road to the adjacent building takes 1 minute. Junyoung never stops on a road or inside a building during the walk. Every minute he crosses exactly one road and moves to another building.

Junyoung has a lot to do, so he walks for exactly $D$ minutes. At the moment $D$ minutes have passed he must be at the info side. The info side is building 1, and Junyoung is at the info side at minute 0. Count the possible routes. He may pass through the same building and the same road more than once, and two routes that visit buildings in a different order count as different routes.

The first line contains the number of buildings $n$ and the number of roads $m$. ($1 \le n \le 50$, $0 \le m \le 1000$)

Each of the next $m$ lines contains two building numbers $a$ and $b$ joined by a road. ($1 \le a, b \le n$, $a \ne b$) A road between the same pair of buildings is given only once.

The last line contains the walking time $D$ in minutes. ($1 \le D \le 10^9$)

Print the number of possible routes modulo $1000000007$.