Sum of Cubes

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
You are given an undirected graph G = (V, E). We define a function f(s) for s ⊆ V to be the number of edges in the induced subgraph of s.
The problem asks you to calculate the sum of f(s)^{k} over all s in 2^{V} subsets of V.
As the answer could be very large, output it modulo (10^{9}+7).
Input
The first line of input contains an integer T denoting the number of test cases.
For each test case, the first line contains three spaceseparated integers n = V, m = E and k.
Then m lines follow, each line contains two spaceseparated integers u, v denoting an edge (u, v) is in E.
Output
For each test case, output one line containing one integer, the answer modulo (10^{9}+7).
Constraints
 1 ≤ T ≤ 100
 2 ≤ n ≤ 10^{5}
 0 ≤ m ≤ 10^{5}
 Sum of each of n, m over all test cases ≤ 3 * 10^{5}
 1 ≤ u, v ≤ n.
 1 ≤ k ≤ 3.
 The graph is simple, i.e., doesn't contain self loops and multiple edges.
Subtasks
 Subtask #1 (8 points): T, n ≤ 15
 Subtask #2 (7 points): k = 1
 Subtask #3 (9 points): k = 2
 Subtask #4 (15 points):
 k = 3.
 Sum of n over all test cases ≤ 300
 Sum of m over all test cases ≤ 300
 Subtask #5 (24 points):
 k = 3.
 Sum of n over all test cases ≤ 3000
 Sum of m over all test cases ≤ 3000
 Subtask #6 (37 points): Original Constraints
Example
Input: 3 3 3 1 1 2 2 3 3 1 4 5 2 1 2 2 3 3 4 4 1 2 4 5 4 3 1 2 1 3 1 4 2 5 Output: 6 56 194
Explanation
Example case 1.
f(emptyset) = f({1}) = f({2}) = f({3}) = 0;
f({1, 2}) = f({2, 3}) = f({3, 1}) = 1
f({1, 2, 3}) = 3.
So the answer is 1 + 1 + 1 + 3 = 6.
Example case 2.
The nonzero f's are as follows
f({1, 2}) = f({2, 3}) = f({3, 4}) = f({4, 1}) = f({2, 4}) = 1
f({1, 2, 3}) = f({1, 3, 4}) = 2
f({1, 2, 4}) = f({2, 3, 4}) = 3
f({1, 2, 3, 4}) = 5
So the answer is 5 * 1^{2} + 2 * 2^{2} + 2 * 3^{2} + 5^{2} = 56.
Author:  r_64 
Tester:  jingbo_adm 
Editorial  https://discuss.codechef.com/problems/SUMCUBE 
Tags  hard, maths, r_64, sept17, sqrtdecomp 
Date Added:  4082017 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions