Public Judge

pjudge

Time Limit: 8 s Memory Limit: 512 MB Total points: 200
Statistics

给定一张 $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 功能在本题中可用。