시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 53 | 18 | 17 | 41.463% |
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(2nn2). 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:
Compute the sum of the weight of all subsets of edges. The answer can be large, so output it modulo 109 + 7.
The first line contains three integers n, m, c (1 ≤ n ≤ 36, 0 ≤ m ≤ n(n−1)/2, 1 ≤ c ≤ 109 + 6).
Each line of the following m lines contains two integers u, v (1 ≤ u, v ≤ n, u ≠ v) indicating an undirected edge (u, v) in the graph. All edges are distinct.
Output one integer: the answer.
6 10 100 3 6 1 3 2 4 3 4 4 6 1 2 4 5 2 3 1 4 3 5
2171001
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
425176360