AT_pakencamp_2018_day2_g グランド・グラフ　(Grand Graph)

作为パ研合宿的组织负责人，$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 分] - 没有额外限制 ### 示例解释 第一种示例中，有以下两种符合条件的染色方案： !\[ \](https://img.atcoder.jp/pakencamp-2018-day2/e503bad686eebb742a89614dee847d14.png) 第二种示例不符合任务 1 的限制条件，但满足任务 2 到任务 8 的限制条件。 在第五种示例中，请确保输出的结果是对 $1\ 000\ 000\ 007$ 取模的值。 **本翻译由 AI 自动生成**

### 制約 - $ N $ は $ 1 $ 以上 $ 100\ 000 $ 以下の整数 - $ M $ は $ 1 $ 以上 $ 100\ 003 $ 以下の整数 - $ M\ -\ N $ **は** $ 3 $ **以下である。** - $ K $ は $ 1 $ 以上 $ 1\ 000\ 000\ 000 $ 以下の整数 - $ a_i,\ b_i $ は $ 1 $ 以上 $ N $ 以下の整数 - $ a_i\