P5789 [TJOI2017] Cola (Enhanced Data Version).

The testdata of the [original problem](https://www.luogu.org/problem/P3758) is very weak. This enhanced version eliminates the brute-force DP solution and also adds the missing $\LaTeX$ from the original statement.

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?

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 the number of possible action plans of the cola robot. The answer may be very large, so output the result modulo $2017$.

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