#5714. 「BalticOI 2026」游客的旅程

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 BalticOI 2026 Day1「Tourist's Journey」

一个国家有 $n$ 个城市，编号为 $1, 2, \ldots, n$，它们由 $m$ 条双向道路连接。道路数量比城市数量最多多出 $10$ 条，且保证任意两个城市之间都可以通过一条或多条道路到达。

一位游客正在规划一次国内旅行，他们决定：

• 行程从城市 $1$ 出发，在城市 $n$ 结束。
• 行程包含恰好 $k$ 步，每一步经过一条道路。
• 在连续的两步中，不允许沿着同一条道路往返。然而，如果中间有其他步骤，则可以多次经过同一条道路。

从城市 $1$ 到城市 $n$ 且包含 $k$ 步的行程方案共有多少种？如果两个方案在任意一步经过的城市不同，则视为不同的方案。

输入格式

第一行包含三个整数 $n, m$ 和 $k$，分别表示国家的城市数量、道路数量以及行程的步数。

接下来的 $m$ 行描述了道路。每行包含两个不同的整数 $u$ 和 $v$，表示城市 $u$ 和城市 $v$ 之间有一条道路。任意两个城市之间最多只有一条道路。

输出格式

输出不同行程方案的数量。由于答案可能很大，请对 $10^{9}+7$ 取模。

样例 1

输入

4 5 5
1 2
1 3
2 3
2 4
3 4

输出

4

下图展示了该国的城市和道路。

可能的行程方案为：

• $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 3 4
1 2
2 3
2 4

输出

0

没有任何合法的 $4$ 步行程方案。注意，方案 $1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$ 是非法的，因为它在连续的两步中使用了连接城市 $2$ 和城市 $3$ 的同一条道路。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq n \leq 2 \cdot 10^{5}$
• $n-1 \leq m \leq n+10$
• $1 \leq k \leq 10^{4}$

详细子任务附加限制及分值如下表所示。