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

Chef is playing a card game with his friend Chefu. The rules of the game are as follows:
There are two piles of cards. One pile belongs to Chef and the other to Chefu. One pile may be empty.
At any moment, each card used in the game has a positive integer value. Whenever the value of a card becomes non-positive, it is removed from the game.
The game is played in rounds. In each round, each player simultaneously draws one card from the top of his pile.
If one player's pile is empty, this player cannot draw a card and therefore loses the game. (Note that it is impossible for both piles to be empty.)
If the values of the drawn cards are equal, each player simply places the card he drew to the bottom of his pile.
Otherwise, the player whose card has the higher value wins this round. This player places the card he drew to the bottom of his pile. Then, the card his opponent drew is transferred to him and he places this card to the bottom of his pile (below the card he just drew) as well.
Whenever a card is transferred from one player to the other, the value of that card decreases by $1$.
When there is no transfer of cards between the players during $10^{100}$ consecutive rounds, each player calculates the sum of values of the cards that are currently in his pile. If one player has a higher sum, this player wins the game. Otherwise, the game ends in a draw.

You are given $N$ cards (numbered $1$ through $N$). For each valid $i$, the value of the $i$-th card is $C_{i}$. Your task is to distribute the cards between the players before the start of the game ― assign each card to one of the players. It is not necessary to distribute the cards equally between the players in any way. After you distribute the cards, each player arranges the cards in his pile in some order he chooses (not necessarily good for this player). Once the game starts, they may not rearrange their piles anymore.

Find the number of distributions of cards such that it is impossible for the game to end in a draw, regardless of how the players form their starting piles. Since this number might be large, compute it modulo $1,000,000,007$. Two distributions of cards are different if there is an integer $i$ ($1 ≤ i ≤ N$) such that the $i$-th card belongs to Chef in one distribution and to Chefu in the other distribution.

------  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 $C_{1}, C_{2}, \ldots, C_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of ways to distribute the cards between the players such that the game does not end in a draw, modulo $1,000,000,007$.

------  Constraints ------
$1 ≤ T ≤ 200$
$1 ≤ N ≤ 10^{5}$
$1 ≤ C_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (5 points): $N ≤ 8$

Subtask #2 (25 points): $N ≤ 200$

Subtask #3 (70 points): original constraints

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

2

2 2

4

1 2 2 6
----- Sample Output 1 ------ 
2

16
----- explanation 1 ------ 
Example case 1: We can only give both cards to Chef or both to Chefu. If we gave one of them to Chef and the other to Chefu, the game would end in a draw.

Example case 2: One of the possible ways to avoid a draw is to give cards $1$ and $4$ to Chef and the rest to Chefu. Let's assume that Chef forms a pile with cards $[6,1]$ (from top to bottom); Chefu's pile is $[2,2]$. Then, the game proceeds like this:
- In the first round, Chef draws the card with value $6$ and wins a card with value $2$ from Chefu, so his pile is $[1,6,1]$ and Chefu's pile is $[2]$ after this round. Note that the value of the card transferred from Chefu to Chef decreased to $1$.
- In the second round, Chef draws a card with value $1$ and Chefu draws his card with value $2$, so Chefu wins the round. The value of the card that is transferred from Chef to Chefu decreases to $0$, so this card is removed from the game. After this round, Chef's pile is $[6,1]$ and Chefu's pile is $[2]$.
- In the third round, Chef again draws the card with value $6$ and wins Chefu's last card. After this round, Chef's pile is $[1,6,1]$ and Chefu's pile is empty. Therefore, Chefu loses the game.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
p = 10 ** 9 + 7

def power(a, n):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * a % p
			n -= 1
		else:
			a = a * a % p
			n = n // 2
	return res
n = 10 ** 5 + 1
f = [0] * n
f[0] = f[1] = 1
for i in range(2, n):
	f[i] = i * f[i - 1] % p

def c(n, k):
	res = f[n]
	res = res * pow(f[k], p - 2, p) % p
	res = res * pow(f[n - k], p - 2, p) % p
	return res % p
