Tara has an array, $\mbox{A}$, consisting of $n$ integers where each integer occurs at most $2$ times in the array. 

Let's define $\mbox{P}$ to be a permutation of $\mbox{A}$ where $p_i$ is the $i^{\mbox{th}}$ element of permutation $\mbox{P}$. Tara thinks a permutation is beautiful if there is no index $\boldsymbol{i}$ such that $p_{i}-p_{i+1}=0$ where $i\in[0,n-1)$.

You are given $\textit{q}$ queries where each query consists of some array $\mbox{A}$. For each $\mbox{A}$, help Tara count the number of possible beautiful permutations of the $n$ integers in $\mbox{A}$ and print the count, modulo $10^9+7$, on a new line.

Note: Two permutations, $\mbox{P}$ and $\mbox{Q}$, are considered to be different if and only if there exists an index $\boldsymbol{i}$ such that $p_i\neq q_i$ and $i\in[0,n)$.

Input Format

The first line contains a single integer, $\textit{q}$, denoting the number of queries. The $2\cdot q$ subsequent lines describe each query in the following form:

The first line contains an integer, $n$, denoting the number of elements in array $\mbox{A}$. 
The second line contains $n$ space-separated integers describing the respective values of $a_0,a_1,\ldots,a_{n-1}$ in array $\mbox{A}$.

Constraints

$1\leq a_i\leq10^9$
Each integer in $\mbox{A}$ can occur at most $2$ times.

For $\textbf{40\%}$ of the maximum score:

$1\leq q\leq100$    
$1\leq n\leq1000$  
The sum of $n$ over all queries does not exceed $\mathbf{10}^4$.  

For $\textbf{100\%}$ of the maximum score:  

$1\leq q\leq100$    
$1\leq n\leq2000$

Output Format

For each query, print the the number of possible beautiful permutations, modulo $10^9+7$, on a new line.

Sample Input 0
3
3
1 1 2
2
1 2
4
1 2 2 1

Sample Output 0
1
2
2

Explanation 0

We perform the following $q=3$ queries:

Array $A=[1,2,1]$ and there is only one good permutation: 

Thus, we print the result of $1\:\text{mod}\:(10^9+7)=1$ on a new line.

Array $A=[1,2]$ and there are two good permutations: 

Thus, we print the result of $2\ \text{mod}\ (10^9+7)=2$ on a new line.

Array $A=[1,2,2,1]$ and there are two good permutations: 

For demonstration purposes, the following two permutations are invalid (i.e., not good): 

Because we only want the number of good permutations, we print the result of $2\ \text{mod}\ (10^9+7)=2$ on a new line.

Difficulty: MEDIUM_HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import sys
sys.setrecursionlimit(5000)
MOD = 1000000007
INV2 = (MOD + 1) // 2
_factorials = {}

def factorial(x):
	if x in {0, 1}:
		return 1
	if x in _factorials:
		return _factorials[x]
	retv = x * factorial(x - 1) % MOD
	_factorials[x] = retv
	return retv
_bin = {}

def binomial(n, k):
	if k == n or k == 0:
		return 1
	if k < 0 or k > n:
		return 0
	if (n, k) in _bin:
		return _bin[n, k]
	retv = (binomial(n - 1, k) + binomial(n - 1, k - 1)) % MOD
	_bin[n, k] = retv
	return retv

def solve(array):
	mults = {}
	for x in array:
		mults[x] = mults.get(x, 0) + 1
	npairs = sum((1 for v in mults.values() if v == 2))
	nsingles = sum((1 for v in mults.values() if v == 1))
	ntot = len(array)
	retv = 0
	twoinvpow = 1
	for i in range(npairs + 1):
		cp = npairs - i
		v = factorial(ntot - cp) * twoinvpow * binomial(npairs, cp)
		twoinvpow = twoinvpow * INV2 % MOD
		retv += v if cp % 2 == 0 else MOD - v
	return retv % MOD
q = int(input())
for _ in range(q):
	n = int(input())
	array = list(map(int, input().split()))
	print(solve(array))


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


