Let $n$ be a fixed integer. 

A permutation is a bijection from the set $\{1,2,\ldots,n\}$ to itself. 

A cycle of length ${k}$ ($k\geq2$) is a permutation $\mbox{f}$ where different integers exist $i_1,\ldots,i_k$ such that $f(i_1)=i_2,f(i_2)=i_3,...,f(i_k)=i_1$ and, for all $\boldsymbol{x}$ not in $\{i_1,\ldots,i_k\}$, $f(x)=x$.

The composition of $m$ permutations $f_1,\ldots,f_m$, written $f_1\circ f_2\circ\ldots\circ f_m$, is their composition as functions.

Steve has some cycles $f_1,f_2,\ldots,f_m$. He knows the length of cycle $f_i$ is $\mathbf{l}_i$, but he does not know exactly what the cycles are.
He finds that the composition $f_1\circ f_2\circ\ldots\circ f_m$ of the cycles is a cycle of length $n$. 

He wants to know how many possibilities of $f_1,\ldots,f_m$ exist.

Input Format

The first line contains ${T}$, the number of test cases. 

Each test case contains the following information:

The first line of each test case contains two space separated integers, $n$ and $m$.

The second line of each test case contains $m$ integers, $l_1,\ldots,l_m$.

Constraints 

$n\geq2$ 

Sum of $n\leqslant1000$ 

$2\leq l_i\leq n$ 

Sum of $m\leq10^{6}$  

Output Format

Output ${T}$ lines. Each line contains a single integer, the answer to the corresponding test case.

Since the answers may be very large, output them modulo $(10^9+7)$.

Sample Input
1
3 2
2 2

Sample Output
6

Explanation

There are three cycles of length $2$. The composition of two cycles of length $2$ is a cycle of length $3$ if, and only if, the two cycles are different. So, there are $3\cdot2=6$ possibilities.

Source: hackerrank | Difficulty: HARD
Tags: Combinatorics


Solutions:
n = int(input())
i = 0
while i < n:
	(a, b) = map(int, input().strip().split(' '))
	x = list(input().strip().split(' '))
	print(a * b % (10 ** 9 + 7))
	i += 1


print(6)


T = int(input())
MOD = 1000000007
for t in range(T):
	(n, m) = tuple(map(int, input().split()))
	l = set(map(int, input().split()))
	ret = 1
	for k in range(1, n + 1):
		if k not in l:
			ret = ret * k % MOD
	for k in range(1, m + 1):
		ret = ret * k % MOD
	print(ret)