for _ in range(int(input())):
	n = int(input())
	max1 = 0
	l = []
	for i in map(int, input().split()):
		max1 = max(i, max1)
		l.append(i)
	x = l.count(max1)
	if x % 2 == 1:
		ans = pow(2, n, p)
	else:
		temp = (pow(2, x, p) - c(x, x // 2) + p) % p
		ans = pow(2, n - x, p) * temp % p
	print(ans)


from collections import Counter
mod = 1000000007

def fast_pow(base, power):
	ans = 1
	while power > 0:
		if power & 1:
			ans = ans * base % mod
		power >>= 1
		base = base * base % mod
	return ans

def combinations(a, b):
	x = y = 1
	for i in range(b):
		x = x * (a - i) % mod
	for i in range(1, b + 1):
		y = y * i % mod
	return x * fast_pow(y, mod - 2) % mod
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	cnt = Counter(c)
	m = cnt[max(c)]
	if m & 1:
		print(fast_pow(2, n))
	else:
		a = combinations(m, m // 2)
		b = fast_pow(2, n - m)
		c = fast_pow(2, m)
		print((c - a) % mod * b % mod)


mod = 10 ** 9 + 7
fact = {0: 1}
for i in range(1, 10 ** 5 + 1):
	fact[i] = i * fact[i - 1]
	fact[i] %= mod

def C(n, r):
	den = fact[r] * fact[n - r] % mod
	den_inv = pow(den, mod - 2, mod)
	return fact[n] * den_inv % mod
for case in range(int(input())):
	N = int(input())
	Cards = list(map(int, input().split()))
	m = max(Cards)
	f = Cards.count(m)
	if f % 2:
		print(pow(2, N, mod))
	else:
		ans = pow(2, N, mod)
		ways = C(f, f // 2) * pow(2, N - f, mod) % mod
		ans = (ans - ways) % mod
		print(ans)


p = 10 ** 9 + 7

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

def ncr(n, r, p):
	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 i in range(int(input())):
	n = int(input())
	l = [int(c) for c in input().split()]
	m = max(l)
	x = l.count(m)
	if x % 2 == 1:
		print(power(2, n, p) % p)
	else:
		t = power(2, n, p) % p - power(2, n - x, p) % p * ncr(x, x // 2, p) % p % p
		if t < 0:
			t = (t + p) % p
		print(t % p)


mod = 10 ** 9 + 7
t = int(input())
for x in range(t):
	count = 0
	combo = 0
	combo1 = 0
	n = int(input())
	values = [int(s) for s in input().split()]
	maximum = max(values)
	combination = pow(2, n, mod)
	for i in values:
		if i == maximum:
			count += 1
	if count % 2 == 1:
		print(combination)
	else:
		combo = pow(2, n - count, mod)
		p1 = 1
		p2 = 1
		for l in range(count // 2 + 1, count + 1):
			p1 = p1 * l % mod
		for j in range(1, count // 2 + 1):
			p2 = p2 * j
		p2 = pow(p2, mod - 2, mod)
		factorial = p2 * p1 % mod
		combo2 = combo * factorial % mod
		print((combination - combo2) % mod)


mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	ret = power(a, b // 2) % mod
	ret = ret * ret % mod
	if b % 2 != 0:
		ret = ret * a % mod
	return ret

def divide(a, b):
	return a % mod * (power(b, mod - 2) % mod) % mod

def comb(n, r):
	ret = 1
	k = min(r, n - r)
	for i in range(k):
		ret = ret % mod * (n - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod
t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	if n == 1:
		print(2)
		t -= 1
		continue
	c = l.count(max(l))
	if c % 2 != 0:
		ans = power(2, n) % mod
	else:
		ans = power(2, n) % mod - power(2, n - c) % mod * comb(c, c // 2) % mod % mod
	if ans < 0:
		ans = (ans + mod) % mod
	print(ans % mod)
	t -= 1


prime = 10 ** 9 + 7
for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	total = pow(2, n, prime)
	m = max(arr)
	k = arr.count(m)
	if k % 2 == 1:
		print(total)
	else:
		x = pow(2, n - k, prime)
		n = 1
		d = 1
		for i in range(k // 2 + 1, k + 1):
			n = n * i % prime
		for i in range(1, k // 2 + 1):
			d = d * i
		d = pow(d, prime - 2, prime)
		ways = n * d % prime
		ways = x * ways % prime
		print((total - ways) % prime)


def combination(a, b):
	ans = 0
	ans += factorial(a) // factorial(b) ** 2
	return ans
M = 1000000007
from math import factorial
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = l.count(max(l))
	if count & 1:
		print(pow(2, n, M))
	else:
		ways = pow(2, n - count, M) * combination(count, count // 2)
		x = pow(2, n, M)
		print((x - ways) % M)


import math
m = 1000000007

def pow(x, y):
	an = 1
	if x == 0:
		return 1
	while y > 0:
		if y % 2 != 0:
			an = an * x % m
			y = y - 1
		x = x * x % m
		y = y / 2
	return an % m

def comb(a, b):
	p = math.factorial(a) % m
	x = pow(math.factorial(b), m - 2) % m
	y = pow(math.factorial(abs(a - b)), m - 2) % m
	an = x * y * p % m
	return an
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = l.count(max(l))
	if f % 2 != 0:
		d = 0
	else:
		x = comb(f, f // 2) % m
		y = pow(2, n - f) % m
		d = x % m * (y % m) % m
	an = (pow(2, n) - d) % m
	print((an + m) % m)


mod = 10 ** 9 + 7
N = 1000001
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)

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

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

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

def nCr(N, R, mod):
	ans = fact[N] * factorialNumInverse[R] % mod * factorialNumInverse[N - R] % mod
	return ans

def solve():
	n = int(input())
	li = list(map(int, input().split()))
	maxNoF = li.count(max(li))
	if maxNoF % 2 == 1:
		print(pow(2, n) % mod)
	else:
		extevent = (pow(2, maxNoF) - nCr(maxNoF, maxNoF // 2, mod) + mod) % mod
		ans = pow(2, n - maxNoF) * extevent % mod
		print(ans)
InverseofNumber(mod)
InverseofFactorial(mod)
factorial(mod)
for test in range(int(input())):
	solve()


mod = 10 ** 9 + 7

def power(a, b):
	if b == 0:
		return 1
	ret = power(a, b // 2) % mod
	ret = ret * ret % mod
	if b % 2 != 0:
		ret = ret * a % mod
	return ret

def fact(n):
	ret = 1
	for x in range(1, n + 1):
		ret *= x
	return ret

def divide(a, b):
	return a % mod * (power(b, mod - 2) % mod) % mod

def combination(n, k):
	ret = 1
	r = min(k, n - k)
	for i in range(r):
		ret = ret % mod * ((n - i) % mod) % mod
		ret = divide(ret, i + 1)
	return ret % mod
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	assert len(c) == n
	N_hc = c.count(max(c))
	if N_hc == 1:
		print(power(2, n) % mod)
	elif N_hc % 2 == 1:
		print(power(2, n) % mod)
	else:
		print(int(power(2, n) % mod - power(2, n - N_hc) % mod * (combination(N_hc, N_hc // 2) % mod)) % mod)


def modulo(a, m):
	q = m
	x = 1
	y = 0
	if m == 1:
		return 0
	else:
		while a > 1:
			w = a // m
			t = m
			m = a % m
			a = t
			t = y
			y = x - w * y
			x = t
		if x <= -1:
			x += q
		return x
mod = 1000000007
arr = [1]
for i in range(1, pow(10, 6) + 7):
	last = arr[-1]
	gh = last * i % mod
	arr.append(gh)

def cmb(n, r):
	a = arr[n] * modulo(arr[r], mod) * modulo(arr[n - r], mod) % mod
	return a
for _ in range(int(input())):
	n = int(input())
	listt = list(map(int, input().split()))
	d = listt.count(max(listt))
	ans = 0
	if d % 2 == 1:
		ans = pow(2, d, mod) * pow(2, n - d, mod) % mod
	else:
		ans = (pow(2, d, mod) - cmb(d, d // 2)) * pow(2, n - d, mod) % mod
	print(ans)


m = 10 ** 9 + 7

def modExp(a, n, m=10 ** 9 + 7):
	if n == 0:
		return 1
	elif n == 1:
		return a
	else:
		while n >= 2:
			if n % 2 == 0:
				n = n // 2
				return modExp(a % m * (a % m) % m, n, m)
			else:
				n = (n - 1) // 2
				return a % m * modExp(a % m * (a % m) % m, n, m) % m % m
memo = {0: 1, 1: 1}

def fact(n, m=10 ** 9 + 7):
	if n not in memo:
		memo[n] = n * fact(n - 1) % m
	return memo[n]
for i in range(10 ** 5 + 1):
	fact(i)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	maxi = arr[0]
	c = 0
	for i in arr:
		if i == maxi:
			c += 1
		elif i > maxi:
			c = 1
			maxi = i
	if c % 2 != 0:
		out = modExp(2, n)
	else:
		luv = (modExp(2, c) - fact(c) * modExp(fact(c // 2) ** 2 % m, m - 2) % m + m) % m
		out = modExp(2, n - c) * luv % m
	print(out)


p = 1000000007

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * power(den, p - 2, p) % p

def power(x, y, p):
	y = int(y)
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if int(y) & int(1) == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	mx = max(l)
	co = l.count(mx)
	ans = int(power(2, n, p))
	if co % 2 == 0:
		ans -= int(power(2, n - co, p)) * int(ncr(co, co // 2, p))
	print(ans % p)


import math
try:

	def nCr(n):
		return math.factorial(n) // (math.factorial(n // 2) * math.factorial(n // 2))
	t = int(input())
	for i in range(t):
		n = int(input())
		l = list(map(int, input().split()))
		ans = pow(2, n, 1000000007)
		m = max(l)
		cnt = l.count(m)
		if cnt % 2 != 0:
			print(ans)
		else:
			subt = pow(2, n - cnt)
			a2 = (pow(2, cnt) - nCr(cnt)) * subt
			print(a2 % 1000000007)
except:
	pass


def ncr(n, r, p):
	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

def power1(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	c1 = a.count(m)
	if c1 % 2 != 0:
		print(power1(2, n, 1000000007) % 1000000007)
	else:
		c2 = c1 // 2
		f = ncr(c1, c2, 1000000007)
		print((power1(2, n, 1000000007) - power1(2, n - c1, 1000000007) * f) % 1000000007)


def power(rm, v):
	if v == 0:
		return 1
	mochi = power(rm, v // 2) % 1000000007
	mochi = mochi * mochi % 1000000007
	if v % 2 != 0:
		mochi = mochi * rm % 1000000007
	return mochi

def comb(n, r):
	mochi = 1
	k = min(r, n - r)
	for i in range(k):
		mochi = mochi % 1000000007 * (n - i) % 1000000007 % 1000000007
		mochi = mochi % 1000000007 * (power(i + 1, 1000000007 - 2) % 1000000007) % 1000000007
	return mochi % 1000000007
bighit = int(input())
while bighit > 0:
	n = int(input())
	jk = list(map(int, input().split()))
	if n == 1:
		print(2)
		bighit = bighit - 1
		continue
	c = jk.count(max(jk))
	if c % 2 != 0:
		ans = power(2, n) % 1000000007
	else:
		ans = power(2, n) % 1000000007 - power(2, n - c) % 1000000007 * comb(c, c // 2) % 1000000007 % 1000000007
	if ans < 0:
		ans = (ans + 1000000007) % 1000000007
	print(ans % 1000000007)
	bighit = bighit - 1


mod = 1000000007

def power(a, b):
	if b == 0:
		return 1
	answer = power(a, b // 2) % mod
	answer = answer * answer % mod
	if b % 2 != 0:
		answer = answer * a % mod
	return answer

def divide(a, b):
	return a % mod * (power(b, mod - 2) % mod) % mod

def comb(n, r):
	answer = 1
	k = min(r, n - r)
	for i in range(k):
		answer = answer % mod * (n - i) % mod % mod
		answer = divide(answer, i + 1)
	return answer % mod

def submain():
	n = int(input())
	a = [int(x) for x in input().split()]
	(max1, maxcount, ans) = (0, 0, 0)
	for i in range(n):
		if max1 < a[i]:
			max1 = a[i]
	for i in range(n):
		if max1 == a[i]:
			maxcount += 1
	if n == 1:
		print(2)
		return
	if maxcount % 2 != 0:
		ans = power(2, n) % mod
	else:
		ans = power(2, n) % mod - power(2, n - maxcount) % mod * comb(maxcount, maxcount // 2) % mod % mod
	if ans < 0:
		ans = (ans + mod) % mod
	print(ans % mod)
t = int(input())
for i in range(t):
	submain()


import math
test = int(input())
for z in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	x = max(a)
	co = a.count(x)
	ans = 0
	if co % 2 != 0:
		ans = 2 ** n
	else:
		ans = 2 ** (n - co)
		a = math.factorial(co)
		b = math.factorial(co // 2)
		al = a // (b * b)
		ans *= 2 ** co - al
	ans %= 1000000007
	print(ans)


import math as math

def po(x, y):
	res = 1
	p = 1000000007
	x = x % p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return int(res)

def fer(n, r):
	p = 1000000007
	if r == 0:
		return 1
	fac = [1]
	for k in range(1, n + 1):
		t = fac[k - 1]
		fac.append(t * k % p)
	return int(fac[n] * po(fac[r], p - 2) % p * po(fac[n - r], p - 2) % p % p)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	p = 1000000007
	maximum = max(arr)
	count = 0
	for i in arr:
		if i == maximum:
			count += 1
	f = count
	lft = po(2, n - f)
	lft %= p
	rgt = po(2, f)
	if f % 2 == 0:
		rgt -= fer(f, f // 2)
	rgt %= p
	print(int(lft * rgt % p))


def nCr(n, r, mod):
	numerator = 1
	denominator = 1
	for i in range(r):
		numerator = numerator * (n - i) % mod
		denominator = denominator * (i + 1) % mod
	return numerator * pow(denominator, mod - 2, mod) % mod
T = int(input())
while T > 0:
	T = T - 1
	N = int(input())
	cards = [int(i) for i in input().strip().split()]
	cnt = 0
	maxu = 0
	for i in range(N):
		maxu = max(maxu, cards[i])
	for i in range(N):
		if cards[i] == maxu:
			cnt = cnt + 1
	mod = 1000000000 + 7
	if cnt & 1:
		print(pow(2, N, mod))
	else:
		a = pow(2, N, mod) % mod
		b = nCr(cnt, cnt // 2, mod) % mod
		c = pow(2, N - cnt, mod) % mod
		ans = (a - b * c % mod) % mod
		print(ans)


mod = 1000000007

def power(aa, bb):
	if bb == 0:
		return 1
	ret = power(aa, bb // 2) % mod
	ret = ret * ret % mod
	if bb % 2 != 0:
		ret = ret * aa % mod
	return ret

def divide(aa, bb):
	return aa % mod * (power(bb, mod - 2) % mod) % mod

def comb(n, r):
	ret = 1
	k = min(r, n - r)
	for i in range(k):
		ret = ret % mod * (n - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod
tem = int(input())
while tem > 0:
	nums = int(input())
	l = [int(x) for x in input().split()]
	if nums == 1:
		print(2)
		tem -= 1
		continue
	c = l.count(max(l))
	if c % 2 != 0:
		ans = power(2, nums) % mod
	else:
		ans = power(2, nums) % mod - power(2, nums - c) % mod * comb(c, c // 2) % mod % mod
	if ans < 0:
		ans = (ans + mod) % mod
	print(ans % mod)
	tem -= 1


import pandas as pd
import math as mt
import numpy as np
MODD = 10 ** 9 + 7

def calcExponent(a, num):
	var = 1
	a = a % MODD
	while num > 0:
		if num & 1:
			var = var * a % MODD
		num = num // 2
		a = a * a % MODD
	return var

def makeExponent(num):
	return calcExponent(num, MODD - 2)

def function(num, val):
	if val == 0:
		return 1
	brr = [0 for i in range(num + 1)]
	brr[0] = 1
	for i in range(1, num + 1):
		brr[i] = brr[i - 1] * i % MODD
	return brr[num] * makeExponent(brr[val]) % MODD * makeExponent(brr[num - val]) % MODD % MODD

def sum(aa, bb):
	c = aa + bb
test = int(input())
for qwerty in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	data = dict()
	large = -1
	for i in arr:
		if i in data:
			data[i] += 1
		else:
			data[i] = 1
		large = max(large, i)
	val = data[large]
	high = pow(2, val)
	low = pow(2, n - val)
	sum(234, 23)
	if val % 2 == 0:
		temp = function(val, val // 2)
		high -= temp
	high = high % MODD
	print(low * high % MODD)


mod = 1000000007

def power(x, n):
	res = 1
	while n:
		if n & 1:
			res = res * x % mod
		n = n // 2
		x = x * x % mod
	return res

def divv(o, p):
	return o % mod * (power(p, mod - 2) % mod) % mod

def sol(n, t):
	ans = 1
	g = min(t, n - t)
	for i in range(0, g):
		ans = ans % mod * (n - i) % mod % mod
		ans = divv(ans, i + 1)
	return ans % mod
test = int(input())
for _ in range(test):
	n = int(input())
	l = list(map(int, input().strip().split()))[:n]
	maxxx = max(l)
	max_val = l.count(maxxx)
	if n == 1:
		print(2)
		continue
	if max_val % 2 != 0:
		res = power(2, n) % mod
	else:
		res = power(2, n) % mod - power(2, n - max_val) % mod * sol(max_val, max_val // 2) % mod % mod
	if res < 0:
		res = (res + mod) % mod
	print(res % mod)


MOD = 1000000007
tc = int(input())

def power(n, p):
	ans = 1
	while p:
		if p & 1:
			ans = ans * n % MOD
		n = n * n % MOD
		p >>= 1
	return ans

def div(a, b):
	return a % MOD * (power(b, MOD - 2) % MOD) % MOD

def solution(n, r):
	ans = 1
	k = min(r, n - r)
	for i in range(k):
		ans = ans % MOD * ((n - i) % MOD) % MOD
		ans = div(ans, i + 1)
	return ans % MOD
for testcase in range(tc):
	n = int(input())
	lst = list(map(int, input().split()))
	max1 = max(lst)
	max_value = lst.count(max1)
	if n == 1:
		print(2)
	elif max_value % 2 == 1:
		print(power(2, n) % MOD)
	else:
		pri = (power(2, n) % MOD - pow(2, n - max_value, MOD) % MOD * solution(max_value, max_value // 2) % MOD % MOD % MOD) % MOD
		pri += MOD
		pri %= MOD
		print(pri % MOD)


mod = 1000000007

def ncr(n, r, p):
	num = 1
	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

def solve(n):
	cards = list(map(int, input().split()))
	if n == 1:
		return 2
	m = max(cards)
	c = 0
	totWays = pow(2, n, mod)
	for i in cards:
		if i == m:
			c += 1
	if c % 2 != 0:
		return totWays % mod
	else:
		p = pow(2, n - c, mod) % mod * (ncr(c, c // 2, mod) % mod) % mod
		ans = (totWays % mod - p % mod + mod) % mod
		return ans
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


def divide(a, b):
	p = 1000000007
	return a % p * (power(b, p - 2) % p) % p

def comb(n, r):
	p = 1000000007
	ans = 1
	k = min(r, n - r)
	k = int(k)
	for i in range(0, k):
		ans = ans % p * (n - i) % p % p
		ans = divide(ans, i + 1)
	return ans % p

def power(a, b):
	p = 1000000007
	if b == 0:
		return 1
	ans = power(a, b // 2) % p
	ans = ans * ans % p
	if b % 2 != 0:
		ans = ans * a % p
	return ans

def card(l, n):
	p = 1000000007
	ans = 0
	maxi = 0
	c = 0
	for i in range(0, n):
		if maxi < l[i]:
			maxi = l[i]
	for i in range(0, n):
		if maxi == l[i]:
			c += 1
		if n == 1:
			return 2
	if c % 2 != 0:
		ans = power(2, n) % p
	else:
		ans = power(2, n) % p - power(2, n - c) % p * comb(c, c / 2) % p % p
	if ans < 0:
		ans = (ans + p) % p
	return ans % p
t = int(input())
h = []
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	h.append(card(l, n))
	t -= 1
print(*h, sep='\n')


mod = 1000000007

def power(y, z):
	if z == 0:
		return 1
	ret = power(y, z // 2) % mod
	ret = ret * ret % mod
	if z % 2 != 0:
		ret = ret * y % mod
	return ret

def divide(y, z):
	return y % mod * (power(z, mod - 2) % mod) % mod

def comb(n, r):
	ret = 1
	k = min(r, n - r)
	for i in range(k):
		ret = ret % mod * (n - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod
p = int(input())
while p > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	if n == 1:
		print(2)
		p = p - 1
		continue
	c = l.count(max(l))
	if c % 2 != 0:
		ans5 = power(2, n) % mod
	else:
		ans5 = power(2, n) % mod - power(2, n - c) % mod * comb(c, c // 2) % mod % mod
	if ans5 < 0:
		ans5 = (ans5 + mod) % mod
	print(ans5 % mod)
	p = p - 1


MOD = 1000000007
arr1 = [0 for i in range(100010)]
arr2 = [0 for i in range(100010)]
arr3 = [0 for i in range(100010)]

def pre():
	arr2[0] = 1
	arr2[1] = 1
	arr1[0] = 1
	arr1[1] = 1
	arr3[0] = 1
	for i in range(2, 100010):
		arr2[i] = arr2[MOD % i] * (MOD - MOD // i) % MOD
	for i in range(2, 100010):
		arr1[i] = arr2[i] * arr1[i - 1] % MOD
	for i in range(1, 100010):
		arr3[i] = arr3[i - 1] * i % MOD

def calc(x, y):
	return arr3[x] * arr1[y] % MOD * arr1[x - y] % MOD
pre()
test = int(input())
for asd in range(test):
	n = int(input())
	res = 0
	minimum = 0
	count_val = 0
	s = input()
	s = s.split()
	for i in range(n):
		temp = int(s[i])
		if minimum < temp:
			minimum = temp
			count_val = 1
		elif minimum == temp:
			count_val += 1
	val = 1
	i = 0
	while i < n - count_val:
		val = 2 * val % MOD
		i += 1
	res = res + val * 2 % MOD
	i = 1
	while i <= count_val // 2:
		if i != count_val - i:
			res = (res + val * (calc(count_val, i) * 2) % MOD % MOD) % MOD
		i += 1
	print(res)


mod = 1000000007

def power(g, h):
	if h == 0:
		return 1
	ret = power(g, h // 2) % mod
	ret = ret * ret % mod
	if h % 2 != 0:
		ret = ret * g % mod
	return ret

def divide(g, h):
	return g % mod * (power(h, mod - 2) % mod) % mod

def comb(n, r):
	ret = 1
	k = min(r, n - r)
	for i in range(k):
		ret = ret % mod * (n - i) % mod % mod
		ret = divide(ret, i + 1)
	return ret % mod
t = int(input())
while t > 0:
	n = int(input())
	l = [int(x) for x in input().split()]
	if n == 1:
		print(2)
		t -= 1
		continue
	c = l.count(max(l))
	if c % 2 != 0:
		gans = power(2, n) % mod
	else:
		gans = power(2, n) % mod - power(2, n - c) % mod * comb(c, c // 2) % mod % mod
	if gans < 0:
		gans = (gans + mod) % mod
	print(gans % mod)
	t -= 1


def fact(n):
	ans = 1
	for i in range(1, n + 1):
		ans = ans * i
	return ans

def ncr(n, r, p):
	num = 1
	den = 1
	for i in range(r):
		den = den * (i + 1) % p
		num = num * (n - i) % p
	return num * pow(den, p - 2, p) % p
t = int(input())
for tc in range(t):
	n = int(input())
	c = 0
	numbers = list(map(int, input().strip().split()))[:n]
	number_list = [int(i) for i in numbers]
	maxi = 0
	for i in range(n):
		if number_list[i] > maxi:
			maxi = number_list[i]
	for i in range(n):
		if number_list[i] == maxi:
			c = c + 1
	other = n - c
	if c % 2 == 1:
		print(pow(2, n, 1000000007))
		continue
	else:
		original = pow(2, n, 1000000007)
		rem_2 = pow(2, n - c)
		rem = c // 2
		print((original - rem_2 * ncr(c, rem, 1000000007)) % 1000000007)