Fast as Ryser

After reading the paper Counting Perfect Matchings as Fast as Ryser, you learned how to count the number of perfect matchings in a general graph in $O(2^n n^2)$. So you decided to write this problem to encourage people to read the paper and learn new technology.

You are given an undirected graph with $n$ vertices and $m$ edges, and also a constant $c$. We define the weight of an edge set $S$ as follows:

• If there are two edges in set $S$ sharing common vertices, the weight is 0.
• Otherwise, the weight is $c^{|S|}$. Note that the weight of an empty set is 1.

Compute the sum of the weight of all subsets of edges. The answer can be large, so output it modulo $10^9 + 7$.

The first line contains three integers $n$, $m$, $c$ ($1 \le n \le 36$, $0 \le m \le n(n-1)/2$, $1 \le c \le 10^9+6$). Each of the following $m$ lines contains two integers $u$, $v$ ($1 \le u, v \le n$, $u \ne v$) indicating an undirected edge $(u, v)$ in the graph. All edges are distinct.

Output one integer: the answer.