Read problems statements [Hindi] , [Vietnamese] , [Mandarin Chinese] , [Russian] and [Bengali] as well.

Raja only participates in contests and does not upsolve, but he claims that he has been upsolving. Chef wants to test if he is really improving, so he asks Raja to solve the following problem.

The median of a sequence of numbers is computed in the following way:
sort the sequence in non-decreasing order
if the number of elements of this sequence is odd, the median is its middle element
if the number of elements is even, the median is the average (arithmetic mean) of its two middle elements

For example, the median of $[1, 3, 2]$ is $2$ and the median of $[2, 3, 3, 2]$ is $(2+3)/2 = 5/2$.

You are given a sequence $A_{1}, A_{2}, \dots, A_{N}$. Let's call a subsequence $A_{i_{1}}, A_{i_{2}}, \dots, A_{i_{k}}$ (for any $k > 0$, $1 ≤ i_{1} < i_{2} < \ldots < i_{k} ≤ N$) *good* if the median of this subsequence is an element of this subsequence. Find the number of good subsequences. Since this number may be large, compute it modulo $1000000007$ ($10^{9}+7$).

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer — the number of good subsequences modulo $10^{9}+7$.

------  Constraints ------
$1 ≤ T ≤ 30$
$1 ≤ N ≤ 1,000$
$1 ≤ A_{i} ≤ 2N$ for each valid $i$

------  Subtasks ------
Subtask #1 (5 points): $A$ is a permutation of integers $1$ through $N$

Subtask #2 (25 points): $1 ≤ N ≤ 100$

Subtask #3 (70 points): original constraints

----- Sample Input 1 ------ 
1

3

2 3 2
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Example case 1: The good subsequences are $[2]$, $[3]$, $[2]$, $[2,2]$, $[2,3,2]$.

Source: codechef | Difficulty: HARD
Tags: Combinatorics

Mathematics


Solutions:
def main():
	(mod, m) = (int(1000000000.0 + 7), 1005)
	(Fact, iFact) = ([1] * m, [1] * m)
	for i in range(2, m):
		Fact[i] = Fact[i - 1] * i % mod
		iFact[m - 1] = pow(Fact[m - 1], mod - 2, mod)
	for i in range(m - 2, 0, -1):
		iFact[i] = iFact[i + 1] * (i + 1) % mod
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr = sorted(map(int, input().split()))
		ans = 0
		for i in range(n):
			for j in range(i, n):
				if i == j or arr[i] == arr[j]:
					(l, r) = (i, n - j - 1)
					ans += Fact[l + r] * iFact[l] * iFact[r] % mod
				else:
					break
		print(ans % mod)
main()


def main():
	(N, M) = (1005, int(1000000000.0 + 7))
	(F, IF) = ([1] * N, [1] * N)
	for i in range(1, N):
		F[i] = F[i - 1] * i % M
	IF[N - 1] = pow(F[N - 1], M - 2, M)
	for i in range(N - 2, 0, -1):
		IF[i] = IF[i + 1] * (i + 1) % M
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		arr.sort()
		res = 0
		for i in range(n):
			for j in range(i, n):
				if i == j:
					(l, r) = (i, n - i - 1)
					res += F[l + r] * IF[l] * IF[r]
				elif arr[i] == arr[j]:
					(l, r) = (i, n - j - 1)
					res += F[l + r] * IF[l] * IF[r]
				else:
					break
		print(res % M)
main()


def main():
	(N, M) = (2222, 1000000007)
	(F, IF) = ([1] * N, [1] * N)
	for i in range(1, N):
		F[i] = F[i - 1] * i % M
	IF[N - 1] = pow(F[N - 1], M - 2, M)
	for i in range(N - 2, 0, -1):
		IF[i] = IF[i + 1] * (i + 1) % M
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		a.sort()
		res = 0
		for i in range(n):
			for j in range(i, n):
				if i == j:
					(l, r) = (i, n - i - 1)
					res += F[l + r] * IF[l] * IF[r]
				elif a[i] == a[j]:
					(l, r) = (i, n - j - 1)
					res += F[l + r] * IF[l] * IF[r]
				else:
					break
		print(res % M)
main()


def modinv(v, m):
	v %= m
	pv = m
	pc = 0
	c = 1
	while v > 0:
		(q, a) = divmod(pv, v)
		(pc, c) = (c, pc - q * c)
		(pv, v) = (v, a)
	return pc % m
mdl = 1000000007
lim = 1001
fac = 1
facm = [1]
for n in range(1, lim):
	fac = n * fac % mdl
	facm.append(fac)
ifac = modinv(fac, mdl)
invfm = [1] * lim
for n in reversed(range(1, lim)):
	invfm[n] = ifac
	ifac = n * ifac % mdl

def bc(n, k):
	if k == 0 or k == n:
		return 1
	return facm[n] * invfm[k] * invfm[n - k] % mdl
for ti in range(int(input())):
	n = int(input())
	ays = list(map(int, input().split()))
	oddseq = pow(2, n - 1, mdl)
	ays.sort()
	evnseq = 0
	ax = 0
	while ax < n - 1:
		a = ays[ax]
		bx = ax + 1
		if ays[bx] == a:
			while bx < n and ays[bx] == a:
				bx += 1
			r = bx - ax - 1
			if r == 1:
				evnseq += bc(n - 2, ax)
			else:
				evnseq += bc(n - r - 1, ax)
				evnseq += sum((bc(n, ci) for ci in range(ax + 2, ax + r, 2)))
				if r % 2 == 0:
					evnseq += bc(n - 1, ax + r - 1)
			evnseq %= mdl
		ax = bx
	print((oddseq + evnseq) % mdl)


M = 10 ** 9 + 7
f = [1] + [None] * 1000
for i in range(1, 1001):
	f[i] = f[i - 1] * i % M
rf = [0] * 1001 + [pow(f[1000], M - 2, M)]
for i in range(1000, 0, -1):
	rf[i] = rf[i + 1] * i % M
C = lambda i, j: f[i] * rf[j + 1] * rf[i - j + 1]
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	r = pow(2, n, M) - 1
	x0 = 0
	for (i, x) in enumerate(a):
		if x > x0:
			(i0, x0) = (i - 1, x)
		r -= C(i0 + n - i, i0)
	print(r % M)


from sys import stdin
dp = [[0 for x in range(1001)] for y in range(1001)]
for i in range(1001):
	for j in range(i + 1):
		if i == j or j == 0:
			dp[i][j] = 1
		else:
			dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
T = int(stdin.readline())
for k in range(T):
	N = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	count = 0
	arr.sort()
	for i in range(N):
		for j in range(i + 1, N):
			if arr[i] == arr[j]:
				count += dp[i + N - 1 - j][i]
			else:
				break
	print(((1 << N - 1) % 1000000007 + count) % 1000000007)


mdl = 1000000007
lim = 1000
coeff = [[1] * (n + 1) for n in range(lim)]
tc = coeff[0]
for n in range(1, lim):
	lc = tc
	tc = coeff[n]
	for k in range(1, n // 2 + 1):
		tc[n - k] = tc[k] = (lc[k - 1] + lc[k]) % mdl

def bc(n, k):
	if k < 0 or k > n:
		return 0
	return coeff[n][k]
for ti in range(int(input())):
	n = int(input())
	ays = list(map(int, input().split()))
	oddseq = pow(2, n - 1, mdl)
	ays.sort()
	evnseq = 0
	ax = 0
	while ax < n - 1:
		a = ays[ax]
		bx = ax + 1
		if ays[bx] == a:
			while bx < n and ays[bx] == a:
				bx += 1
			r = bx - ax - 1
			out = n - 2
			for g in range(r):
				evnseq += sum(coeff[out][ax:ax + r - g])
				out -= 1
			evnseq %= mdl
		ax = bx
	print((oddseq + evnseq) % mdl)


MOD = 10 ** 9 + 7
table = [[1 for i in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	for j in range(1, 1001):
		table[i][j] = (table[i][j - 1] + table[i - 1][j]) % MOD
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().strip().split()]
	sarr = set(arr)
	if len(sarr) == n:
		print(2 ** (n - 1) % MOD)
	else:
		arr = sorted(arr, reverse=False)
		(ga, gb) = (0, 0)
		while gb < n:
			tmp = gb
			mark = tmp + 1
			while mark < n:
				if arr[mark] == arr[tmp]:
					mark += 1
				else:
					break
			gb = mark
			for i in range(tmp, mark):
				for j in range(i, mark):
					(low, right) = (i, n - j - 1)
					val = 0
					val = table[low][right] % MOD
					ga = (ga + val) % MOD
		print(ga % MOD)


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
mod = 1000000007
fac = [0 for x in range(2001)]
fac[0] = 1
for i in range(1, 2001):
	fac[i] = fac[i - 1] * i % mod

def modInverse(n, p):
	return power(n, p - 2, p)

def nCrModPFermat(n, r, p):
	if r == 0:
		return 1
	return fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p % p
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a.append(3000)
	dup = [1]
	pos_f = [0]
	pos_l = [0]
	j = 1
	for i in range(n):
		if a[i] == a[i + 1]:
			if dup[j - 1] == 1:
				pos_f[j - 1] = i
			dup[j - 1] += 1
		elif dup[j - 1] > 1:
			pos_l[j - 1] = i
			dup.append(1)
			pos_f.append(0)
			pos_l.append(0)
			j += 1
	ans = 0
	for i in range(j - 1):
		mi = min(pos_f[i] - 0, n - pos_l[i] - 1)
		ma = max(pos_f[i] - 0, n - pos_l[i] - 1)
		s_even = 0
		s_odd = 0
		l_even = 0
		l_odd = 1
		for k in range(2, dup[i] + 1):
			if k % 2 == 0:
				if l_even == 0 and mi + l_even <= ma + mi:
					s_even = (s_even + nCrModPFermat(ma + mi, mi + l_even, mod)) % mod
				else:
					if mi + l_even <= ma + mi:
						s_even = (s_even + nCrModPFermat(ma + mi, mi + l_even, mod)) % mod
					if ma + l_even <= ma + mi:
						s_even = (s_even + nCrModPFermat(ma + mi, ma + l_even, mod)) % mod
				l_even += 2
				ans = (ans + nCrModPFermat(dup[i], k, mod) * s_even) % mod
			else:
				if mi + l_odd <= ma + mi:
					s_odd = (s_odd + nCrModPFermat(ma + mi, mi + l_odd, mod)) % mod
				if ma + l_odd <= ma + mi:
					s_odd = (s_odd + nCrModPFermat(ma + mi, ma + l_odd, mod)) % mod
				l_odd += 2
				ans = (ans + nCrModPFermat(dup[i], k, mod) * s_odd) % mod
	ans = (ans + power(2, n - 1, mod)) % mod
	print(ans)


def readInt():
	return int(input())

def readInts():
	return [int(x) for x in input().split()]

def cases():
	numCases = readInt()
	for _ in range(numCases):
		n = readInt()
		seq = readInts()
		yield (n, seq)
medianWays = [[[0, 0] for _ in range(1001)] for _ in range(1001)]
for n in range(1, 1001):
	for m in range(n - 1):
		medianWays[n][m][0] = (medianWays[n - 1][m][0] + medianWays[n - 1][m][1]) % 1000000007
		medianWays[n][m][1] = (medianWays[n - 1][n - m - 2][0] + medianWays[n - 1][m][1]) % 1000000007
	medianWays[n][n - 1][1] = 1

def calcWays(n, lastPos, groupSize):
	left = lastPos + 1 - groupSize
	result = 0
	for p1 in range(1, groupSize):
		for p2 in range(p1 + 1, groupSize + 1):
			result = (result + medianWays[n - (p2 - p1 - 1)][left + p1][0]) % 1000000007
	return result

def solve(n, seq):
	seq.sort()
	ways = pow(2, n - 1, 1000000007)
	for (p, e) in enumerate(seq):
		otherp = p + 1
		while otherp < n and seq[otherp] == e:
			pairDist = otherp - p
			ways = (ways + medianWays[n - pairDist][p][1]) % 1000000007
			otherp += 1
	return ways
for data in cases():
	print(solve(*data))


arr = [[0 for x in range(1001)] for y in range(1001)]
for i in range(1001):
	for j in range(i + 1):
		if i == j or j == 0:
			arr[i][j] = 1
		else:
			arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]
modu = 1000000007
t = int(input())
while t > 0:
	n = int(input())
	a = []
	a = [int(i) for i in input().split()]
	a.sort()
	ans = 0
	p = 1
	while p <= n:
		ans = ans + arr[n][p]
		p = p + 2
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i] == a[j]:
				ans = ans + arr[i + n - 1 - j][i]
	print(ans % modu)
	t = t - 1


