给定一张 $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
见下发文件。
子任务
请注意，本题满分为 7 分。
对于所有数据，$1\le n\le 40$，$0 \le m \le \binom{n}{2}$，$0 \le c < 10^9+7$，保证图中没有重边与自环。
| 子任务编号 | $n \le$ | 特殊性质 | 分值 |
|---|---|---|---|
| $1$ | $28$ | 无 | $1$ |
| $2$ | $34$ | $1$ | |
| $3$ | $40$ | A | $1$ |
| $4$ | B | $1$ | |
| $5$ | 无 | $3$ |
- 性质 A：保证 $m = \binom{n}{2}$。
- 性质 B：保证 $m \ge \binom{n}{2} - 10$。
提示：本题的时间限制较为严格，请在实现时注意常数问题。你可以使用【自定义测试】来测试你的程序在评测系统中的运行效率。
Hack
Hack 功能在本题中可用。