P16359 [BalticOI 2026] Tourist's Journey

一个国家有 $n$ 个城市，编号为 $1,2,\dots,n$，由 $m$ 条双向道路连接。道路的数量最多比城市的数量多 $10$，但任意两个城市之间仍然可以通过一条或多条道路互相到达。 一位旅行者正在计划在该国旅行。他/她已经决定好以下几点： - 旅行将从城市 $1$ 出发，在城市 $n$ 结束。 - 旅行应恰好由 $k$ 步组成，每一步沿着一条道路行进。 - 不允许在连续两步中在同一条路上往返。不过，如果中间有其他步，则可以多次经过同一条路。 从城市 $1$ 出发，恰好经过 $k$ 步到达城市 $n$ 的旅行计划有多少种？如果在任意一步到达的城市不同，则认为两个计划不同。

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示国家的城市数、道路数以及旅行者旅行所需的步数。 接下来的 $m$ 行描述所有道路。每行包含两个不同的整数 $u$ 和 $v$，表示城市 $u$ 和城市 $v$ 之间有一条道路。两个城市之间最多有一条道路。

输出不同旅行计划的数量。由于答案可能很大，请输出其对 $10^9+7$ 取模的结果。

### 解释 1 该国的城市与道路如下图所示。 :::align{center}  ::: 可能的旅行计划有： - $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ - $1 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$ - $1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 4$ - $1 \rightarrow 3 \rightarrow 4 \rightarrow 2 \rightarrow 3 \rightarrow 4$ ### 解释 2 不存在任何恰好 $4$ 步的有效旅行计划。注意计划 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$ 是无效的，因为它在连续两步中使用了连接城市 $2$ 和 $3$ 的道路。 ### 数据范围 - $2 \le n \le 2 \cdot 10^5$ - $n-1 \le m \le n + 10$ - $1 \le k \le 10^4$ ### 子任务 | 子任务 | 约束条件 | 分值 | | :---: | --- | :---: | | 1 | $n,k \le 10$ | $7$ | | 2 | $n,k \le 100$ | $8$ | | 3 | $m=n-1$ | $11$ | | 4 | $m=n-1$ 或 $m=n$ | $29$ | | 5 | $n \le 1000$ | $15$ | | 6 | 无额外限制 | $30$ | 翻译由 DeepSeek V4 Pro 完成