from sys import stdin
a = []
for i in range(1001):
	a.append([])
	a[i].append(1)
	for j in range(1, i):
		a[i].append((a[i - 1][j - 1] + a[i - 1][j]) % (10 ** 9 + 7))
	if i != 0:
		a[i].append(1)
a[0] = [1]
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	b = [int(x) for x in stdin.readline().split()]
	c = 0
	if n % 2 != 0:
		ulim = n
	else:
		ulim = n - 1
	for i in range(ulim, -1, -2):
		c = (c + a[n][n - i]) % (10 ** 9 + 7)
	ulim = n - 2
	b = sorted(b)
	for i in range(n - 1):
		rec = 0
		for j in range(i + 1, n):
			if b[i] == b[j]:
				c = (c + a[ulim - rec][i]) % (10 ** 9 + 7)
				rec += 1
			else:
				break
	print(c)


a = []
for i in range(1001):
	a.append([])
	a[i].append(1)
	for j in range(1, i):
		a[i].append((a[i - 1][j - 1] + a[i - 1][j]) % (10 ** 9 + 7))
	if i != 0:
		a[i].append(1)
a[0] = [1]
for _ in range(int(input())):
	n = int(input())
	b = [int(x) for x in input().split()]
	c = 0
	if n % 2 == 0:
		ulim = n - 1
	else:
		ulim = n
	for i in range(ulim, -1, -2):
		c = (c + a[n][n - i]) % (10 ** 9 + 7)
	ulim = n - 2
	b = sorted(b)
	for i in range(n - 1):
		rec = 0
		for j in range(i + 1, n):
			if b[i] == b[j]:
				c = (c + a[ulim - rec][i]) % (10 ** 9 + 7)
				rec += 1
			else:
				break
	print(c)


M = 1000000007
C = None
SC = None

