Description

The people on the planet Jialidun (pinyin) love drinking cola. Therefore, their enemy planet developed a cola robot and placed it in city $1$ of planet Jialidun. This cola robot has three possible actions: stay where it is, go to an adjacent city, or self-destruct. Every second, it randomly triggers one of these actions. Given the city graph of planet Jialidun, and that at time $0$ the cola robot is in city $1$, after $t$ seconds, how many behavior sequences could the cola robot have?

Input Format

The first line contains two positive integers $N$, $M$. $N$ is the number of cities, and $M$ is the number of roads. Then $M$ lines follow, each containing two integers $u$, $v$, indicating there is a road between $u$ and $v$. There is at most one road between any pair of cities, and no road connects a city to itself. The last line contains an integer $t$, the elapsed time.

Output Format

Output the number of behavior sequences of the cola robot. Since the answer can be large, output the result modulo $2017$.

3 2
1 2
2 3
2

8

Hint

Sample Input/Output 1 Explanation

• $1$ -> self-destructs.
• $1$ -> $1$ -> self-destructs.
• $1$ -> $2$ -> self-destructs.
• $1$ -> $1$ -> $1$.
• $1$ -> $1$ -> $2$.
• $1$ -> $2$ -> $1$.
• $1$ -> $2$ -> $2$.
• $1$ -> $2$ -> $3$.

Constraints

• For $20\%$ of the testdata, $t \leq 1000$.
• For $100\%$ of the testdata, $1 < t \leq 10^6$, $1 \leq N \leq 30$, $0 < M < 100$, $1 \leq u, v \leq N$.

Translated by ChatGPT 5