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 space-separated integers n = |V|, m = |E| and k.
Then m lines follow, each line contains two space-separated 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

----- Sample Input 1 ------ 
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
----- Sample Output 1 ------ 
6

56

194
----- explanation 1 ------ 
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 * 12 + 2 * 22 + 2 * 32 + 52 = 56.

Difficulty: VERY_HARD
Tags: Bit manipulation

Graph algorithms

Square root algorithms

Combinatorics

Mathematics

Data structures
Skill types: Bit manipulation

Data structures

Starter code:

Solutions:
MOD = 10 ** 9 + 7

def pow2(n):
	return 0 if n < 0 else pow(2, n, MOD)

def setB():
	global B
	gs = [set(g_u) for g_u in g]
	es = set(e)
	B = [0] * (n + 1)
	lim = m ** 0.5
	for u in range(1, n + 1):
		if deg[u] < lim:
			for v in g[u]:
				for w in g[u]:
					if (v, w) in es:
						B[u] += 1
		else:
			for (v, w) in e:
				if v in gs[u] and w in gs[u]:
					B[u] += 1

def solve3():
	(a23, a24) = solve2(get_a23_a24=True)
	setB()
	tri = sum(B)
	claw = sum((deg_u * (deg_u - 1) * (deg_u - 2) for deg_u in deg))
	P4 = 3 * sum(((deg[u] - 1) * (deg[v] - 1) for (u, v) in e)) - 3 * tri
	a32 = m
	a33 = 3 * a23 + tri
	a34 = 3 * a24 + claw + P4
	a35 = 3 * sum((deg[u] * (deg[u] - 1) * (m - deg[u] + 2) + B[u] - 2 * (deg[u] - 1) * sum((deg[v] for v in g[u])) for u in range(1, n + 1)))
	a36 = m * m * m - a32 - a33 - a34 - a35
	return (a32 * pow2(n - 2) + a33 * pow2(n - 3) + a34 * pow2(n - 4) + a35 * pow2(n - 5) + a36 * pow2(n - 6)) % MOD

def solve2(get_a23_a24=False):
	a22 = m
	a23 = sum((deg_u * (deg_u - 1) for deg_u in deg))
	a24 = m * m - a22 - a23
	if get_a23_a24:
		return (a23, a24)
	return (a22 * pow2(n - 2) + a23 * pow2(n - 3) + a24 * pow2(n - 4)) % MOD

def solve1():
	return m * pow2(n - 2) % MOD
T = int(input())
for t in range(T):
	(n, m, k) = map(int, input().split())
	e = []
	g = [[] for i in range(n + 1)]
	for i in range(m):
		(u, v) = map(int, input().split())
		e.append((u, v))
		e.append((v, u))
		g[u].append(v)
		g[v].append(u)
	deg = [len(g_u) for g_u in g]
	ans = solve1() if k == 1 else solve2() if k == 2 else solve3()
	print(ans)


import sys
MOD = 10 ** 9 + 7

def trivial(edge, N, K):
	total = 2 ** N
	situation = []
	for i in range(1, total):
		s = bin(i)[2:]
		if len(s) < N:
			s = '0' * (N - len(s)) + s
		s = '0' + s[::-1]
		situation += [s]
	ans = 0
	for i in range(len(situation)):
		s = situation[i]
		temp = []
		for j in range(len(s)):
			if s[j] != '0':
				temp += [j]
		value = 0
		for ii in range(len(temp)):
			for jj in range(ii + 1, len(temp)):
				aa = temp[ii]
				bb = temp[jj]
				if (aa, bb) in edge or (bb, aa) in edge:
					value += 1
		ans += value ** K
		ans %= MOD
	return ans

def ONE(edge, N):
	if N == 1:
		return 0
	return pow(2, N - 2, MOD) * len(edge) % MOD

def TWO(graph, edge, N, M):
	MOD = 10 ** 9 + 7
	degree = {}
	for i in range(1, N + 1):
		degree[i] = len(graph[i])
	temp = 0
	for X in edge:
		(a, b) = X
		temp += degree[a] + degree[b]
		temp %= MOD
	sum1 = M
	sum2 = (temp - 2 * M) * pow(2, MOD - 2, MOD) % MOD
	sum3 = (M * (M + 1) - temp) % MOD * pow(2, MOD - 2, MOD) % MOD
	ans = (pow(2, N - 2, MOD) * (sum2 + sum1) % MOD + pow(2, N - 3, MOD) * sum3 % MOD) % MOD
	return ans

def THREE(graph, edge, N, M):
	MOD = 10 ** 9 + 7
	degree = {}
	GRAPH = {}
	for i in range(1, N + 1):
		degree[i] = len(graph[i])
		GRAPH[i] = set(graph[i])
	temp = 0
	for X in edge:
		(a, b) = X
		temp += degree[a] + degree[b]
		temp %= MOD
	sum1 = M
	sum2 = (temp - 2 * M) * pow(2, MOD - 2, MOD) % MOD
	sum3 = (M * (M + 1) - temp) % MOD * pow(2, MOD - 2, MOD) % MOD
	total = 0
	tri = 0
	for X in edge:
		(a, b) = X
		if degree[a] >= 2 and degree[b] >= 2:
			total += (degree[a] - 1) * (degree[b] - 1)
			tri += len(GRAPH[a] & GRAPH[b])
			tri %= MOD
			total %= MOD
	tri *= pow(3, MOD - 2, MOD)
	tri %= MOD
	need = (tri + total) % MOD
	number1 = sum2 * (M - 2) % MOD
	number2 = M * (M - 1) * (M - 2) // 6 % MOD
	ans11 = 3 * (number1 + number2 + need) % MOD % MOD
	ans11 += M * 8 + (12 * sum2 + 6 * sum3) * 2
	ans11 %= MOD
	return ans11 * pow(2, N - 5, MOD) % MOD
ANS = []
for _ in range(int(input())):
	(N, M, K) = list(map(int, sys.stdin.readline().strip().split(' ')))
	edge = set()
	graph = {}
	for i in range(1, N + 1):
		graph[i] = []
	for ii in range(M):
		(x, y) = list(map(int, sys.stdin.readline().strip().split(' ')))
		graph[x] += [y]
		graph[y] += [x]
		edge.add((x, y))
	if N < 16:
		ANS += [trivial(edge, N, K)]
	elif K == 1:
		ANS += [ONE(edge, N)]
	elif K == 2:
		ANS += [TWO(graph, edge, N, M)]
	else:
		ANS += [THREE(graph, edge, N, M)]
print('\n'.join(list(map(str, ANS))))