Ryser만큼 빠르게

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 n(n-1)/2$, $1 \le c \le 10^9+6$). 이어지는 $m$개의 줄에는 무방향 간선 $(u, v)$를 나타내는 정수 $u$, $v$가 한 줄에 하나씩 주어진다 ($1 \le u, v \le n$, $u \ne v$). 모든 간선은 서로 다르다.

답을 나타내는 정수 하나를 출력한다.