给定一张 $n$ 个点 $m$ 条边的无向图 $G = (V, E)$ 与常数 $c$。定义一个边集的子集 $S \subseteq E$ 的权值 $f(S)$ 如下：

• 如果存在两条边 $e_1, e_2 \in S$ 满足其交于一个公共的顶点，那么 $f(S) = 0$。
• 否则，$f(S) = c^{|S|}$。

即当 $S$ 为 $G$ 的一个匹配时，$f(S) = c^{|S|}$，否则 $f(S) = 0$。

现在你需要求：

$$g(G) = \sum_{S \subseteq E} f(S)$$

由于答案可能很大，因此你只需要输出它对 $10^9+7$ 取模后的结果即可。

输入格式

输入的第一行包含三个整数 $n, m, c$。

接下来 $m$ 行，每行两个整数 $u, v$，描述一条边。

输出格式

输出一行一个整数，表示答案。

样例数据

样例 1 输入

3 3 3
1 2
1 3
2 3

样例 1 输出

10

样例 2 输入

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

样例 2 输出

449

样例 3 输入

30 15 6
1 2
1 3
1 4
2 3
2 4
3 4
5 6
7 8
9 10
11 12
13 14
15 16
16 17
17 18
19 20

样例 3 输出

938250775

样例 4

见下发文件。

子任务

请注意，本题满分为 200 分。

对于所有数据，$1\le n\le 40$，$0 \le m \le \binom{n}{2}$，$0 \le c < 10^9+7$，保证图中没有重边与自环。

• 性质 A：保证 $m = \binom{n}{2}$。
• 性质 B：保证 $m \ge \binom{n}{2} - 10$。

提示：本题的时间限制较为严格，请在实现时注意常数问题。你可以使用【自定义测试】来测试你的程序在评测系统中的运行效率。

Hack

Hack 功能在本题中可用。