在阅读了论文《Counting Perfect Matchings as Fast as Ryser》之后，你学会了如何以 $O(2^n n^2)$ 的时间复杂度计算一般图中的完美匹配数量。因此，你决定编写这道题目，以鼓励大家阅读这篇论文并学习新技术。

给定一个包含 $n$ 个顶点和 $m$ 条边的无向图，以及一个常数 $c$。我们定义边集 $S$ 的权重如下：

• 如果集合 $S$ 中有两条边共享公共顶点，则权重为 0。
• 否则，权重为 $c^{|S|}$。注意，空集的权重为 1。

计算所有边子集的权重之和。答案可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含三个整数 $n, m, c$ ($1 \le n \le 36, 0 \le m \le \frac{n(n-1)}{2}, 1 \le c \le 10^9 + 6$)。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示图中的一条无向边 $(u, v)$。所有边均不相同。

输出格式

输出一个整数：答案。

样例

输入 1

6 10 100
3 6
1 3
2 4
3 4
4 6
1 2
4 5
2 3
1 4
3 5

输出 1

2171001

输入 2

8 11 818466928
6 7
3 6
6 5
7 3
6 2
8 1
1 7
4 3
5 1
6 1
6 4

输出 2

425176360