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