题目描述

一个国家有 $n$ 个城市，编号为 $1,2,\dots,n$，由 $m$ 条双向道路连接。道路的数量最多比城市的数量多 $10$，但任意两个城市之间仍然可以通过一条或多条道路互相到达。

一位旅行者正在计划在该国旅行。他/她已经决定好以下几点：

• 旅行将从城市 $1$ 出发，在城市 $n$ 结束。
• 旅行应恰好由 $k$ 步组成，每一步沿着一条道路行进。
• 不允许在连续两步中在同一条路上往返。不过，如果中间有其他步，则可以多次经过同一条路。

从城市 $1$ 出发，恰好经过 $k$ 步到达城市 $n$ 的旅行计划有多少种？如果在任意一步到达的城市不同，则认为两个计划不同。

输入格式

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

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

输出格式

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

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

4

4 3 4
1 2
2 3
2 4

0

提示

解释 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$

子任务

翻译由 DeepSeek V4 Pro 完成