Description

People on the planet Gariton especially like drinking cola. Therefore, their enemy planet developed a cola robot and placed it in City $1$ on Gariton. This cola robot has three kinds of actions: stay where it is, go to the next adjacent city, and self-destruct. Every second it randomly triggers one action. Now you are given the city graph of Gariton. At time $0$, the cola robot is in City $1$. After $t$ seconds, how many possible action plans does the cola robot have?

Input Format

The first line contains two positive integers $N, M$, where $N$ is the number of cities and $M$ is the number of roads.

The next $M$ lines each contain $u, v$, meaning there is a bidirectional road between $u$ and $v$.

Finally, input the time $t$.

Output Format

Output the number of possible action plans of the cola robot. The answer may be very large, so output the result modulo $2017$.

3 2
1 2
2 3
2

8

Hint

Constraints

For $20\%$ of the data, $n, m \leq 30$, $t \leq 1000$.

For $50\%$ of the data, $t \leq 10^6$.

For $100\%$ of the data, $n, m \leq 100$, $t \leq 10^9$.

Sample Explanation

$1$ $\rightarrow$ explode.

$1$ $\rightarrow$ $1$ $\rightarrow$ explode.

$1$ $\rightarrow$ $2$ $\rightarrow$ explode.

$1$ $\rightarrow$ $1$ $\rightarrow$ $1$.

$1$ $\rightarrow$ $1$ $\rightarrow$ $2$.

$1$ $\rightarrow$ $2$ $\rightarrow$ $1$.

$1$ $\rightarrow$ $2$ $\rightarrow$ $2$.

$1$ $\rightarrow$ $2$ $\rightarrow$ $3$.

Translated by ChatGPT 5