from math import factorial
t = int(input())
for t_itr in range(t):
	arr_count = int(input())
	arr = list(map(int, input().rstrip().split()))
	length = len(arr)
	repetitions = length - len(set(arr))
	perm = 0
	for i in range(repetitions + 1):
		perm += (-1) ** i * (factorial(repetitions) // (factorial(i) * factorial(repetitions - i))) * factorial(length - i) // 2 ** (repetitions - i)
	print(perm % (10 ** 9 + 7))


MOD = 10 ** 9 + 7
N = 2010
inv = [1, 1] + [pow(i, MOD - 2, MOD) for i in range(2, N)]
fact = [1] * N
f_inv = [1] * N
for i in range(2, N):
	fact[i] = fact[i - 1] * i % MOD
	f_inv[i] = f_inv[i - 1] * inv[i] % MOD
for _ in range(int(input())):
	n = int(input())
	k = len(set(map(int, input().split())))
	r = n - k
	den = pow(inv[2], r, MOD)
	c = 1
	a = 0
	m = 1
	for i in range(r + 1):
		a += fact[n - i] * den * c * m % MOD
		m = -m
		den = den * 2 % MOD
		c = c * (r - i) * inv[i + 1] % MOD
	print(a % MOD)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


from sys import stdin
mod = 10 ** 9 + 7
C = [[0 for _ in range(i + 1)] for i in range(2001)]
C[0][0] = 1
for i in range(1, 2001):
	C[i][0] = 1
	for j in range(1, i):
		C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
		C[i][j] %= mod
	C[i][i] = 1
P = [1 for _ in range(2001)]
for i in range(1, 2001):
	P[i] = P[i - 1] * i
	P[i] %= mod
A = [1 for _ in range(2001)]
for i in range(1, 2001):
	if A[i - 1] % 2 == 0:
		A[i] = A[i - 1] // 2
	else:
		A[i] = (A[i - 1] + mod) // 2
	A[i] %= mod

def f(n, a):
	a.sort()
	k = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			k += 1
	ans = 0
	for i in range(1, k + 1):
		t = C[k][i] * P[n - i] * A[k - i]
		t %= mod
		if i % 2 == 0:
			ans -= t
		else:
			ans += t
		ans %= mod
	ans = P[n] * A[k] - ans
	ans %= mod
	return ans
q = int(stdin.readline().strip())
for _ in range(q):
	n = int(stdin.readline().strip())
	a = list(map(int, stdin.readline().strip().split()))
	print(f(n, a))


from sys import stdin
mod = 10 ** 9 + 7
C = [[0 for _ in range(i + 1)] for i in range(2001)]
C[0][0] = 1
for i in range(1, 2001):
	C[i][0] = 1
	for j in range(1, i):
		C[i][j] = C[i - 1][j - 1] + C[i - 1][j]
		C[i][j] %= mod
	C[i][i] = 1
P = [1 for _ in range(2001)]
for i in range(1, 2001):
	P[i] = P[i - 1] * i
	P[i] %= mod
A = [1 for _ in range(2001)]
for i in range(1, 2001):
	if A[i - 1] % 2 == 0:
		A[i] = A[i - 1] // 2
	else:
		A[i] = (A[i - 1] + mod) // 2
	A[i] %= mod

def f(n, a):
	a.sort()
	k = 0
	for i in range(1, n):
		if a[i] == a[i - 1]:
			k += 1
	ans = 0
	for i in range(1, k + 1):
		t = C[k][i] * P[n - i] * A[k - i]
		t %= mod
		if i % 2 == 0:
			ans -= t
		else:
			ans += t
		ans %= mod
	ans = P[n] * A[k] - ans
	ans %= mod
	return ans
q = int(stdin.readline().strip())
for _ in range(q):
	n = int(stdin.readline().strip())
	a = list(map(int, stdin.readline().strip().split()))
	print(f(n, a))


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


fact = [1]
for i in range(1, 2001):
	fact.append(fact[-1] * i)
permu = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	permu[i][0] = 1
	for j in range(1, i + 1):
		permu[i][j] = permu[i - 1][j - 1] + permu[i - 1][j]
for _ in range(int(input())):
	num = int(input())
	num1 = len(set(input().split()))
	diff = num - num1
	final = 0
	f = 1
	for j in range(0, diff + 1):
		permu1 = permu[diff][j]
		final += f * permu1 * fact[num - j] // 2 ** (diff - j)
		f = f * -1
	print(final % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


import math
import os
import random
import re
import sys
factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


import math
import os
import random
import re
factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


import math
import os
import random
import re
import sys
factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


import math
import os
import random
import re
import sys
factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


def satfas():
	saiteja = [1]
	for i in range(1, 2001):
		saiteja.append(saiteja[-1] * i)
	ramaya = [[0 for y in range(1001)] for x in range(1001)]
	for i in range(1001):
		ramaya[i][0] = 1
		for j in range(1, i + 1):
			ramaya[i][j] = ramaya[i - 1][j - 1] + ramaya[i - 1][j]
	for l in range(int(input())):
		g = int(input())
		hart = len(set(input().split()))
		camera = g - hart
		abha = 0
		fiujjs = 1
		for j in range(0, camera + 1):
			kCj = ramaya[camera][j]
			abha += fiujjs * kCj * saiteja[g - j] // 2 ** (camera - j)
			fiujjs = fiujjs * -1
		print(abha % 1000000007)
satfas()


factorial = [1]
for zz in range(1, 2001):
	factorial.append(factorial[-1] * zz)
parlour = [[0 for y in range(1001)] for x in range(1001)]
for zz in range(1001):
	parlour[zz][0] = 1
	for xx in range(1, zz + 1):
		parlour[zz][xx] = parlour[zz - 1][xx - 1] + parlour[zz - 1][xx]
for _ in range(int(input())):
	soll = int(input())
	sill = len(set(input().split()))
	loll = soll - sill
	javab = 0
	guss = 1
	for xx in range(0, loll + 1):
		svpp = parlour[loll][xx]
		javab += guss * svpp * factorial[soll - xx] // 2 ** (loll - xx)
		guss = guss * -1
	print(javab % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


result = [1]
for i in range(1, 2001):
	result.append(result[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * result[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


import math
import os
import random
import re
import sys
factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)


factorial = [1]
for i in range(1, 2001):
	factorial.append(factorial[-1] * i)
pascal = [[0 for y in range(1001)] for x in range(1001)]
for i in range(1001):
	pascal[i][0] = 1
	for j in range(1, i + 1):
		pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
for _ in range(int(input())):
	m = int(input())
	n = len(set(input().split()))
	k = m - n
	ans = 0
	f = 1
	for j in range(0, k + 1):
		kCj = pascal[k][j]
		ans += f * kCj * factorial[m - j] // 2 ** (k - j)
		f = f * -1
	print(ans % 1000000007)