P3758 [TJOI2017] Cola

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?

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 the number of behavior sequences of the cola robot. Since the answer can be large, output the result modulo $2017$.

#### 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