Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sereja has an undirected graph on N vertices. There are edges between all but M pairs of vertices.

A permutation p on the vertices of the graph is represented as p[1], p[2], … , p[N] such that for all i, p[i] is a vertex of the graph. A permutation is called connected if there is an edge between vertices p[i] and p[i+1] for all natural numbers i less than N. Sereja wants to know the number of connected permutations on the graph vertices.

------ Input ------ 

First line of input contains a single integer T, denoting the number of test cases. T tests follow. First line of each test case contains two integers, N and M. M lines follow, each containing a pair of indices of vertices, indicating that those vertices are not connected by an edge.

------ Output ------ 

For each test case, output one number — the answer for the problem modulo 10^{9}+7.

------ Constraints ------ 

$1 ≤ T ≤  10 $
$1 ≤ N ≤  10^{5}$
$0 ≤ M ≤  7 $

------ Subtasks ------ 

$Subtask #1:  1 ≤ N ≤  10  (25 points) $
$Subtask #2:  1 ≤ N ≤  100  (25 points) $
$Subtask #3:  1 ≤ N ≤  1000  (25 points) $
$Subtask #4:   original  (25 points) $

----- Sample Input 1 ------ 
2
4 3
1 2
2 3
3 4
2 1
1 2
----- Sample Output 1 ------ 
2
0

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Combinatorics

Mathematics
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
from collections import defaultdict
MOD = 1000000007
MX = 100010
(fact, inv_fact) = ([1] * MX, [1] * MX)
for i in range(2, MX):
	fact[i] = fact[i - 1] * i % MOD
inv_fact[MX - 1] = 549915853
for i in range(MX - 2, -1, -1):
	inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD

def ncr(n, r):
	if n < r:
		return 0
	return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 0:
		print(fact[n] % MOD)
		continue
	faulty_nodes = []
	discon = defaultdict(lambda : 0)
	for i in range(m):
		(u, v) = map(int, input().split())
		discon[u, v] = 1
		discon[v, u] = 1
		if u not in faulty_nodes:
			faulty_nodes.append(u)
		if v not in faulty_nodes:
			faulty_nodes.append(v)
	k = len(faulty_nodes)
	normal_nodes = n - k
	normal_nodes_combinations = fact[normal_nodes]
	ans = 0
	dp = [[[0] * (k + 1) for _ in range(k + 1)] for _ in range(1 << k + 1)]
	for i in range(k):
		dp[1 << i][i][0] = 1
	for mask in range(1, 1 << k):
		for first_node in range(k):
			for number_tied in range(k):
				if dp[mask][first_node][number_tied] > 0:
					for new_first in range(k):
						if mask >> new_first & 1 == 0:
							new_mask = mask ^ 1 << new_first
							edge_missing = discon[faulty_nodes[first_node], faulty_nodes[new_first]]
							dp[new_mask][new_first][number_tied + edge_missing] += dp[mask][first_node][number_tied]
				if mask == (1 << k) - 1:
					get_ways = ncr(n - number_tied, k) * dp[mask][first_node][number_tied] * normal_nodes_combinations % MOD
					ans = (ans + get_ways) % MOD
	print(ans)


from math import factorial
roots = [i for i in range(100010)]
MOD = 10 ** 9 + 7
factorials = [1] * 100010
for i in range(2, 100010):
	factorials[i] = i * factorials[i - 1] % MOD

def nPr(n, r, MOD):
	res = 1
	for i in range(n - r + 1, n + 1):
		res = res * i % MOD
	return res

def root(x):
	while x != roots[x]:
		x = roots[x]
	return x

def unite(x, y):
	(p, q) = (root(x), root(y))
	roots[p] = q

def find(x, y):
	return roots[x] == roots[y]

def subset(i, s):
	if i == len(arr):
		subsets.append(s)
		return
	subset(i + 1, s)
	temp = s[:] + [arr[i]]
	subset(i + 1, temp)

def solve(v, ans):
	nodes = set()
	r = dict()
	q = dict()
	for (x, y) in v:
		nodes.add(x)
		nodes.add(y)
		unite(x, y)
	for node in nodes:
		a = root(node)
		if a in q:
			q[a].append(node)
		else:
			q[a] = [node]
		if a in r:
			r[a] += 1
		else:
			r[a] = 1
	for node in nodes:
		roots[node] = node
	for temp_arr in q.values():
		d = dict()
		(c1, c2) = (0, 0)
		for (x, y) in v:
			if x in temp_arr:
				if x in d:
					d[x] += 1
				else:
					d[x] = 1
				if y in d:
					d[y] += 1
				else:
					d[y] = 1
		for value in d.values():
			if value == 1:
				c1 += 1
			elif value == 2:
				c2 += 1
			else:
				return ans
		if c1 < 2:
			return ans
	p1 = len(r)
	p2 = n - sum([value - 1 for value in r.values()])
	q = nPr(p2, p1, MOD) * (1 << p1) * factorials[p2 - p1]
	if len(v) % 2 == 0:
		ans += q
	else:
		ans -= q
	return ans % (10 ** 9 + 7)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(m):
		(x, y) = map(int, input().split())
		if x < y:
			arr.append((x, y))
		else:
			arr.append((y, x))
	arr = list(set(arr))
	arr.sort()
	subsets = []
	subset(0, [])
	subsets.sort()
	ans = factorials[n]
	for v in subsets:
		if len(v):
			ans = solve(v, ans)
	print(ans % (10 ** 9 + 7))