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

一位游客正在计划在该国进行一次旅行。他们决定了以下事项： 旅行将从城市 $1$ 开始，并在城市 $n$ 结束。 旅行应恰好包含 $k$ 个步骤，每一步经过一条道路。 * 不允许在连续的两个步骤中沿同一条道路往返。然而，如果中间有其他步骤，则可以多次经过同一条道路。

从城市 $1$ 到城市 $n$ 进行 $k$ 步的旅行计划有多少种？如果两个计划在任何步骤经过的城市不同，则它们是不同的。

输入格式

第一行包含三个整数 $n, m$ 和 $k$：国家的城市数量和道路数量，以及游客旅行的步数。

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

输出格式

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

数据范围

• $2 \le n \le 2 \cdot 10^5$
• $n - 1 \le m \le n + 10$
• $1 \le k \le 10^4$

样例

样例输入 1

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

样例输出 1

4

说明 1

该国家的城市和道路如下图所示：

可能的旅行计划有： $1 \to 2 \to 3 \to 1 \to 2 \to 4$ $1 \to 3 \to 2 \to 1 \to 3 \to 4$ $1 \to 2 \to 4 \to 3 \to 2 \to 4$ $1 \to 3 \to 4 \to 2 \to 3 \to 4$

样例输入 2

4 3 4
1 2
2 3
2 4

样例输出 2

0

说明 2

不存在 $4$ 步的有效旅行计划。注意，计划 $1 \to 2 \to 3 \to 2 \to 4$ 是无效的，因为它在连续的两个步骤中使用了城市 $2$ 和城市 $3$ 之间的道路。

子任务