def genC(n, M):
	C = [[0 for j in range(n + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		C[i][0] = 1
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1]
	return C

def genSC(n, M):
	SC = [[0 for j in range(n + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		SC[i][0] = C[i][0]
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			SC[i][j] = (C[i][j] % M + SC[i][j - 1] % M) % M
	return SC

def series_sum(l1, l2, m):
	if l1 > l2:
		(l1, l2) = (l2, l1)
	s = 0
	for i in range(m - 1):
		if l1 == 0:
			s = (s % M + SC[l1 + l2 + m - 2 - i][l1 + m - 2 - i] % M) % M
		else:
			s = (s % M + (SC[l1 + l2 + m - 2 - i][l1 + m - 2 - i] % M - SC[l1 + l2 + m - 2 - i][l1 - 1] % M + M) % M) % M
	return s

def findSubs(arr, M):
	arr.sort()
	sum_e = 0
	sum_o = 0
	i = 0
	while i < len(arr) - 1:
		j = i + 1
		while j < len(arr) and arr[j] == arr[i]:
			j += 1
		sum_e = (sum_e % M + series_sum(i, len(arr) - j, j - i) % M) % M
		i = j
	sum_o = pow(2, len(arr) - 1, M)
	total = (sum_e + sum_o) % M
	return total
C = genC(1000, M)
SC = genSC(1000, M)
t = int(input())
for _ in range(t):
	int(input())
	arr = [int(i) for i in input().split()]
	print(findSubs(arr, M))


from collections import defaultdict
mod = 10 ** 9 + 7
l2 = [[0 for i in range(1001)] for j in range(1001)]
l1 = [[0 for i in range(1001)] for j in range(1001)]
l2[0][0] = 1
for i in range(1, 999):
	l2[i][0] = 1
	for j in range(1, i + 1):
		l2[i][j] = (l2[i - 1][j - 1] + l2[i - 1][j]) % mod
		l1[i][j] += (l2[i][j] + l1[i - 1][j]) % mod
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	ans = pow(2, n - 1, mod)
	d = defaultdict(int)
	for i in l:
		d[i] += 1
	for i in d:
		ans += l2[d[i]][2]
	for i in range(len(l) - 1):
		if l[i] == l[i + 1]:
			extra = n - i - d[l[i]]
			d[l[i]] -= 1
			start = n - i - 2
			for j in range(1, start + 1):
				if i < j:
					break
				if extra == 0:
					sum1 = l1[start][j]
				else:
					sum1 = l1[start][j] - l1[extra - 1][j]
				save = l2[i][j] * sum1
				if save == 0:
					break
				ans += save
				ans %= mod
	print(ans)


import math
mod = 10 ** 9 + 7
facts = [0] * 1001
invfacts = [0] * 1001
facts[0] = 1
invfacts[0] = 1
for i in range(1, 1001):
	facts[i] = facts[i - 1] * i % mod
	invfacts[i] = pow(facts[i], mod - 2, mod)

def ncr(n, r, k):
	su = 0
	for i in range(k, r + 1):
		su += facts[n] * invfacts[i] * invfacts[n - i] % mod
	return su % mod
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	s = pow(2, n - 1, mod)
	(i, count) = (0, 1)
	while i < n - 1:
		if arr[i] == arr[i + 1]:
			count += 1
		elif count > 1:
			for it in range(2, count + 1):
				s += ncr(n - it, i + 1 - it, i - count + 1)
			s %= mod
			count = 1
		i += 1
	if count > 1:
		for it in range(2, count + 1):
			s += ncr(n - it, i + 1 - it, i - count + 1)
	print(s % mod)


ghat = 1000000007
sala = [[1 for x in range(1001)] for j in range(1001)]
for i in range(1, 1001):
	for j in range(1, 1001):
		sala[i][j] = (sala[i - 1][j] + sala[i][j - 1]) % ghat
for T in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	baby = 0
	bara = 0
	while bara < n:
		gandu = bara
		chup = gandu + 1
		while chup < n and ar[chup] == ar[gandu]:
			chup += 1
		bara = chup
		dher = chup - 1
		for i in range(gandu, dher + 1):
			for j in range(i, dher + 1):
				badike = i
				dandike = n - j - 1
				chor = sala[badike][dandike]
				baby = (baby + chor) % ghat
	print(baby % ghat)


from bisect import bisect_left as bl
mod = 1000000007

def po(n):
	a = 1
	for i in range(n):
		a *= 2
		a %= mod
	return a
bigdaddyarray = [[0] * 1001 for i in range(1001)]
bigdaddyarray[0][0] = 1
for i in range(1, 1001):
	bigdaddyarray[i][1] = i
for i in range(1, 1001):
	bigdaddyarray[i][0] = 1
for i in range(2, 1001):
	bigdaddyarray[1][i] = 0
for i in range(2, 1001):
	for j in range(2, 1001):
		bigdaddyarray[i][j] = bigdaddyarray[i - 1][j] + bigdaddyarray[i - 1][j - 1]
for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	ans = po(n - 1)
	for i in d.keys():
		if d[i] >= 2:
			m = bl(a, i)
			for j in range(m + 1, m + d[i]):
				r = 0
				for x in range(j + 1, m + d[i] + 1):
					ans += bigdaddyarray[n - r - 2][j - 1]
					r += 1
		ans %= mod
	print(ans)


(array, prefix) = ([], [])
for i in range(1001):
	array.append([1] * (i + 1))
	prefix.append([1] * (i + 1))
MOD = 10 ** 9 + 7
for i in range(2, 1001):
	for j in range(1, i):
		array[i][j] = array[i - 1][j - 1] + array[i - 1][j]
for i in range(1, 1001):
	for j in range(i):
		prefix[i][j] = prefix[i - 1][j] + array[i][j]
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	(cur, minus) = (0, 0)
	for i in range(n):
		while cur < n and ar[i] == ar[cur]:
			cur += 1
		if cur >= n:
			break
		for j in range(min(i, n - cur - 1) + 1):
			minus += array[i][j] * prefix[n - cur - 1][j]
	print((2 ** n - 1 - minus) % MOD)


import numpy as np
M = int(1000000000.0 + 7)

def mod_pow(base, index):
	ret = 1
	while index > 0:
		if index & 1 == 1:
			ret = ret * base % M
		index = index >> 1
		base = base * base % M
	return ret

def inv_mod(n):
	return mod_pow(n, M - 2)
F = np.empty(1001, dtype=np.int64)
F[0] = 1
for i in range(1, 1001):
	F[i] = F[i - 1] * i % M
I = np.empty(1001, dtype=np.int64)
for i in range(1001):
	I[i] = inv_mod(i)
C = np.zeros((1001, 1001), dtype=np.int64)
Cum = np.zeros((1001, 1001), dtype=np.int64)
C[:, 0] = 1
A = np.arange(1001)
for x in range(1, 1001):
	C[:, x] = C[:, x - 1] * I[x] % M
	C[:, x] = C[:, x] * (A - x + 1) % M
Cum[0, :] = C[0, :]
for A in range(1, 1001):
	Cum[A, :] = (C[A, :] + Cum[A - 1, :]) % M

def cum_sum(A1, A2):
	if A1 == 0:
		return Cum[A2, :]
	else:
		return Cum[A2, :] - Cum[A1 - 1, :]
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	next_A = [0 for _ in range(len(A))]
	next_A[n - 1] = n
	for i in range(n - 2, -1, -1):
		if A[i] == A[i + 1]:
			next_A[i] = next_A[i + 1]
		else:
			next_A[i] = i + 1
	ans = 0
	for i in range(len(A) - 1):
		if A[i] == A[i + 1]:
			prev = i
			A2 = n - i - 2
			A1 = n - next_A[i]
			ans = (ans + np.sum(C[prev, :] * cum_sum(A1, A2) % M) % M) % M
	ans = (ans + M) % M
	ans = (ans + mod_pow(2, len(A) - 1)) % M
	print(ans)


M = 10 ** 9 + 7
f = [1] + [None] * 999
rf = [1] + [None] * 999
for i in range(1, 1000):
	f[i] = f[i - 1] * i % M
	rf[i] = pow(f[i], M - 2, M)
choose = lambda i, j: f[i] * rf[j] * rf[i - j]
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	r = pow(2, n, M) - 1
	x0 = 0
	for (i, x) in enumerate(a):
		if x > x0:
			(i0, x0) = (i, x)
		i = n - i
		r -= sum((choose(i0, k + 1) * choose(i - 1, k) for k in range(min(i0, i))))
	print(r % M)


mod = 1000000007
import time

def modex(a, b):
	if b == 0:
		return 1
	if b % 2 == 0:
		y = modex(a, b / 2)
		return y % mod * (y % mod) % mod
	return a % mod * modex(a, b - 1) % mod

def modi(a):
	return modex(a, mod - 2) % mod

def main():
	nc = [[0 for x in range(2001)] for y in range(2001)]
	nc[0][0] = 1
	nc[1][0] = 1
	nc[1][1] = 1
	for i in range(2, 2001):
		nc[i][0] = 1
		for j in range(1, i + 1):
			nc[i][j] = (nc[i - 1][j] + nc[i - 1][j - 1]) % mod
	t = int(input())
	while True:
		n = int(input())
		a = [int(x) for x in input().split()]
		c = modex(2, n - 1)
		a.sort()
		for i in range(0, n - 1):
			for j in range(i + 1, n):
				if a[i] == a[j]:
					c = (c + nc[i + n - 1 - j][i]) % mod
		print(c)
		t = t - 1
		if t == 0:
			return
main()


ncr = [[1] * 1001 for i in range(1001)]
for j in range(1, 1001):
	temp = j
	for i in range(1, j):
		ncr[j][i] = temp
		temp = temp * (j - i)
		temp = temp // (i + 1)
ncr_sum = [[1] * 1001 for i in range(1001)]
for j in range(1, 1000):
	for i in range(j):
		ncr_sum[j][i] = ncr_sum[j - 1][i] + ncr[j][i]
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print('1')
		continue
	fre = [0] * 2001
	for i in a:
		fre[i] += 1
	count = 0
	for i in range(1, n + 1, 2):
		count = (count + ncr[n][i]) % 1000000007
	a.sort()
	i = 0
	while i < n - 1:
		if a[i] != a[i + 1]:
			i += 1
			continue
		j = i + fre[a[i]]
		c = fre[a[i]]
		n1 = i
		n2 = n - j
		while c > 1:
			c -= 1
			if n1 + n2 == 0:
				count = count + ncr_sum[n - 2][n2]
				n2 += 1
				continue
			if n1 < n2:
				count = count + (ncr_sum[n - 2][n1] - ncr_sum[n1 + n2 - 1][n1])
				n1 += 1
			else:
				count = count + (ncr_sum[n - 2][n2] - ncr_sum[n1 + n2 - 1][n2])
				n2 += 1
		i += fre[a[i]]
	print(count % 1000000007)


M = 10 ** 9 + 7
f = [1] + [None] * 1000
rf = [1] + [None] * 1000
for i in range(1, 1001):
	f[i] = f[i - 1] * i % M
	rf[i] = pow(f[i], M - 2, M)
c = lambda i, j: f[i] * rf[j] * rf[i - j]
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	r = pow(2, n, M) - 1
	i = 0
	while i < n:
		i1 = next((j for j in range(i + 1, n) if a[j] > a[i]), n)
		u = n - i1
		for j in range(i, i1):
			r -= sum((c(j, k) * c(u, k + 1) for k in range(min(j + 1, u))))
		i = i1
	print(r % M)


M = 10 ** 9 + 7
f = [1] + [None] * 1000
rf = [1] + [None] * 1000
for i in range(1, 1001):
	f[i] = f[i - 1] * i % M
	rf[i] = pow(f[i], M - 2, M)
c = lambda i, j: f[i] * rf[j] * rf[i - j]
t = int(input())
for _ in range(t):
	n = int(input())
	a = [0] * (2 * n)
	for i in map(int, input().split()):
		a[i - 1] += 1
	r = pow(2, n, M) - 1
	s = 0
	for x in a:
		(u, s) = (s, s + x)
		v = n - s
		for i in range(x):
			r -= sum((c(u, k) * c(v, k + 1) for k in range(min(u + 1, v))))
			u += 1
	print(r % M)


M = 10 ** 9 + 7
C = [1001 * [0] for x in range(1001)]
C[0][0] = 1
for i in range(1, 1001):
	C[i][0] = 1
	for j in range(1, i + 1):
		C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M
t = int(input())
answer = 0
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	A.sort()
	for i in range(len(A)):
		for j in range(i, len(A)):
			if A[i] == A[j]:
				answer = (answer + C[i + n - 1 - j][i]) % M
	print(answer)
	answer = 0


M = 1000000007
N = 1000
factorialNumInverse = [0 for i in range(N + 1)]
naturalNumInverse = [0 for i in range(N + 1)]
fact = [0 for i in range(N + 1)]

def InverseofNumber(p):
	naturalNumInverse[0] = naturalNumInverse[1] = 1
	for i in range(2, N + 1):
		naturalNumInverse[i] = naturalNumInverse[p % i] * (p - p // i) % p

def InverseofFactorial(p):
	factorialNumInverse[0] = factorialNumInverse[1] = 1
	for i in range(2, N + 1):
		factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p

def factorial(p):
	fact[0] = 1
	for i in range(1, N + 1):
		fact[i] = fact[i - 1] * i % p
InverseofNumber(M)
InverseofFactorial(M)
factorial(M)

def nCr(n, r, p):
	return fact[n] * factorialNumInverse[r] % p * factorialNumInverse[n - r] % p
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	sufInd = [0 for i in range(n)]
	sufInd[n - 1] = n - 1
	for i in range(n - 2, -1, -1):
		if a[i] == a[i + 1]:
			sufInd[i] = sufInd[i + 1]
		else:
			sufInd[i] = i
	finalAns = 0
	i = 0
	y = 0
	z = 0
	m = 0
	while i < n:
		m = sufInd[i] - i + 1
		y = i
		z = n - sufInd[i] - 1
		for j in range(2, m + 1):
			c1 = 0
			c2 = j - 2
			ans = 0
			for k in range(1, j):
				if c1 == 0 and y + c2 <= y + z:
					ans = (ans + nCr(y + z, y + c2, M)) % M
				elif c2 == 0 and z + c1 <= y + z:
					ans = (ans + nCr(y + z, z + c1, M)) % M
				c2 = c2 - 2
				if c2 < 0:
					if c1 == 0:
						c1 = -c2
					else:
						c1 += 2
					c2 = 0
			ans = ans * nCr(m, j, M) % M
			finalAns = (finalAns + ans) % M
		i = sufInd[i] + 1
	for i in range(1, n + 1, 2):
		finalAns = (finalAns + nCr(n, i, M)) % M
	print(finalAns)


import math
mod = 10 ** 9 + 7
facts = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 227020758, 178290591, 674358851, 789741546, 425606191, 660911389, 557316307, 146326063, 72847302, 602640637, 860734560, 657629300, 440732388, 459042011, 394134213, 35757887, 36978716, 109361473, 390205642, 486580460, 57155068, 943272305, 14530444, 523095984, 354551275, 472948359, 444985875, 799434881, 776829897, 626855450, 954784168, 10503098, 472639410, 741412713, 846397273, 627068824, 726372166, 318608048, 249010336, 948537388, 272481214, 713985458, 269199917, 75195247, 286129051, 595484846, 133605669, 16340084, 996745124, 798197261, 286427093, 331333826, 536698543, 422103593, 280940535, 103956247, 172980994, 108669496, 715534167, 518459667, 847555432, 719101534, 932614679, 878715114, 661063309, 562937745, 472081547, 766523501, 88403147, 249058005, 671814275, 432398708, 753889928, 834533360, 604401816, 187359437, 674989781, 749079870, 166267694, 296627743, 586379910, 119711155, 372559648, 765725963, 275417893, 990953332, 104379182, 437918130, 229730822, 432543683, 551999041, 407899865, 829485531, 925465677, 24826746, 681288554, 260451868, 649705284, 117286020, 136034149, 371858732, 391895154, 67942395, 881317771, 114178486, 473061257, 294289191, 314702675, 79023409, 640855835, 825267159, 333127002, 640874963, 750244778, 281086141, 979025803, 294327705, 262601384, 400781066, 903100348, 112345444, 54289391, 329067736, 753211788, 190014235, 221964248, 853030262, 424235847, 817254014, 50069176, 159892119, 24464975, 547421354, 923517131, 757017312, 38561392, 745647373, 847105173, 912880234, 757794602, 942573301, 156287339, 224537377, 27830567, 369398991, 365040172, 41386942, 621910678, 127618458, 674190056, 892978365, 448450838, 994387759, 68366839, 417262036, 100021558, 903643190, 619341229, 907349424, 64099836, 89271551, 533249769, 318708924, 92770232, 420330952, 818908938, 584698880, 245797665, 489377057, 66623751, 192146349, 354927971, 661674180, 71396619, 351167662, 19519994, 689278845, 962979640, 929109959, 389110882, 98399701, 89541861, 460662776, 289903466, 110982403, 974515647, 928612402, 722479105, 218299090, 96415872, 572421883, 774063320, 682979494, 693774784, 611379287, 166890807, 880178425, 837467962, 705738750, 616613957, 338771924, 497191232, 896114138, 560652457, 661582322, 224945188, 262995829, 859081981, 857116478, 279856786, 408062844, 406076419, 367193638, 985761614, 767884817, 77737051, 801784560, 410447512, 813374614, 702909132, 777826615, 11426636, 685259446, 721228129, 931065383, 593559607, 860745086, 578819198, 495425745, 893029457, 6156532, 502193801, 37480384, 220174401, 383076669, 3013247, 750298503, 574624441, 230733683, 144887710, 656590378, 773954850, 358485371, 772254339, 469363737, 95843299, 823414273, 87709482, 892174648, 749756145, 185864756, 68295241, 98238739, 131504392, 111672419, 928208089, 687974198, 753032165, 71715287, 506557931, 290314197, 546089425, 174590825, 187067364, 817659471, 309331349, 303445769, 964814732, 112937795, 848457973, 113604679, 263728612, 162653895, 519013648, 956915940, 591788795, 26960558, 818561771, 201473695, 830318534, 283328761, 298655153, 103269519, 567777414, 629890782, 707451727, 528064896, 419467694, 259775012, 452053078, 972081682, 512829263, 412924123, 354780756, 917691336, 648929514, 519218426, 957710940, 848100261, 607279584, 78508462, 651656900, 271922065, 927371945, 976904514, 655633282, 147015495, 44958071, 431540693, 956102180, 821001984, 4640954, 508310043, 709072863, 866824584, 318461564, 773853828, 371761455, 53040744, 609526889, 972452623, 799173814, 723225821, 3874155, 305590228, 289496343, 139259591, 348260611, 756867525, 848691744, 101266155, 835557082, 267191274, 448180160, 518514435, 443022120, 614718802, 151579195, 204297074, 912569551, 137049249, 515433810, 979001276, 524451820, 229298431, 88837724, 892742699, 387369393, 840349900, 206661672, 18186411, 619853562, 246548548, 236767938, 893832644, 930410696, 321544423, 971435684, 402636244, 780681725, 194281388, 661238608, 964476271, 643075362, 439409780, 96895678, 723461710, 915447882, 785640606, 114709392, 933696835, 539582134, 739120141, 300372431, 244129985, 722433522, 26638091, 388855420, 42468156, 647517040, 474194942, 832805846, 958306874, 489519451, 339220689, 9833277, 923477502, 390998217, 790283925, 694135631, 736657340, 609563281, 873127083, 489593220, 264439147, 891171227, 489029295, 502009550, 325923608, 280525558, 857054649, 820622208, 558213940, 216997416, 487921842, 951328535, 606653379, 794417402, 449723904, 783486165, 414645478, 809681447, 114612567, 824953206, 255016498, 147060381, 88903008, 228293174, 394357308, 362355866, 900088886, 638573794, 779598451, 904922263, 451026166, 549459329, 212643744, 563246709, 391796933, 174243175, 189725986, 238337196, 60051478, 782959006, 982673239, 237607992, 685987666, 694447544, 195840153, 519748540, 446086975, 523485236, 185780714, 716004996, 214280883, 140643728, 555470704, 516522055, 116665689, 899547947, 490696549, 683197147, 686671136, 988747143, 744912554, 619072836, 345158054, 224284246, 637879131, 78947725, 342273666, 237716550, 915360466, 711578771, 423071394, 228124918, 271834959, 480779410, 254894593, 859192972, 990202578, 258044399, 151532640, 644862529, 48049425, 448119239, 130306338, 850105179, 401639970, 606863861, 183881380, 837401090, 513536652, 714177614, 946271680, 243293343, 403377310, 688653593, 15447678, 754734307, 631353768, 202296846, 159906516, 912696536, 737140518, 467380526, 896686075, 309895051, 356369955, 461415686, 706245266, 10064183, 183054210, 455971702, 737368289, 956771035, 564163693, 365118309, 226637659, 304857172, 440299843, 717116122, 485961418, 615704083, 476049473, 354119987, 329471814, 620060202, 251964959, 45357250, 175414082, 671119137, 48735782, 122378970, 717506435, 18459328, 949577729, 771970076, 635808197, 608040366, 165916428, 258536202, 902229110, 617090616, 548564593, 613394864, 753777984, 577888302, 416452176, 881599549, 524547188, 599140122, 522765386, 657552586, 256787840, 287613719, 776067801, 597965522, 458655497, 764387515, 350167935, 494713961, 513386012, 576480762, 864589772, 86987059, 495636228, 512647986, 721997962, 982831380, 162376799, 204281975, 462134806, 189646394, 425968575, 209834628, 494248765, 664281698, 947663843, 540352769, 25662122, 986679150, 207298711, 477043799, 24708053, 528335066, 189351697, 717500453, 42764755, 316734785, 823726196, 293357001, 547414377, 258966410, 602945692, 561521296, 351253952, 752369730, 174204566, 871148004, 302242737, 554611874, 540181425, 349941261, 414343943, 921115587, 959388563, 227019335, 708812719, 793380997, 342547759, 324322556, 458370547, 356254978, 809319893, 159690374, 848340820, 971304725, 180230004, 103061704, 207441144, 443272953, 45593686, 541647240, 612817107, 849140508, 109375794, 906749744, 159084460, 541378020, 692284266, 908221578, 720697998, 363923522, 819281897, 701846632, 479994712, 196613531, 29272489, 792937812, 859009553, 202148261, 385627435, 115321267, 612859231, 132778909, 173511339, 782369566, 322583903, 324703286, 31244274, 433755056, 109559692, 871157455, 350443931, 592104988, 197184362, 141678010, 649163959, 746537855, 954594407, 850681817, 703404350, 467293824, 684978431, 565588709, 378843675, 825260479, 749777538, 850502015, 387852091, 412307507, 307565279, 914127155, 864079609, 845970807, 414173935, 638273833, 664477235, 173471099, 480759791, 839694748, 190898355, 956270620, 957911348, 43002811, 628936576, 966234409, 667971950, 236586166, 954211897, 223051884, 21058295, 656573222, 631532535, 809706350, 984734695, 314281677, 311454037, 640732448, 434907794, 175084834, 434807109, 973816812, 488481268, 844735329, 917344075, 314288693, 459259162, 992521062, 667512257, 603748166, 679935673, 833938466, 933875943, 522922384, 981191471, 457854178, 112860028, 484939649, 611363777, 627371454, 844300972, 962501388, 738504183, 631041465, 29224765, 334078303, 211237785, 626057542, 900175080, 728504100, 450509755, 575177363, 905713570, 416609984, 874776027, 334255451, 683287462, 999293262, 474888472, 317020697, 180417613, 591538360, 879151833, 605566485, 569294094, 970567518, 896200922, 943088633, 145735679, 884701203, 949403596, 749113557, 78958680, 850679027, 665376978, 686499745, 426302291, 842343474, 708066168, 962548572, 349652428, 833757979, 492365420, 136639914, 76093131, 591710464, 208764552, 166233017, 498121245, 545840935, 26721664, 736011124, 880639351, 137410283, 42609708, 235572009, 981737748, 718913567, 909319027, 906112184, 298059463, 274736280, 217450848, 351267027, 149682364, 249066734, 11785215, 333890217, 774940233, 302540697, 519852435, 802535369, 620684620, 306323295, 752310997, 848793393, 883503040, 569433124, 254795373, 855478464, 660158704, 87911700, 944741410, 351053939, 2634663, 134077016, 736459220, 4882454, 969435081, 120150411, 922584286, 828772112, 106810765, 371205161, 17024731, 960279329, 389323593, 23991206, 744762405, 684217429, 479374977, 963728237, 3246420, 688035746, 381629444, 752436308, 274567573, 440219140, 702541058, 919238277, 563955926, 467150839, 5249506, 399086000, 833151662, 847391187, 655983283, 337920422, 866913758, 675206635, 549602585, 963783662, 324756002, 393087771, 731515248, 787956453, 550936813, 398161393, 631665856, 442637251, 454846959, 348994181, 88011024, 513458067, 60476466, 9760396, 403700900, 990173371, 519613195, 945797344, 114696834, 327457551, 905694736, 143025346, 289024806, 451579463, 325709522, 18701196, 326143996, 49850509, 619195074, 414881030, 850660769, 880149960, 651809429, 592293509, 810577782, 929598726, 835669318, 731671946, 529667681, 285562083, 293565850, 686472980, 274474950, 282703792, 889076915, 56602629, 546147347, 255724802, 873696194, 831784350, 110556728, 279941051, 667003092, 302778600, 803516696, 772054724, 165410893, 531446229, 958833885, 703493734, 68812272, 481542542, 722167619, 172528691, 173636402, 356397518, 390931659, 311533827, 53449710, 959934024, 259493848, 215350798, 907381983, 791418522, 896453666, 530274270, 443147787, 468552325, 410897594, 491169384, 314015783, 406644587, 772818684, 721371094, 596483817, 922913559, 78344520, 173781169, 485391881, 326797438, 209197264, 227032260, 183290649, 293208856, 909531571, 778733890, 346053132, 674154326, 75833611, 738595509, 449942130, 545136258, 334305223, 589959631, 51605154, 128106265, 85269691, 347284647, 656835568, 934798619, 602272125, 976691718, 647351010, 456965253, 143605060, 148066754, 588283108, 104912143, 240217288, 49898584, 251930392, 868617755, 690598708, 880742077, 200550782, 935358746, 104053488, 348096605, 394187502, 726999264, 278275958, 153885020, 653433530, 364854920, 922674021, 65882280, 762280792, 84294078, 29666249, 250921311, 659332228, 420236707, 614100318, 959310571, 676769211, 355052615, 567244231, 840761673, 557858783, 627343983, 461946676, 22779421, 756641425, 641419708, 61123214, 245460001, 196379281, 164796745, 620727570, 451931052, 94566179, 322707767, 612134628, 255969954, 785621688, 49142691, 781545640, 487273416, 582513782, 833998375, 176341439, 515583649, 379734656, 329346411, 262683279, 462309262, 942371722, 988636580, 352487409, 652079107, 685238206, 424870840, 192091301, 854038651, 513843021, 285993962, 431760681, 440541032, 959964935, 523665702, 41329173, 899681280, 768843382, 597111687, 593261820, 178812114, 501033600, 79074739, 633101681, 224353692, 898313886, 432945941, 160288931, 303376374, 848566848, 692317852, 10693053, 270477785, 354061180, 888603469, 253860160, 584047404, 506196510, 568296848, 962951514, 654500714, 734254117, 246375021, 389395531, 95633141, 40560733, 318862543, 864056087, 540006622, 347088116, 78457748, 185163016, 865077798, 958626347, 481942155, 51697302, 729691171, 336768000, 709437459, 901887817, 842611169, 547889643, 912368861, 920207262, 345079539, 101456268, 384418814, 632085520, 973211984, 774267117, 499685849, 156629135, 352272493, 738377140, 261339777, 689733367, 327231667, 627599520, 359467170, 773351405, 233242346, 266305839, 1644198, 816838783, 423687677, 22255156, 658712680, 512357010, 716277124, 783879199, 673663191, 787126340, 858736628, 491333521, 328205600, 605652638, 119644545, 882244924, 114307964, 139226748, 212410164, 536612506, 152452523, 509087178, 232158417, 642534132, 778495828, 921783666, 615535293, 170411511, 905829108, 304372182, 158051973, 388988102, 890480785, 476645461, 422530824, 262605169, 369890567, 45133993, 543019649, 671454467, 143904872, 771077292, 654570451, 792302047, 562743593, 592383835, 241405483, 857708994, 80754172, 109559665, 431852528, 789666354, 854298840, 423750964, 703612882, 487324533, 296454325, 183468917, 190880063, 993511722, 447636316, 496304493, 691034792, 437596622, 112850919, 922723394, 586363427, 631568215, 197942800, 186902776, 423857491, 32548439, 276963998, 986623371, 242322904, 698701821, 468143012, 876893308, 487882804, 165353093, 778060747, 1978741, 346786812, 635942967, 500239511, 784774421, 881554459, 931353326, 173156822, 576087204, 848116767, 499529474, 437246725, 384326164, 422741252, 866757606, 109119920, 53023003, 733649165, 579939321, 246937598, 559803511, 123029541, 496654951, 959176615, 644519422, 868495167, 747639880, 139528218, 247727251, 740880614, 169939710, 646685918, 16756697, 409656806, 371643021, 404482449, 873066778, 887595254, 528988047, 481364999, 672119652, 18687584, 929665414, 629120405, 188972334, 435969196, 678076524, 390271723, 205031092, 8365757, 331709825, 993340837, 762606773, 107178366, 793994550, 553235112, 564769190, 443329073, 58033882, 194148704, 715134793, 57945841, 258463223, 562100050, 62957536, 696919454, 846230857, 481025551, 725011189, 164024643, 850925530, 762458204, 409955722, 724294671, 886984412, 600351301, 42985262, 247400266, 466533774, 698686213, 838053264, 975424804, 863218023, 560445506, 205342137, 784512170, 114961091, 230506730, 435065239, 273110608, 216022764, 645044939, 722381342, 203348615, 82876765, 82258458, 373083963, 293637220, 736550628, 730999737, 334655472, 366933982, 244031530, 312608442, 952278924, 439803364, 786138955, 691522755, 138915957, 757247105, 634994115, 952367286, 220361297, 28961504, 620993437, 291462451, 192646098, 825217846, 258845813, 534937793, 93814979, 522361720, 726763266, 606345278, 705963351, 811983342, 510153914, 321930485, 694723851, 867133830, 280978470, 767663937, 13397952, 658500617, 562307747, 246220846, 257735291, 726052322, 567215286, 993033414, 769264345, 44514330, 70515497, 644579365, 645970093, 140217677, 629726785, 796071754, 163640655, 296632244, 4042968, 401405213, 678766029, 188940446, 991255430, 282266904, 519915618, 726754477, 31255779, 7766682, 446187220, 567993920, 87804885, 360984154, 967620344, 287455258, 352050842, 972735059, 110525615, 651681667, 28652604, 852930758, 427030507, 907424453, 189822996, 159272754, 770216682, 35113541, 859756054, 707249452, 395495225, 246473570, 929367838, 375193487, 639880112, 635747308, 609553171, 306944760, 435152533, 899576163, 917215473, 88482014, 839732431, 151281819, 617626945, 325178136, 71002673, 125693400, 833970989, 215840698, 939364644, 959387477, 670421289, 544742622, 647496666, 20359440, 319980844, 413331733, 771100044, 913453818, 268067192, 221797414, 850985195, 677294287, 534700884, 581232364, 306536266, 763841929, 670218890, 987314980, 177537191, 617288803, 525339745, 678355787, 803297198, 649041256, 797205811, 654597257, 945917673, 527580263, 526066923, 910757760, 543736890, 18904623, 825659855, 436985896, 956953876, 788402152, 896254449, 266326444, 515180047, 646741884, 900662014, 145346990, 700847261, 211576216, 765562982, 286182552, 99594146, 818004370, 836262739, 873284804, 910254570, 946062504, 383933729, 864565896, 839447421, 483172612, 218074237, 899196030, 338254257, 115652199, 348730784, 962171704, 186789338, 844538210, 424934135, 4359701, 334645511, 574569592, 998750515, 180739662, 337685693, 345736950, 430206522, 101517724, 317393728, 29627088, 344429443, 244701024, 486997654, 938555773, 861309359, 402130164, 729206786, 933967923, 866805122, 937130659, 393451047, 946839225, 587847103, 662317959, 243618597, 68283846, 991807534, 875140051, 82406459, 126371384, 408761163, 601561650, 319043999, 99379196, 776863423, 972765339, 447579635, 893651488, 434359284, 64047192, 622456991, 950738051, 353376298, 650938112, 454346846, 611570548, 744245040, 367552188, 695830331, 137149847, 136218599, 872771468, 521050149, 701518906, 188983943, 987784056, 566130074, 856405762, 29097324, 995153587, 667366596, 393019274, 424195945, 81048119, 949995669, 93415448, 898064525, 58068445, 322104229, 242633108, 530220901, 56647468, 387388098, 154233411, 514416952, 29097154, 489548158, 8676497, 283716816, 654159074, 825853428, 859149690, 794764924, 758914724, 451922626, 56993923, 713646888, 16199827, 963933239, 385044136, 123097690, 62832030, 75485671, 700846554, 209611450, 478522332, 231087081, 184973044, 893189242, 229693882, 714596254, 482570946, 397815780, 1349347, 100933265, 254025771, 26174217, 831778240, 405823554, 896386917, 52741464, 487649122, 170870589, 583340505, 94564937, 277820180, 899859375, 779208866, 137119918, 552509591, 97580560, 591800369, 85574651, 865649038, 128523371, 809878024, 797390950, 877692187, 631337938, 776610930, 375093587, 148237650, 956673612, 284338013, 244423474, 144473996, 569178041, 993078862, 988458389, 625744277, 810626289, 138295622, 581515550, 98811304, 801651389, 38910655, 218136911, 19055157, 507306147, 704441810, 220213527, 222494837, 104210886, 362681747, 829563355, 937865509, 25593418, 205402693, 903736113, 822603964, 860184650, 338015384, 894841345, 63603398, 846693852, 950642953, 90930134, 306816051, 348815192, 778237469, 79403346, 951033008, 428627185, 947797938, 67234332, 457491733, 254027842, 65379562, 634064880, 793876922, 401004554, 241436651, 748921627, 235773197, 960720794, 660649561, 804622905, 581554967, 331694169, 641821690, 513029292, 420150147, 146986978, 940564101, 109063504, 736653339, 741347513, 223387889, 813402163, 740363875, 821476814, 722640850, 970598385, 310914311, 185009722, 746116934, 807984847, 254836633, 283644452, 417075927, 597261750, 843545049, 502496757, 159591303, 38700239, 551998204, 284996029, 943365105, 363079423, 68791007, 87353906, 230437622, 983014155, 531712251, 681438690, 454113819, 457096767, 922563191, 828713221, 895627971, 341864644, 700056471, 595145382, 415107031, 285556397, 19194762, 419952794, 720216897, 886764308, 405198636, 1285946, 178392510, 375302336, 512757404, 149308498, 525827833, 381482016, 519422664, 537945283, 582865261, 619532539, 683439071, 263607900, 715074257, 631748159, 25848019, 174264163, 991716651, 827177989, 128707256, 475527988, 54965727, 266221147, 835485060, 527837982, 825646734, 286725813, 168394909, 807636366, 749812522, 926966369, 90008970, 265472165, 204953584, 954837097, 958492073, 232782618, 713926326, 806461661, 791587080, 820400043, 573664608, 308087915, 840616702, 151201154, 787603818, 643029919, 872051234, 241187768, 149088916, 861978775, 290973079, 748019306, 41699134, 848386594, 979755938, 593123571, 966241991, 889714404, 779624902, 682443644, 6143197, 781310665, 981518143, 527365183, 107985225, 946009452, 976623872, 834626559, 611986668, 932488138, 909063924, 497814632, 140633959, 500203817, 360342268, 445467633, 477704894, 15361352, 220315555, 619476285, 950921904, 886367791, 189185798, 183160694, 659711657, 627029592, 112665948, 658051988, 648634412, 515148504, 24924703, 490594547, 201854810, 714542950, 602785661, 383539983, 536564768, 987492768, 587027873, 540968925, 498244660, 349158442, 88557443, 137723958, 627674755, 186876342, 377413248, 721254895, 701311697, 464980843, 825434906, 909994907, 450790541, 578501889, 931407997, 917054785, 869149237, 29257189, 14026097, 429313686, 775020958, 663028928, 60524820, 973597177, 999655403, 373165331, 160897667, 994649563, 251491102, 468275740, 134943782, 272400428, 403178049, 606290371, 298790432, 487696306, 484233736, 631964414, 758798349, 877363987, 85540895, 967541233, 405691356, 255015757, 718958090, 163918256, 609588933, 253217799, 427182496, 297334619, 285033600, 886988325, 380436491, 666193963, 126435007, 778326312, 903667127, 687840373, 880361885, 310561488, 780994727, 745208449, 106871663, 460676805, 937497705, 808221401, 291795339, 31122078, 949308837, 562350955, 222172784, 352239262, 278458293, 881629398, 883703942, 642656041, 766788263, 660830035, 73816861, 258979687, 327930043, 868826327, 918178049, 420185912, 109137213, 68821792, 384968057, 124910149, 80898773, 332388495, 219920198, 549570332, 489638900, 948597839, 952707502, 664458685, 826905865, 678979774, 629723420, 66425716, 810305229, 528398210, 842999153, 169382048, 487124857, 50096968, 184238535, 237452585, 634813513, 50106783, 403314167, 313482759, 498134475, 942437182, 170130670, 779446762, 743305004, 455852704, 590363951, 366230360, 964904140, 791415171, 351457024, 743110297, 285539671, 950624820, 199641625, 511558944, 216283487, 913142596, 886342412, 209131158, 786607494, 792630333, 191271328, 962389136, 411019481, 678612260, 78877143, 469516355, 44624214, 347853488, 444348057, 702180389, 825584362, 808066718, 649421951, 527998071, 372246707, 275346640, 273864415, 666283451, 587586574, 31051570, 488457940, 4518396, 810872144, 11541870, 529730086, 562850720, 810299187, 134899497, 863414291, 701755664, 37580494, 620187235, 566972095, 832270518, 914744892, 644210431, 229277629, 530537835, 37376309, 519199292, 784199509, 88822413, 980152392, 880351115, 52386628, 358816323, 303416646, 247871657, 794390809, 510618403, 3194064, 321052614, 684171275, 343286290, 393422020, 155860200, 226634637, 869751302, 326073683, 908403592, 906328261, 686898515, 928035288, 718245479, 744984158, 753416506, 312502450, 442383389, 997238270, 484811253, 652876718, 100550147, 100292593, 685477193]
invfacts = [1, 1, 500000004, 166666668, 41666667, 808333339, 301388891, 900198419, 487524805, 831947206, 283194722, 571199524, 380933296, 490841026, 320774361, 821384963, 738836565, 514049213, 639669405, 402087866, 120104394, 862862120, 130130097, 179570875, 799148792, 791965957, 761229465, 917082579, 282752951, 699405279, 123313510, 649139150, 957785605, 604781386, 958964165, 170256120, 671396008, 261389083, 243720767, 211377457, 230284438, 469031331, 654024560, 317535457, 393580354, 297635121, 202122504, 366002609, 861791727, 854322286, 57086446, 138374245, 98814890, 662241795, 956708188, 762849245, 960050886, 16842998, 379600744, 752196628, 279203279, 250478744, 971781922, 888440989, 92006891, 262953954, 367620517, 856233148, 659650492, 328400734, 261834298, 102279357, 626420551, 159266036, 785936033, 757145819, 470488764, 58058296, 590487931, 361904913, 517023815, 623666965, 775898383, 33444559, 512302915, 711909451, 833859418, 262458156, 412073391, 746203077, 108291146, 902288920, 444590100, 843490222, 455781814, 720587182, 986672790, 267903845, 992529638, 545379091, 875453797, 751242122, 732855320, 463425783, 917917562, 427789694, 494601793, 929856098, 360461633, 462022587, 631472937, 708391653, 979539218, 150261410, 966230370, 704054182, 781931507, 664802838, 73430533, 244314544, 735369293, 204424541, 157413317, 90710678, 403957347, 35231659, 341549460, 435760235, 26841877, 287029784, 832977158, 494908226, 18900820, 428713543, 234542640, 890626248, 477136961, 324650637, 415396022, 556945299, 311121040, 775256183, 97008847, 909769299, 860484515, 247313688, 97584341, 197942752, 622959077, 816261476, 218775078, 61051491, 388559552, 270513463, 930328016, 535034378, 939327150, 802161325, 87355452, 76021104, 300475134, 921120970, 141488402, 117432445, 836081911, 411127772, 279585109, 331015482, 251970332, 113916985, 971258342, 929656488, 889125916, 178549862, 909072132, 142337556, 23536009, 73579300, 595918989, 327351505, 474040845, 682177026, 267484491, 181789534, 164031466, 579265039, 169780996, 589143218, 907389066, 354007352, 970284256, 753771127, 915384231, 880390598, 520002017, 689846169, 600458403, 815230759, 706137534, 732191651, 538660962, 47456025, 599244836, 111326330, 657408467, 412962971, 375791085, 784424117, 527809735, 930755077, 237765502, 688330647, 526831752, 551769167, 745569020, 26723577, 264012611, 623336468, 599189621, 669402697, 589406380, 862395510, 571452236, 262652254, 206529699, 414251246, 621302001, 764851556, 933179180, 287917815, 979512693, 56188367, 340759435, 756827299, 7507809, 544712803, 794680992, 674239165, 82664871, 130052992, 267208556, 113141945, 12864223, 559723725, 842457890, 921805957, 885861006, 35975146, 40467642, 554379392, 778217523, 182383338, 405485651, 139942632, 890314741, 678001239, 811242198, 707436745, 425222626, 905116696, 126558142, 441097927, 852828624, 326436613, 232297110, 604650182, 671446058, 10005416, 522425397, 518670730, 38958040, 830402065, 800847072, 376559882, 110863358, 113130413, 279395402, 246496014, 986498194, 953356631, 314119133, 22470175, 961072596, 215410152, 155688065, 70721713, 297450078, 812883107, 541016959, 1872031, 644834046, 476442732, 755056316, 91314186, 326841207, 285853701, 396235995, 476081606, 270053967, 311939982, 581039804, 985319076, 135712978, 964144274, 904487323, 678375373, 515288812, 705261532, 807484621, 122354320, 419749533, 972410777, 211450036, 949557355, 18947635, 222282375, 48171780, 378700860, 623832397, 478444619, 510870143, 876980910, 810176965, 748638324, 113421724, 440348993, 863313960, 855851119, 438584915, 828080811, 720691159, 71663720, 48408626, 843989221, 837856261, 23396586, 696498209, 699396142, 558282241, 447074582, 748373754, 670816350, 949329879, 230172975, 253576086, 513778485, 518825953, 716192587, 608379868, 932975307, 856951364, 238908695, 952383270, 413462845, 749755550, 255633116, 371504590, 575270325, 736243777, 7621849, 202798951, 842667039, 502327813, 12403107, 546737375, 494648599, 151624724, 395508517, 384226928, 242233679, 35789821, 275029085, 239986639, 890723831, 812542048, 364833448, 745651158, 442296160, 329212426, 335960985, 66673582, 971303612, 458040065, 136966163, 279002518, 756568843, 351700958, 866541869, 396563255, 517728958, 965430081, 680218496, 838469951, 144627151, 576509210, 798927877, 640906388, 538138307, 199844570, 847618664, 622119051, 373122494, 767097325, 617288087, 395092300, 433074305, 67569149, 815890839, 568176207, 776450314, 850674275, 408395804, 136913583, 801784300, 794207214, 262154718, 34284026, 400561835, 433972639, 573828101, 184699592, 812790266, 404769648, 582517190, 392883298, 497395023, 656097176, 460552924, 608552698, 486267026, 331363414, 476406879, 202491684, 432338321, 344314146, 993894982, 649068571, 532377735, 925873015, 756095388, 83536581, 782502356, 467833719, 201958994, 113067476, 982276563, 417000623, 683259514, 595275137, 339855849, 540755239, 602085936, 629650637, 694546695, 783468170, 990732904, 300418276, 153830238, 781995268, 886235290, 762796169, 704474617, 834858176, 120593647, 291208178, 185572492, 867351020, 704212748, 633983365, 436319797, 679651749, 574691409, 884692149, 583265738, 954817023, 25168036, 437027667, 13494817, 926806481, 260807531, 473460019, 215121540, 398786562, 665421923, 247242609, 357210812, 375220601, 951489166, 260146496, 562904189, 803189606, 115688778, 402674167, 664102792, 62073083, 931438538, 989781133, 54305395, 845490579, 408508000, 817016, 770460718, 252530800, 193344993, 18240764, 451521272, 550299453, 675641621, 648967803, 128976362, 498292114, 586102337, 268722858, 813389329, 711699206, 345071263, 549118359, 498160774, 12544712, 899831499, 7499676, 159323417, 860458480, 925163407, 526574743, 431479193, 124394448, 736478932, 827152428, 468482333, 191449968, 570982019, 630772527, 6811956, 460686917, 587776989, 189529436, 618602480, 213045731, 31935150, 166725807, 46518902, 361709447, 728106284, 141044314, 106680816, 648547039, 81624401, 345039463, 428679492, 444415784, 871949944, 552304261, 263204892, 812749473, 93356306, 615275825, 658196191, 99745872, 808765204, 980015659, 506203240, 798053748, 875307384, 490913669, 395559142, 537801345, 254916759, 26857248, 323421544, 786532324, 111710215, 362083412, 98363148, 686582519, 232498406, 816375871, 302974657, 320593384, 541140925, 837139904, 84057040, 831759554, 589762885, 489023570, 342716282, 966455154, 672855976, 456926629, 511811424, 370359005, 435482844, 480465346, 749545478, 742002607, 688642026, 635383632, 287496457, 895129599, 639223927, 732732045, 883082755, 597812434, 281256739, 243843142, 932634458, 133552203, 978803223, 605228299, 76527469, 923076281, 353392926, 363322540, 770576388, 900277818, 11219964, 45472760, 708339507, 491437446, 743928014, 675393437, 584018351, 629556304, 639854830, 305512590, 408488823, 110876181, 497784495, 617034693, 851537422, 102938949, 385266150, 668331122, 814641919, 630622468, 978945869, 28268783, 357972167, 146329111, 973624935, 149958790, 433931296, 25598024, 447940280, 354732829, 764891064, 685394573, 585294277, 465409408, 469130064, 920721745, 182673921, 284022508, 597678446, 416816025, 588422624, 98457962, 240636924, 36839874, 300511140, 182273503, 581213731, 455560749, 864940520, 856724314, 261438685, 740632796, 674273817, 942626165, 174802133, 374887767, 194299387, 742848665, 907493095, 441999251, 492506669, 611675310, 290416066, 970929824, 883609623, 223358251, 807963821, 422005815, 659475855, 461490465, 664907290, 263359925, 173600234, 665950005, 716496304, 824226812, 899890349, 390028746, 771125588, 145203352, 452007490, 325362082, 146808268, 736600017, 245688986, 146065271, 957412368, 898799739, 278661168, 704941285, 610928999, 81601883, 483849511, 959722958, 846205539, 512459448, 477514011, 94771790, 785546670, 950680044, 61469483, 942823288, 676349828, 399270685, 202224300, 83614201, 27855221, 178708942, 736070142, 898806733, 147446631, 252269212, 554679879, 911476215, 87670064, 942585856, 185967971, 834953514, 366759830, 422843000, 170643325, 93981853, 572719111, 985870900, 598086433, 218375794, 859943833, 859649526, 91331965, 695015236, 607644320, 732718027, 917982226, 747216559, 979635810, 561306185, 34036360, 223449518, 94586255, 423202372, 442944642, 611697021, 200279654, 277309078, 618283679, 820550379, 353246455, 521460957, 68835467, 668938271, 630939793, 166620027, 751195077, 59571869, 663276431, 490471791, 292464946, 386389206, 728831039, 100424847, 231097324, 77617394, 253639149, 723976405, 560621283, 219949516, 322944880, 693507607, 78791198, 119998459, 265121019, 385833490, 175839688, 127126701, 357575575, 462477947, 523972795, 85257542, 474256318, 882209397, 465260644, 945308123, 444097002, 744917420, 375150087, 199218939, 962795536, 153320195, 574288074, 366385933, 970641480, 460261345, 165378268, 54660122, 796112070, 75056929, 684432874, 318576890, 508386937, 736496795, 933419021, 301388996, 795962538, 981413164, 518902828, 825023058, 764707707, 274652931, 632168477, 715573025, 516018880, 296024238, 427201967, 100757491, 425935778, 453525227, 714143838, 325377579, 154052075, 164453301, 661274799, 281891479, 854578132, 707463702, 54478503, 560779145, 542878457, 842687510, 21165703, 595996646, 257510057, 793448599, 603061927, 924060221, 392136705, 100461338, 471328395, 891398279, 205030949, 652464912, 835850842, 87425060, 823905986, 380913646, 278673941, 927068232, 520240501, 876473603, 136589194, 511732167, 687296805, 683241687, 350269024, 968145478, 892943787, 218267753, 631708693, 575265725, 844874308, 490669196, 539989340, 283721451, 422216333, 634877244, 154305891, 30857166, 70409600, 192823595, 593649861, 218997343, 408157062, 510618691, 46798894, 349151803, 787794327, 112121118, 212247051, 734542883, 558493333, 135971470, 553224553, 555304942, 877988083, 353984399, 287379295, 128097089, 213238733, 686489183, 584370424, 478522537, 386164116, 728903056, 854166382, 496535429, 200766267, 471649197, 622910706, 125683017, 956326056, 20739963, 301662013, 197927580, 561829805, 470110929, 409651919, 25445274, 530972257, 693634465, 812235796, 433779479, 246955439, 273484835, 533196859, 434841810, 150091327, 794785050, 966482053, 130865325, 820075960, 424860898, 894572050, 601383094, 45465724, 85336318, 672082365, 48587322, 356055887, 859189025, 162098823, 439790362, 893587086, 428005909, 694221764, 21829348, 71677376, 928496509, 456286540, 290395261, 680262749, 924193154, 292067220, 171853628, 296940288, 150623112, 455840069, 180683168, 811842548, 508120422, 642272196, 544234726, 650304911, 229451663, 921643700, 798472778, 749018037, 226545381, 765423842, 718894474, 717080061, 749196186, 489999179, 806854513, 378512648, 701818525, 88561613, 592947516, 719258871, 280773178, 426531817, 513644853, 265496088, 511425456, 854621511, 704306302, 284837521, 431600849, 280960245, 932742910, 291976581, 677356118, 77062670, 110519140, 832608350, 207247104, 180387636, 52180388, 623428756, 387847736, 784035746, 353370556, 902839181, 7855705, 291964109, 433821396, 645623217, 653114483, 803811197, 899015630, 881440298, 612309117, 704051541, 525299267, 338766275, 893260091, 835027739, 493955913, 741913772, 478221054, 317183014, 709294129, 149960288, 300341094, 154138600, 902873682, 630615042, 402553998, 895637789, 935945392, 681448161, 355591345, 343338738, 967512882, 916072825, 984504894, 522602992, 754348662, 579975363, 204971187, 68269388, 616923634, 343174092, 457307053, 322308796, 27025104, 796975244, 722663791, 869384082, 854438584, 72986172, 958323523, 850197469, 490388448, 851930364, 530105798, 594457139, 965655155, 978289974, 921177, 159925609, 392067602, 154358750, 390388707, 362127827, 965694883, 326441251, 651706959, 759712150, 901828096, 85649421, 511252936, 351173261, 584898864, 36754781, 526008125, 156187219, 928848328, 969406897, 419565074, 999464056, 41512421, 412019830, 363178658, 93250395, 517548947, 368702986, 20521746, 372154468, 256751059, 62448995, 719435516, 16182133, 384138855, 496248079, 12291665, 204742760, 836549772, 897217581, 239471161, 496137330, 842840710, 489450538, 920876544, 846360328, 834698887, 428164745, 437322674, 837477344, 65501329, 828450591, 109361267, 106824540, 656009704, 581607891, 978158869, 7129722, 923220658, 489672814, 228600423, 270907037, 851664514, 332312593, 871520710, 333515105, 717494256, 336330821, 564014456, 400145020, 353485, 427184781, 489794699, 38317000, 274681619, 99625930, 399033066, 384898188, 768758688, 60270604, 907233168, 153024702, 816567335, 860975174, 604590733, 770361462, 667918438, 823905940, 113759919, 883678338, 16392082, 65061919, 245290350, 233978608, 958679919, 914398174, 999062527, 735115676, 528219931, 686070823, 479936381, 147446206, 122119800, 115984653, 229087467, 619733584, 658064845, 722547537, 828822696, 427693276, 522549230, 580155630, 101005244, 326043411, 941603785, 634614791, 539587962, 656946220, 254794024, 980740730, 327394876, 181172778, 751842212, 227638687, 542350458, 812588338, 221222719, 723482951, 384641585, 112833453, 279457077, 823369207, 343235655, 799450412, 512374126, 981213352, 735376644, 520212995, 929600184, 779291929, 249400411, 866375235, 63011940, 506276362, 8711672, 602327023, 224836365, 484056940, 66515750, 179245679, 236946574, 198876297, 312354925, 761573960, 375626297, 840900274, 900526197, 86054575, 799250870, 361014950, 378364172, 308567757, 252703080, 28777717, 960056106, 692713987, 478577132, 176955719, 165184518, 48062701, 250850702, 797445951, 53320459, 289921719, 857030687, 177734060, 179465053, 32428947, 531477769, 206713521, 790021514, 184062770, 381176902, 304723839, 736199623, 273244749, 632430489, 512916281, 854010339, 552241419, 137022558, 252304090, 816788127, 358419754, 243915941, 846653877, 411642812, 350604961, 505833817, 775976083, 316779698, 87345036, 617157714, 718274438, 144327232, 105086289, 303710638, 329632556, 616007589, 297888285, 960139856, 745451804, 642657345, 659327579, 357099789, 414531796, 778102143, 69412121, 825835484, 627498705, 213437988, 286994108, 184024140, 54617918, 615905617, 458132020, 127684886, 193272061, 819529674, 252377639, 866294416, 750863342, 706917210, 70043952, 592646643, 284188627, 962468565, 363327538, 743356411, 308795818, 754461446, 466427065, 123823948, 196263468, 819445843, 114628498, 466448496, 895696300, 840378400, 845797396, 284181250, 349797551, 401331660, 315894551, 90665574, 321253355, 770349970, 529772824, 703431651, 155717966, 217969531, 39469365, 15890838, 615861054, 63812867, 660183737, 531370624, 542912999, 273340538, 879243688, 643302740, 911210286, 774296265, 483726068, 410541714, 834263687, 412432188, 154154170, 67279220, 972458828, 724634, 900968528, 488765605, 372110609, 965358187, 645111629, 158490440, 159494805, 100118145, 135529326, 957200842, 970404442, 764379920, 701671134, 438570557, 296564903, 34828104, 306868897, 6843286, 867014586, 687861249, 853769530, 826139133, 411594244, 795323281, 198826134, 57162885, 737076092, 368421226, 841260707, 924082558, 813491690, 290257274, 49665642, 181722142, 785171917, 439611884, 937954765, 888360843, 970230536, 429066740, 806528615, 855351544, 757296288, 364182756, 595071513, 130832185, 56969642, 132415087, 250993830, 383801004, 627698354, 726418727, 548190985, 15435667, 71593011, 495759369, 883842579, 288488461, 799634901, 777317862, 972756470, 848271200, 242596636, 270442816, 393227041, 620307694, 397885246, 37161621, 918523863, 603341735, 812882767, 117265123, 234005136, 593385601, 738598019, 215612553, 943069501, 660523293, 879423316, 75161339, 454023307, 654110976, 619406398, 4641940, 966366259, 778687937, 607962697, 160565010, 721286214, 987933866, 175846431, 901796273, 381116237, 237730584, 689100722, 167377679, 32082959, 182661170, 719071942, 316726127, 427800922, 79243630, 294172489, 162720729, 95482185, 299099092, 332159491, 542987700, 111332177, 144016070, 521090173, 775461553, 867199636, 684661543, 83517270, 448616956, 740540524, 910096267, 459212937, 549561709, 122726974, 228225908, 17903226, 506151370, 50106443, 451669013, 774303388, 970594771, 844983415, 858590348, 223936587, 477085442, 352187857, 854574659, 783246163, 809054976, 978234662, 523633946, 404810019, 556953317, 831798356, 493821970, 17167557, 619796214, 549172698, 318917457, 740979802, 962913416, 406413761, 443301889, 489915142, 806218155, 237997472, 679303479, 697848571, 949063991, 304168824, 112202780, 245910863, 691908068, 343108391, 191052600, 807435921, 843165634, 857891954, 996590121, 722330416, 915710159, 610136146, 864160149, 120201032, 286737255, 911080361, 616036337, 239034963, 729406484, 789815283, 428809092, 791208953, 446643373, 794777841, 951308916, 860951684, 522189356, 897525998, 695613569, 264025910, 836773879, 19488422, 37871729, 392718771, 656709730, 518343137, 527030175, 714070942, 831413576, 72015214, 362384428, 699131987, 945330183, 891733856, 782960973, 722836873, 936431337, 635382313, 295630094, 273915838, 462112207, 204037469, 663146936, 145307887, 151316158, 659904388, 535128477, 570671249, 886759102, 862659890, 801835044, 944139555, 886007778, 157956500, 184244219, 861459587, 574624180, 370500720, 439011802, 612771841, 826504956, 250048700, 463263393, 952614923, 996157958, 83807085, 368708002, 83937038, 643906175, 892744722, 781577692, 754447556, 391121651, 47625472, 494979565, 899365924, 855548156, 718245467, 758008976, 817972321, 269067909, 161074211, 589925302, 400244777, 647051601, 851189380, 942889223, 9983024, 428041294, 55302090, 456284567, 87730347, 485073493, 32117950, 243162170, 498593874, 2801117, 944619049, 613149643, 352773868, 177858867, 946106685, 787807764, 537376202, 611237536, 716787149, 13438606, 449606335, 201143145, 935269397, 833293382, 872198213, 823595689, 557500679, 975096990, 572907756, 790020244, 794585144, 39800114, 712117746, 602890874, 299572590, 253860034, 567822331, 692513972, 146600927, 380896458, 907990780, 772227106, 286621251, 748345506, 784733915, 412779987, 449429571, 461952211, 642834018, 270135381, 18378953, 486054845, 586104343, 273688550, 470789639, 79582803, 261391159, 55176174, 690667785, 614547509, 646116207, 192790180, 971785896, 333115536, 920128312, 24621016, 613965501, 984143015, 264855343, 258862460, 757203882, 97576262, 416475483, 917015860, 329693010, 489431638, 18822135, 66319488, 472278403, 987751963, 616569922, 683323348, 141562433, 453060457, 861661553, 872688271, 152627861, 45815100, 584596927, 214462989, 182106974, 790392249, 121249493, 947409030, 915994926, 32456262, 416439729, 900481966, 969262828, 177458293, 401400980, 983746415, 638012804, 16845890, 262208612, 100036551, 142160915, 119214884, 48750273, 768492825, 111170764, 597254788, 478406823, 82735911, 404490205, 872315713, 283054477, 406816254, 305193481, 623138229, 670135787, 491076916, 967708603, 774399836, 973140274, 598706822, 578989387, 693491298, 195184634, 699997215, 574232776, 967924910, 373607825, 407730412, 524210131, 678709133, 561845768, 160646971, 629487409, 729049249, 814466931, 218535368, 890292436, 30396720, 270551637, 968582413, 495105329, 170582057, 403536153, 259681294, 31058776, 665921663, 365160621, 684208668, 148306231, 798600637, 136793270, 452757582, 390001574, 771292717, 469989356, 172053465, 827272350, 972060957, 881301574, 274052954, 919610927, 101995245, 801757510, 840771103, 420396591, 850350909, 935472223, 407873151, 486396318, 836617611, 398103002, 497405924, 827322488, 221186557, 531919636, 501986460, 7027536, 995509573, 605836899, 540744020, 266708215, 999588969, 750139831, 757978807, 966288747, 391480030, 950470370, 615056133, 223123986, 590526301, 464356125, 904941119, 570420584, 824371064, 634292921, 325714292, 164161043, 139535646, 57823174, 877945524, 707641683, 627332400, 623616255, 792704112, 121080634, 598518301, 505029588, 738400574, 70534733, 75645991, 869319171, 267844169, 946704053, 311644663, 497144552, 126786109, 985776140, 626915266, 384748446, 661023467, 40406486, 494539700, 726298383, 841033028, 504018084, 149072221, 530425959, 34716080, 127817978, 599414752, 356028052, 909681592, 433193290, 254048582, 908684845, 318775130, 389515378, 383907348, 923619728, 112336385, 453126610, 827794543, 261153278, 164821861, 343889998, 570532412, 736922954, 393911853, 663097742, 616988718, 468222879, 914492036, 519091374, 533684859, 560868978, 636469794, 516749046, 571245568, 532279018, 954098975, 40233011, 400772660, 40429369, 151682975, 890815048, 679277743, 384526101, 249938251, 363041124, 532245218, 632425122, 763411118, 534273823, 805721900, 133087759, 205076193, 118257093, 521871417, 899798981, 825664086, 124177199, 496350416, 844825656, 103311149, 58348337, 81069041, 175797285, 436600954, 868554528, 970860765, 125710968, 457299745, 372272984, 168972719, 475576689, 613000835, 369464458, 213878667, 678176690, 868915977, 965249043, 266788473, 593840838, 41234964, 277420681, 95009131, 533837096, 189808293, 869801057, 595120193, 228225365, 12135959, 416716523, 141657995, 451821421, 829745481, 855565272, 12945607, 192614757, 645781802, 399191777, 341683574, 113424252, 984482574, 248045919, 310813304, 144277250, 943079943, 860664470, 808934097, 237355891, 551829040, 873670202, 832062852, 769144075, 366237951, 250317814, 926933160, 561528563, 821607384, 541853636, 109332230, 74606341, 240017785, 247170016, 568915389, 306602832, 243234157, 796639285, 507067954, 731954469, 68440100, 951441664, 254065156, 368550879, 507338385, 684791908, 284022855, 145478850, 241664364, 105573951, 123780843, 285559178, 836360921, 91426722, 277485483, 715224731, 465845295, 663858881, 840600340, 337983074, 320333327, 754086250, 442689318, 543471268, 518980525, 523758963, 692688772, 282530385, 482988162, 84963686, 785325088, 711226869, 775282597, 610858224, 382601038, 269171747, 426768431, 761640773, 749880347, 535248313, 354832123, 692408442, 265877962, 259021473, 890520037, 192041282, 337096023, 977679715]

def ncr(n, r, k):
	su = 0
	for i in range(k, r + 1):
		su += facts[n] * invfacts[i] * invfacts[n - i] % mod
	return su % mod
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	s = pow(2, n - 1, mod)
	(i, count) = (0, 1)
	while i < n - 1:
		if arr[i] == arr[i + 1]:
			count += 1
		elif count > 1:
			for it in range(2, count + 1):
				s += ncr(n - it, i + 1 - it, i - count + 1)
			s %= mod
			count = 1
		i += 1
	if count > 1:
		for it in range(2, count + 1):
			s += ncr(n - it, i + 1 - it, i - count + 1)
	print(s % mod)


import math
import collections
import bisect
import heapq
import time
import itertools
import sys
from functools import reduce
import operator as op
memo = {}

def ncr(n, m):
	if m > n:
		return 0
	m = min(m, n - m)
	key = (n, m)
	if key in memo:
		return memo[key]
	ans = -1
	prekey = (n, m - 1)
	if prekey in memo:
		preval = memo[prekey]
		ans = preval * (n - m + 1) // m
	else:
		numer = reduce(op.mul, range(n, n - m, -1), 1)
		denom = reduce(op.mul, range(1, m + 1), 1)
		ans = numer // denom
	memo[key] = ans
	return ans
MOD = 10 ** 9 + 7

def solve(A):
	ans = 0
	A = list(sorted(collections.Counter(A).items()))
	N = len(A)
	if max([v[1] for v in A]) == 1:
		for i in range(1, N + 1, 2):
			ans += ncr(N, i)
			ans %= MOD
		return ans
	(left, right) = ([0] * (N + 1), [0] * (N + 1))
	for i in range(N):
		left[i + 1] = left[i] + A[i][1]
	for i in range(N - 1, -1, -1):
		right[i] = right[i + 1] + A[i][1]
	for (i, v) in enumerate(A):
		(l, m, r) = (left[i], v[1], right[i + 1])
		nrcs = [1] * (r + 1)
		for c in range(1, r + 1):
			nrcs[c] = nrcs[c - 1] + ncr(r, c)
		for b in range(1, m + 1):
			nb = ncr(m, b)
			for a in range(min(l, r + b - 1) + 1):
				mxc = min(a + b - 1, r)
				na = ncr(l, a)
				nc = nrcs[mxc] - (nrcs[a - b] if a - b >= 0 else 0)
				ans += na * nb * nc
				ans %= MOD
	return ans % MOD
T = int(input())
for ti in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	print(solve(A))


import operator as op
from functools import reduce

def ncr(n, r):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom
for test in range(int(input())):
	n = int(input())
	mod = 1000000007
	res = 2 ** (n - 1) % mod
	l = [int(j) for j in input().split()]
	sor = sorted(l)
	for i in range(n):
		l = 0
		for j in range(i + 1, n):
			if sor[i] == sor[j]:
				l += 1
			else:
				break
		if l > 0:
			res += (ncr(n - 1, i + 1) - ncr(n - l - 1, i + 1)) % mod
		res = res % mod
	print(res % mod)


import bisect
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 2001):
	fact.append(fact[i - 1] * i)

def func1(right, left, freq):
	aa = left + right + freq
	ab = left + right
	val1 = fact[aa + 1] // (fact[left + 1] * fact[aa - left])
	val2 = fact[ab] // (fact[left + 1] * fact[ab - left - 1])
	return val1 - val2

def calc(aa, left, freq):
	val1 = fact[aa + 1] // (fact[left + 1] * fact[aa - left])
	sec = aa - freq
	val2 = fact[sec + 1] // (fact[left + 1] * fact[sec - left])
	return val1 - val2

def func2(right, left, freq):
	aa = left + right + freq
	nosf = right + freq - left + 1
	val1 = 0
	if nosf >= 0:
		val1 = calc(aa, left, nosf)
	start = min(freq + right, left - 1)
	fir = left + start
	las = right + left
	sum1 = fact[fir + 1] // (fact[start] * fact[fir + 1 - start])
	sum2 = fact[las] // (fact[right - 1] * fact[las - right + 1])
	return val1 + sum1 - sum2
for i in range(int(input())):
	a = int(input())
	v = list(map(int, input().split()))
	v.sort()
	hash = [False] * 2005
	for j in range(a):
		hash[v[j]] = True
	list1 = []
	sum1 = 0
	for j in range(a):
		x1 = bisect.bisect_right(v, v[j], 0, len(v))
		if x1 == j + 1:
			continue
		right = a - x1
		left = j
		freq = x1 - j - 2
		if right >= left:
			val = func1(right, left, freq)
		else:
			val = func2(right, left, freq)
		sum1 += val
	for j in range(a + 1):
		if j % 2 == 1:
			sum1 = (sum1 + fact[a] // (fact[j] * fact[a - j]) % mod) % mod
	print(sum1 % mod)


def generate_binfac_products():
	pList = [[0 for j in range(1000)] for i in range(1000)]
	for r in range(1, 500):
		for c in range(r, 999 - r):
			tmp = (pList[r][c - 1] + pList[r - 1][c] + 1) % 1000000007
			(pList[r][c], pList[c][r]) = (tmp, tmp)
	return pList

def calc_good_subseq():
	ctr = pow(2, N - 1, 1000000007)
	for i in range(N - 1):
		(preCtr, eqCtr, postCtr) = (i, 1, N - (i + 1))
		while postCtr and A[i + eqCtr] == A[i]:
			ctr += 1
			ctr += binFacList[preCtr][postCtr - 1]
			eqCtr += 1
			postCtr -= 1
	return str(ctr % 1000000007)
binFacList = generate_binfac_products()
T = int(input())
opList = []
for x in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	opList.append(calc_good_subseq())
print('\n'.join(opList))


from collections import defaultdict
from itertools import combinations
mod = 10 ** 9 + 7

def binomial(n, k):
	if 0 <= k <= n:
		(num, den) = (1, 1)
		for t in range(1, min(k, n - k) + 1):
			num *= n
			den *= t
			n -= 1
		return num // den % mod
	else:
		return 0

def sum_nC3(n):
	n += 1
	return binomial(n, 4)

def sum_nCr(n, r):
	n += 1
	return binomial(n, r + 1)

def brute():
	results = []
	for _ in range(1):
		A = [1] * 10 + [2] * 4 + [3] * 10 + [4] * 2 + [5] * 3
		A.sort()
		N = len(A)
		res = pow(2, N - 1, mod)
		if len(set(A)) != N:
			for i in range(2, N + 1, 2):
				for combi in combinations(A, i):
					if combi[i // 2 - 1] == combi[i // 2]:
						res += 1
		results.append(res)
	print('\n'.join((str(k) for k in results)))

def solve():
	results = []
	for _ in range(int(input())):
		N = int(input())
		arr = [int(k) for k in input().split()]
		arr.sort()
		freq = defaultdict(int)
		pos = dict()
		for i in range(N):
			freq[arr[i]] += 1
			if arr[i] not in pos:
				pos[arr[i]] = [i, 0]
			pos[arr[i]][1] = N - i - 1
		if len(freq) == N:
			results.append(pow(2, N - 1, mod))
			continue
		ans = pow(2, N - 1, mod)
		if len(freq) == 2 and 1 in freq.values():
			for x in range(max(freq.values()) - 1, 0, -1):
				ans = (ans + pow(2, x, mod) - 1) % mod
			results.append(ans)
			continue
		for (num, val) in freq.items():
			if val > 1:
				(left, right) = pos[num]
				for x1 in range(0, val - 1):
					ans = (ans + sum_nCr(right + left + val - 2, right + x1) - sum_nCr(right + left + x1 - 1, right + x1)) % mod
		results.append(ans)
	print('\n'.join((str(k) for k in results)))
solve()


from collections import Counter
from bisect import bisect

def make_pairs(l1, l2, n):
	(x, y, c, tot) = (0, 0, 0, 0)
	M = 10 ** 9 + 7
	las2_ind = bisect(l2, n - l1[0] - 2) - 1
	c = (las2_ind + 1) * (las2_ind + 2) // 2
	l1 = l1[0:las2_ind + 1]
	las2 = l2[las2_ind]
	xx = l1[0] + las2 + 1
	for i in l1:
		yy = i + 1
		tot = tot % M + ncr(xx, yy, M)
	(zz1, zz2) = (ncr(l1[-1] + l2[0] + 1, l2[0], M), ncr(l1[0] + l2[0], l1[0], M))
	zz = zz2 - zz1
	tot += zz
	tot %= M
	return [tot, c]

def ncr(n, r, p):
	if n < r:
		return 0
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
for _ in range(int(input())):
	M = 10 ** 9 + 7
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	fre = dict(Counter(a))
	f = list(set(a))
	total = pow(2, n - 1, M)
	for x in f:
		ind = a.index(x)
		freq = fre[x]
		if freq >= 2:
			(min1, min2, max1, max2) = (ind, n - ind - freq, ind + freq - 2, n - ind - 2)
			(l1, l2) = (list(range(min1, max1 + 1)), list(range(min2, max2 + 1)))
			lis = make_pairs(l1, l2, n)
			(total, xx) = (total + lis[0], lis[1])
			total -= xx
			total = total % M + ncr(freq, 2, M)
	print(total % M)


p = 10 ** 9 + 7
import functools

def power(x, y, p=10 ** 9 + 7):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	if r > n:
		return 0
	else:
		r = min(r, n - r)
		a = functools.reduce(lambda x, y: x * y, range(n, n - r, -1), 1)
		b = functools.reduce(lambda x, y: x * y, range(1, r + 1), 1)
		return a // b

def sum(n, x, i):
	if x < 2:
		return 0
	a = ncr(n - x, i) % p - ncr(n - 1, x + i - 1) % p
	for j in range(1, x):
		a = (a + ncr(n - 1, i + j) % p) % p
	return a
t = int(input())
for i in range(t):
	n = int(input())
	inp = list(map(int, input().split()))
	ans = power(2, n - 1)
	inp.sort()
	count = []
	dist = []
	dist.append(inp[0])
	x = 1
	for j in range(1, n):
		if inp[j] == inp[j - 1]:
			x = x + 1
		else:
			dist.append(inp[j])
			count.append(x)
			x = 1
	count.append(x)
	h = 0
	s = 0
	for j in range(len(dist)):
		s = (s + sum(n, count[j], h)) % p
		h = h + count[j]
	ans = (ans + s) % p
	print(ans)