题目描述

作为パ研合宿的组织负责人，$E869120$ 先生拥有一个由 $N$ 个顶点和 $M$ 条边组成的连通无向图。在这个图中，第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。

今天是 $12$ 月 $24$ 日，正是圣诞节前夕。因此，他计划给这个图染色，并将其作为礼物送给パ研部长 $reiji1112$。不过，为了美观，直接相连的两个顶点不能涂成相同的颜色。

共准备了 $K$ 种颜色，分别标记为 $1, 2, 3, \ldots, K$。你需要计算有多少种不同的染色方案。最后，请输出方案数对 $1\ 000\ 000\ 007$ 取模的结果。

输入格式

输入通过标准输入给出：

$N$ $M$ $K$ $a_1$ $b_1$ $a_2$ $b_2$ $a_3$ $b_3$ ... $a_M$ $b_M$

输出格式

请输出符合条件的染色方案数，并对 $1\ 000\ 000\ 007$ 取模。

数据范围

• $1 \leq N \leq 100,000$
• $1 \leq M \leq 100,003$
• $M - N \leq 3$
• $1 \leq K \leq 1,000,000,000$
• $1 \leq a_i, b_i \leq N$
• $a_i < b_i$（$1 \leq i \leq M$）
• $(a_i, b_i) \neq (a_j, b_j)$ 当 $i \neq j$ 时

附加任务

任务 1 [4 分]
输入限制：

• $N \leq 8$
• $K \leq 2$

任务 2 [13 分]

• $N \leq 8$

任务 3 [8 分]

• 满足 $M - N = -1$ 且 $a_i = i, b_i = i + 1$（$1 \leq i \leq M$）

任务 4 [13 分]

• 满足 $M - N \leq -1$

任务 5 [13 分]

• 满足 $M - N \leq 0$

任务 6 [13 分]

• 满足 $M - N \leq 1$

任务 7 [13 分]

• 满足 $M - N \leq 2$

任务 8 [23 分]

• 没有额外限制

示例解释

第一种示例中，有以下两种符合条件的染色方案：

第二种示例不符合任务 1 的限制条件，但满足任务 2 到任务 8 的限制条件。

在第五种示例中，请确保输出的结果是对 $1\ 000\ 000\ 007$ 取模的值。

输入输出样例 #1

输入 #1

3 2 2
1 2
2 3

输出 #1

2

输入输出样例 #2

输入 #2

3 2 5
1 2
2 3

输出 #2

80

输入输出样例 #3

输入 #3

4 3 1
1 2
2 3
2 4

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

972

输入输出样例 #5

输入 #5

10 10 100
1 2
1 3
2 4
2 5
2 6
2 7
3 8
5 9
9 10
4 8

输出 #5

332858118