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

Chefina likes prefix and suffix sums, so Chef decided to give some to her as her birthday present. He created a sequence $a_{1}, a_{2}, \ldots, a_{N}$ and calculated its prefix sums $pre_{1}, pre_{2}, \ldots, pre_{N}$ (for each valid $i$, $pre_{i}$ is the sum of the first $i$ elements of $a$) and suffix sums $suf_{1}, suf_{2}, \ldots, suf_{N}$ (for each valid $i$, $suf_{i}$ is the sum of the last $i$ elements of $a$). He arranged the elements of these sequences in a gift box and went to Chefina's home.

When Chefina opened the gift box, she found out that all the elements got shuffled when Chef was carrying the box. For each element, it is now impossible to determine if it belonged to the sequence $pre$ or $suf$ and what its index in the correct sequence was. The only thing we know is a sequence $x_{1}, x_{2}, \ldots, x_{2N}$, which contains all the elements of the sequences $pre$ and $suf$, in no particular order.

Chefina is now curious about the number of initial sequences $a$ which Chef could have chosen, such that it is possible to obtain $x$ by shuffling the prefix and suffix sums of $a$. Help Chefina find this number. Since it could be very large, compute it modulo $1,000,000,007$.

------  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 $2N$ space-separated integers $x_{1}, x_{2}, \ldots, x_{2N}$.

------  Output ------
For each test case, print a single line containing one integer ― the number of possible initial sequences modulo $1,000,000,007$.

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

------  Subtasks ------
Subtask #1 (20 points):
$T ≤ 10$
$N ≤ 10$

Subtask #2 (80 points): original constraints

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

1

-1 1

1

0 0

2

4 3 1 4

3

5 3 7 10 5 10
----- Sample Output 1 ------ 
0

1

2

4

Difficulty: HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
from sys import stdin
mod = int(1000000000.0) + 7
fact = [1] * 100001

def generateFactorials():
	for i in range(1, 100001):
		fact[i] = i * fact[i - 1] % mod
generateFactorials()

def isUnique(a, length, freq, target, n):
	freq[target] -= 2
	pairs = 0
	elements = 2
	mul = 0
	deno = 1
	num = fact[n - 1]
	for i in range(length):
		p1 = a[i]
		p2 = target - a[i]
		n1 = freq.get(p1)
		n2 = freq.get(p2, 0)
		if n1 > 0 and n2 > 0:
			req = n1
			if n1 != n2:
				return 0
			if p1 != p2:
				mul = mul + req
			else:
				req = req // 2
			elements += 2 * req
			deno = deno * fact[req] % mod
			freq[a[i]] = -1
			freq[target - a[i]] = -1
	if elements == 2 * n:
		return pow(2, mul, mod) * (num * pow(deno, mod - 2, mod)) % mod % mod
	else:
		return 0
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	summ = sum(arr)
	if n == 1:
		if arr[0] == arr[1]:
			print(1)
		else:
			print(0)
		continue
	elif n > 1:
		check = [0]
		if [0] == list(set(arr)):
			print(1)
			continue
	freq = {}
	for i in arr:
		if freq.get(i, -1) == -1:
			freq[i] = 0
		freq[i] += 1
	a = list(freq.keys())
	length = len(a)
	possible = []
	for i in a:
		if freq.get(i) >= 2 and (n + 1) * i == summ:
			possible.append(i)
	answer = 0
	if len(possible) == 0:
		print(0)
		continue
	assert len(possible) == 1
	for i in possible:
		answer = (answer + isUnique(a, length, freq, i, n)) % mod
		freq[i] += 2
	print(answer % mod)


import sys
from collections import defaultdict
import math
from typing import Dict, List

class Solution:
	MOD = 1000000007
	N = 10 ** 5 + 5

	def __init__(self):
		self.fact = self.giveFact()

	def modMul(self, a: int, b: int) -> int:
		return a % self.MOD * (b % self.MOD) % self.MOD

	def power(self, a: int, b: int) -> int:
		ans = 1
		while b > 0:
			if b & 1:
				ans = ans * a % self.MOD
			b = b >> 1
			a = a * a % self.MOD
		return ans % self.MOD

	def giveFact(self) -> list:
		l = []
		for i in range(int(math.log2(self.N))):
			l.append(i ** 2)
		facts = []
		for i in range(self.N):
			facts.append(0)
		facts[0] += 1
		for i in range(1, self.N):
			facts[i] = self.modMul(facts[i - 1], i)
		return facts

	def input(self) -> int:
		return int(sys.stdin.readline())

	def input_list(self) -> List[int]:
		return [int(x) for x in sys.stdin.readline().split()]

	def init_vars(self) -> list:
		(m, h) = (defaultdict(int), defaultdict(int))
		s = set()
		return [m, h, s]

	def populate_map(self, m, arr) -> dict:
		for x in arr:
			m[x] += 1
		return m

	def to_continue(self, f, n) -> bool:
		if f:
			print('0')
			return False
		if n == 1:
			print('1')
			return False
		return True

	def solve(self) -> None:
		facts = self.fact
		t = self.input()
		for testcase in range(t):
			n = self.input()
			res = 1
			arr = self.input_list()
			L = self.init_vars()
			(m, h, s) = (L[0], L[1], L[2])
			SUM = sum(arr)
			m = self.populate_map(m, arr)
			for x in arr:
				s.add(x)
			prefix = SUM // (n + 1)
			if m[prefix] < 2:
				print('0')
				continue
			m[2 ** 0 - 1] += 2
			flag = False
			for x in s:
				if m[x] != m[prefix - x]:
					flag = True
					break
			flag = self.to_continue(flag, n)
			if not flag:
				continue
			m[prefix] -= 2
			m[0] -= 2
			A = []
			for i in range(len(arr)):
				ele = arr[i]
				if ele in h or h[ele] == 1:
					continue
				if prefix % 2 == 0 and prefix == 2 * ele:
					r = m[ele] // 2
					A.append(r)
				elif m[ele] > 1:
					r = m[ele]
					A.append(r)
				h[ele] = 1
				h[prefix - ele] = 1
			fn = False
			if prefix % 2 == 0:
				fn = True
			if fn:
				res += m[prefix // 2] // 2
			else:
				res += 0
			result = facts[n - 1] * pow(2, n - res) % self.MOD
			for x in A:
				result = result * self.power(facts[x], self.MOD - 2) % self.MOD
			print(result)
s = Solution()
s.solve()


from sys import stdin
M = 10 ** 9 + 7
fact = [0] * 1000001
fact[0] = 1
for x in range(1, len(fact)):
	fact[x] = x * fact[x - 1]
	fact[x] = fact[x] % M

def power(x, y):
	ans = 1
	while y > 0:
		if y % 2 == 1:
			ans = ans * x % M
		y = y // 2
		x = x * x % M
	return ans % M
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	l = [int(x) for x in stdin.readline().split()]
	s = sum(l)
	if s % (n + 1):
		print(0)
		continue
	ans = fact[n - 1]
	d = {}
	for x in list(l):
		if x in d:
			d[x] += 1
		else:
			d[x] = 1
	ssum = s // (n + 1)
	if ssum in d and d[ssum] >= 2:
		d[ssum] -= 2
	else:
		print(0)
		continue
	flag = 0
	for x in dict(d):
		if d[x] == 0:
			continue
		if ssum - x not in d or d[ssum - x] != d[x]:
			flag = 1
			break
		elif ssum - x != x:
			ans = ans * power(2, d[x]) % M
			ans = ans * power(fact[d[x]], M - 2) % M
			d[ssum - x] = 0
		else:
			if d[x] % 2 == 1:
				flag = 1
				break
			ans = ans * power(fact[d[x] // 2], M - 2) % M
			d[x] = 0
	if flag == 1:
		print(0)
	else:
		print(ans % M)


from math import factorial
import sys
iterations = int(sys.stdin.readline())
for given_tc in range(iterations):
	input_size = int(sys.stdin.readline())
	MY_list = list(map(int, sys.stdin.readline().split()))
	temporary_variable = sum(MY_list)
	temporary_variable = temporary_variable / (input_size + 1)
	temporary_variable = int(temporary_variable)
	cnt = MY_list.count(temporary_variable)
	if cnt >= 2:
		unordered_map = {}
		MY_list.sort(reverse=False)
		MY_list.remove(temporary_variable)
		n = 2 * input_size - 2
		condition = True
		countering = 0
		MY_list.remove(temporary_variable)
		for gibrish in range(0, n // 2, 1):
			if MY_list[gibrish] > MY_list[n - gibrish - 1]:
				chefpsaup = MY_list[n - gibrish - 1]
				chefpsadown = MY_list[gibrish]
			else:
				chefpsaup = MY_list[gibrish]
				chefpsadown = MY_list[n - gibrish - 1]
			if chefpsaup + chefpsadown == temporary_variable:
				if chefpsaup != chefpsadown:
					countering += 1
				elif chefpsaup == chefpsadown:
					pass
				elif chefpsaup == 'a':
					pass
				elif chefpsadown == 'b':
					pass
				else:
					pass
				if unordered_map.get((chefpsaup, chefpsadown)) != None:
					unordered_map[chefpsaup, chefpsadown] += 1
				else:
					unordered_map[chefpsaup, chefpsadown] = 1
			else:
				condition = False
				sys.stdout.write('0\n')
				break
		verdict = factorial(input_size - 1) % 1000000007
		if condition:
			for iterator in unordered_map:
				verdict = verdict * pow(factorial(unordered_map[iterator]), 1000000005, 1000000007)
				verdict %= 1000000007
			verdict = verdict * pow(2, countering, 1000000007)
			verdict %= 1000000007
			verdict = int(verdict)
			sys.stdout.write(str(verdict) + '\n')
	else:
		sys.stdout.write('0\n')


from collections import Counter
from sys import stdin
(N, M) = (100001, 1000000007)
(r, f) = ([1] * N, [1] * N)
for i in range(2, N):
	f[i] = pow(f[i - 1] * i, 1, M)
	r[i] = pow(f[i], M - 2, M)
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	if n == 1:
		if a[0] != a[1]:
			print(0)
		else:
			print(1)
		continue
	s = sum(a)
	if s % (n + 1):
		print(0)
		continue
	s //= n + 1
	a = Counter(a)
	if s not in a or a[s] < 2:
		print(0)
		continue
	a[s] -= 2
	t = x = 0
	ans = f[n - 1]
	for i in a:
		if a[i]:
			if s - i not in a:
				t = 1
				break
			else:
				if a[s - i] == a[i]:
					if s - i == i:
						if a[i] & 1:
							t = 1
							break
						x = a[i] >> 1
						ans = ans * r[a[i] >> 1] % M
					else:
						ans = ans * r[a[i]] % M
				else:
					t = 1
					break
				a[s - i] = 0
	if t == 1:
		print(0)
	else:
		print(ans * pow(2, n - 1 - x, M) % M)


from sys import stdin, stdout
mod = 1000000007
from collections import defaultdict as dd
t = stdin.readline()
t = int(t)
fact = [1]
mul = 1
for i in range(1, 100002):
	mul = mul * i % mod
	fact.append(mul)
for _ in range(t):
	n = stdin.readline()
	n = int(n)
	d = dd(int)
	a = [int(x) for x in stdin.readline().split()]
	s = 0
	for i in a:
		s += i
		d[i] += 1
	fs = s / (n + 1)
	if d[fs] < 2:
		print(0)
	else:
		flag = 0
		d[fs] -= 2
		nn = n - 1
		ls = fact[n - 1]
		nn -= d[fs / 2] // 2
		m = 1
		for i in a:
			if d[i] != d[fs - i]:
				flag = 1
				break
			else:
				if i != fs - i:
					m *= fact[max(d[i], 1)]
					m %= mod
				else:
					m *= fact[max(d[i] // 2, 1)]
					m %= mod
				d[i] = d[fs - i] = 1
		y = pow(m, mod - 2, mod)
		ls *= y
		ls %= mod
		if flag == 1:
			print(0)
		else:
			print(pow(2, nn, mod) * ls % mod)


import sys
from collections import defaultdict
mod = 10 ** 9 + 7
fac = [1]
for i in range(1, 10 ** 5 + 1):
	fac.append(fac[-1] * i % mod)

def modularexpo(x, n, mod):
	res = 1
	while n > 0:
		if n % 2 == 1:
			res = res * x % mod
		x = x * x % mod
		n = n // 2
	return res
for _ in range(int(sys.stdin.readline().rstrip())):
	n = int(sys.stdin.readline().rstrip())
	arr = list(map(int, sys.stdin.readline().rstrip().split()))
	if n == 1:
		if arr[0] == arr[1]:
			sys.stdout.write('1\n')
		else:
			sys.stdout.write('0\n')
	else:
		final = sum(arr) // (n + 1)
		d = defaultdict(lambda : 0)
		keys = []
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
				keys.append(i)
		if final in d and d[final] >= 2:
			d[final] -= 2
			(total_pair, diff_pair, freq) = (0, 0, 1)
			for i in keys:
				x = min(d[i], d[final - i])
				if i == final - i:
					if x % 2 == 0:
						d[i] = 0
					else:
						d[i] = 1
					total_pair += x // 2
					freq = freq * fac[x // 2] % mod
				else:
					d[i] -= x
					d[final - i] -= x
					total_pair += x
					diff_pair += x
					freq = freq * fac[x] % mod
			if total_pair != n - 1:
				sys.stdout.write('0\n')
			else:
				mod = 10 ** 9 + 7
				temp1 = fac[total_pair]
				temp2 = modularexpo(2, diff_pair, mod)
				temp3 = freq
				temp1 = temp1 * temp2 % mod
				temp3 = modularexpo(temp3, mod - 2, mod)
				temp3 = temp3 * temp1 % mod
				sys.stdout.write(str(temp3) + '\n')
		else:
			sys.stdout.write('0\n')


mod = pow(10, 9) + 7
import math

def modFact(n, p):
	if n >= p:
		return 0
	result = 1
	for i in range(1, n + 1):
		result = result * i % p
	return result

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		print('Division not defined')
	else:
		return inv * a % m

def generating(n):
	x = modFact(n, mod)
	x = x * pow(2, n, mod)
	return x % mod
finall = []
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	candidate = []
	mark = 0
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
			if d[i] >= 2:
				candidate.append(i)
				mark += 1
	if mark == 0:
		finall.append(0)
	else:
		if 0 not in d:
			d[0] = 2
		else:
			d[0] += 2
		l.append(0)
		l.append(0)
		for i in candidate:
			flag = 0
			for x in l:
				diff = i - x
				if diff not in d:
					flag = 1
					break
				elif d[diff] != d[x]:
					flag = 1
					break
			if flag == 0:
				break
		if flag == 0:
			item = i
			g = {}
			for i in l:
				diff = item - i
				if diff not in g:
					if i not in g:
						g[diff] = 1
				else:
					g[diff] += 1
			ans = 1
			if 0 in g:
				g[0] -= 2
			if item in g:
				g[item] -= 2
			for (x, y) in g.items():
				if 2 * x == item:
					ans *= generating(y // 2)
				else:
					ans *= modFact(y, mod)
			yt = pow(2, n - 1, mod) * modFact(n - 1, mod) % mod
			finall.append(modDivide(yt, ans, mod))
		else:
			finall.append(0)
for x in finall:
	print(x)


import sys
from collections import defaultdict
MOD = 1000000007

def power(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % MOD
		b = b >> 1
		a = a * a % MOD
	return ans % MOD
N = 100000

def giveFact():
	facts = [0] * (N + 1)
	facts[0] = 1
	for i in range(1, N + 1):
		facts[i] = facts[i - 1] % MOD * (i % MOD) % MOD
	return facts
fact = giveFact()
t = int(sys.stdin.readline())
for testcase in range(t):
	n = int(sys.stdin.readline())
	res = 1
	arr = [int(x) for x in sys.stdin.readline().split()]
	m = defaultdict(int)
	h = defaultdict(int)
	s = set()
	SUM = sum(arr)
	for x in arr:
		m[x] += 1
		s.add(x)
	prefix = SUM // (n + 1)
	if m[prefix] < 2:
		print('0')
		continue
	m[0] += 2
	flag = False
	for x in s:
		if m[x] != m[prefix - x]:
			flag = True
			break
	if flag:
		print('0')
		continue
	if n == 1:
		print('1')
		continue
	m[prefix] -= 2
	m[0] -= 2
	A = []
	for i in range(len(arr)):
		ele = arr[i]
		if h[ele] == 1:
			continue
		if prefix % 2 == 0 and prefix == 2 * ele:
			A.append(m[ele] // 2)
		elif m[ele] > 1:
			A.append(m[ele])
		h[ele] = 1
		h[prefix - ele] = 1
	if prefix % 2 == 0:
		res += m[prefix // 2] // 2
	result = fact[n - 1] * pow(2, n - res) % MOD
	for x in A:
		result = result * power(fact[x], MOD - 2) % MOD
	print(result)


import math
from sys import stdin, stdout

def modDivide(a, b, c):
	m = 10 ** 9 + 7
	a = a % m
	a = a * c
	inv = pow(b, m - 2, m)
	c = 0
	return inv * a % m

def coun(arr, t):
	count = 0
	t += 1
	for i in range(len(arr)):
		if arr[i][0] != arr[i][1]:
			count += 1
	t = 0
	return count + t

def printPairs(arr, summ, t):
	bigarr = []
	t = 2
	for i in range(len(arr) // 2):
		k = []
		if arr[i] + arr[-i - 1] == summ:
			k.append(arr[i])
			t += 1
			k.append(arr[-i - 1])
			k = tuple(k)
			bigarr.append(k)
	t += 1
	return bigarr

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

def countt(listOfTuple, t):
	count_map = {}
	k = []
	t += 1
	for i in listOfTuple:
		count_map[i] = count_map.get(i, 0) + 1
		k.append(count_map)
	p = count_map.values()
	t -= 1
	return p

def modfact(n, p, l):
	if n >= p:
		l = 1
		return 0
	result = 1
	l += 1
	for i in range(1, n + 1):
		result = result * i % p
	l = 1
	return result * l
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	maxx = sum(arr) // (n + 1)
	flag = 1
	t = 0
	if len(arr) == 2:
		flag = 0
		t = 0
		if arr[0] == arr[1] and t > -10:
			print(1)
		elif t > -9:
			print(0)
	if flag == 1 and t > -9:
		if arr.count(maxx) < 2:
			print(0)
			t = 1
			flag = 0
		elif t > -10:
			arr.remove(maxx)
			arr.remove(maxx)
			arr.sort()
	if flag == 1:
		arr1 = printPairs(arr, maxx, 1)
		kk = len(arr1)
		if kk < 1 or kk != n - 1:
			print(0)
			t += 1
		elif t > -10:
			arrdict = countt(arr1, 1)
			arrlist = list(arrdict)
			arrlist.sort(reverse=True)
			powerf = coun(arr1, 1)
			t += 1
			twotothepowermod = power(2, powerf, 1000000007, 1)
			if t > -5:
				mod = (10 ** 9 + 7) * arrlist[0]
				k = modfact(n - 1, mod, 1) // arrlist[0]
				for i in range(1, arrlist[0]):
					k = modDivide(k, i, 1)
				for i in range(1, len(arrlist)):
					for j in range(1, arrlist[i] + 1):
						k = modDivide(k, j, 1)
				z = k * twotothepowermod % (10 ** 9 + 7)
				t += 1
				print(int(z))


from sys import stdin, stdout

def compute(a, facts, pow2, n, l, inv):
	counts = {}
	sum = 0
	for i in a:
		if i not in counts:
			counts[i] = 1
		else:
			counts[i] += 1
		sum += i
	if abs(sum) % (n + 1) != 0:
		return 0
	sum //= n + 1
	if sum not in counts:
		return 0
	v = counts[sum]
	if v < 2:
		return 0
	counts[sum] = v - 2
	repetitions = []
	non_similar_pairs = 0
	for (ai, count) in counts.items():
		if count == 0:
			continue
		other = sum - ai
		if ai == other:
			if count % 2 == 1:
				return 0
			counts[ai] = 0
			count //= 2
			if count > 1:
				repetitions.append(count)
			continue
		if other not in counts or counts[other] != count:
			return 0
		non_similar_pairs += count
		counts[ai] = 0
		counts[other] = 0
		if count == 1:
			continue
		repetitions.append(count)
	if n == 1:
		return 1
	ans = facts[n - 1]
	for repc in repetitions:
		val = power(inv, (facts[repc], limit - 2))
		ans = ans * val % limit
		if ans == 0:
			return 0
	return ans * pow2[non_similar_pairs] % limit

def power(inv, pr):
	if pr in inv:
		return inv[pr]
	(x, y) = pr
	if y == 0:
		inv[pr] = 1
		return 1
	p = power(inv, (x, y // 2)) % limit
	if p == 0:
		inv[pr] = 0
		return 0
	p = p * p % limit
	if y % 2 == 0:
		inv[pr] = p
		return p
	p = x * p % limit
	inv[pr] = p
	return p
limit = 1000000007
facts = [1]
pow2 = [1]
i = 1
fp = 1
pp = 1
while i < 100001:
	fp = fp * i % limit
	pp = pp * 2 % limit
	facts.append(fp)
	pow2.append(pp)
	i += 1
inv = {}
t = int(input().strip())
i = 0
n = 0
l = 0
lines = []
while i < t:
	lines.append(input())
	lines.append(input())
	i += 1
i = 0
t <<= 1
for line in lines:
	if i % 2 == 0:
		n = int(line)
		l = n + n
		i += 1
		continue
	a = list(map(int, line.split()))
	print(compute(a, facts, pow2, n, l, inv))
	i += 1
	if i == t:
		break


import sys
import math
total_number_of_testcases = sys.stdin.readline()
total_number_of_testcases = int(total_number_of_testcases)
for testcases in range(total_number_of_testcases):
	my_dictionary = {}
	new_number = sys.stdin.readline()
	new_number = int(new_number)
	my_list_old = [int(index) for index in sys.stdin.readline().split()]
	sum_term = sum(my_list_old) // (new_number + 1)
	if my_list_old.count(sum_term) < 2:
		sys.stdout.write('0\n')
	else:
		new_var = 0
		my_list_old.sort()
		check_var = True
		my_list_old.remove(sum_term)
		my_list_old.remove(sum_term)
		numberr = new_number * 2 - 2
		this_term = numberr // 2
		for index_var in range(this_term):
			first_num = min(my_list_old[numberr - index_var - 1], my_list_old[index_var])
			second_num = max(my_list_old[index_var], my_list_old[numberr - index_var - 1])
			if first_num + second_num != sum_term:
				sys.stdout.write('0\n')
				check_var = False
				break
			else:
				if first_num == second_num:
					pass
				else:
					new_var = new_var + 1
				if my_dictionary.get((first_num, second_num)) != None:
					my_dictionary[first_num, second_num] = my_dictionary[first_num, second_num] + 1
				else:
					my_dictionary[first_num, second_num] = 1
		new_num = new_number - 1
		desired_result = math.factorial(new_num) % 1000000007
		if check_var == False:
			pass
		else:
			for index_var in my_dictionary.keys():
				temporary = math.factorial(my_dictionary[index_var])
				desired_result = pow(temporary, 1000000005, 1000000007) * desired_result % 1000000007
			temporary = pow(2, new_var, 1000000007)
			desired_result = temporary * desired_result % 1000000007
			desired_result = str(desired_result)
			sys.stdout.write(desired_result + '\n')


from collections import defaultdict
import sys
mod = 10 ** 9 + 7
(fact, ppo, ifact) = ([1], [1], [1])
N = 10 ** 5 + 1
inf = 10 ** 10
for i in range(1, N):
	f = fact[-1] * i % mod
	fact.append(f)
	ff = (ppo[-1] << 1) % mod
	ppo.append(ff)
	f = pow(f, mod - 2, mod)
	ifact.append(f)
T = int(sys.stdin.readline())
for _ in range(T):
	n = int(sys.stdin.readline().rstrip())
	nn = n << 1
	a = list(map(int, sys.stdin.readline().split()))
	mp = defaultdict(int)
	l = []
	for x in a:
		if mp[x] == 0:
			l.append(x)
		mp[x] += 1
	if n == 1:
		if l[0] == l[-1]:
			sys.stdout.write('1\n')
		else:
			sys.stdout.write('0\n')
		continue
	l.sort()
	ma = l[-1]
	mi = l[0]
	xx = 0
	if mi >= 0 and ma > 0:
		xx = ma
	elif mi < 0 and ma <= 0:
		xx = mi
	else:
		xx = mi + ma
	if mp[xx] < 2:
		sys.stdout.write('0\n')
		continue
	mp[xx] -= 2
	flg = 0
	p = 0
	n -= 1
	d = defaultdict(int)
	ans = fact[n]
	la = []
	for i in l:
		i2 = xx - i
		if mp[i] != mp[i2]:
			flg = 1
			break
		q1 = mp[i]
		node = (min(i, i2), max(i, i2))
		if d[node] == 0:
			d[node] = 1
			if i != i2:
				if q1 > 1:
					ans = ans * ifact[q1] % mod
				p += q1
			else:
				if mp[i] & 1:
					flg = 1
					break
				q = q1 >> 1
				if q > 1:
					ans = ans * ifact[q] % mod
	if flg:
		sys.stdout.write('0\n')
		continue
	ans = ans * ppo[p] % mod
	sys.stdout.write(str(ans) + '\n')


import math
d = math.factorial(10 ** 5)
f = [-1 for mm in range(10 ** 5 + 1)]
re = [-1 for mmm in range(10 ** 5 + 1)]
f1 = [-1 for mmmm in range(10 ** 5 + 1)]

def myfac(n):
	p = 1
	for i in range(1, n + 1):
		p = p * i % (10 ** 9 + 7)
	return p
U1 = [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]
ser = ''
for yt in range(1000, 10 ** 5 + 1):
	U1.append(-1)

def fac_inv(n):
	if U1[n - 1] != -1:
		return U1[n - 1]
	elif f1[n] != -1:
		p = f1[n]
	else:
		p = math.factorial(n)
		f1[n] = p
	k = pow(p, 10 ** 9 + 5, 10 ** 9 + 7)
	U1[n - 1] = k
	return k
t = int(input())
waste = 0
while waste < t:
	ser += ' '
	n = int(input())
	var = list(map(int, input().split()))
	totsum = sum(var)
	if totsum % (n + 1) != 0:
		ser += str(0)
		waste += 1
		continue
	s1 = totsum // (n + 1)
	if var.count(s1) < 2:
		ser += str(0)
		waste += 1
		continue
	var.remove(s1)
	var.remove(s1)
	var.sort()
	count = 0
	(i_, i) = (0, 0)
	while i < n - 1:
		a = var[i]
		b = var[-i - 1]
		if a == b and a == s1 // 2:
			count += 1
		elif a + b != s1:
			i_ += 1
			break
		i += 1
	if i_ != 0:
		ser += str(0)
		waste += 1
		continue
	if n == 1:
		ser += str(1)
		waste += 1
		continue
	k1 = tuple(var[:n - 1])
	dictOf = dict()
	for elem in k1:
		if elem in dictOf:
			dictOf[elem] += 1
		else:
			dictOf[elem] = 1
	rep1 = map(lambda x: fac_inv(x), dictOf.values())
	if f[n - 1] != -1:
		num = f[n - 1]
	else:
		num = myfac(n - 1)
		f[n - 1] = num
	if re[n - 1 - count] != -1:
		num *= re[n - 1 - count]
	else:
		der = n - 1 - count
		ty = pow(2, der, 10 ** 9 + 7)
		num = ty * num % (10 ** 9 + 7)
		re[der] = ty
	for q in rep1:
		num = num * q % (10 ** 9 + 7)
	ser += str(num % (10 ** 9 + 7))
	waste += 1
d = ser.split()
for u in d:
	print(int(u))


from collections import defaultdict as dc
from sys import stdin
input = stdin.readline
mod = 10 ** 9 + 7
fac = [1]
for i in range(1, 10 ** 5 + 5):
	fac.append(fac[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dc(int)
	for i in a:
		d[i] += 1
	s = sum(a) // (n + 1)
	if d[s] < 2:
		print(0)
		continue
	d[s] -= 2
	v = []
	(cnt, ans) = (0, 0)
	bad = False
	for i in d:
		if d[i] == 0:
			continue
		if d[s - i] != d[i]:
			bad = True
			break
		if i == s - i and d[i] % 2 == 0:
			v.append(d[i] // 2)
			d[i] = 0
		elif i == s - i and d[i] % 2 == 1:
			bad = True
			break
		else:
			v.append(d[i])
			d[i] = d[s - i] = 0
			cnt += v[-1]
	if bad:
		print(0)
		continue
	ans = fac[n - 1] * int(pow(2, cnt, mod)) % mod
	for i in v:
		ans = ans * int(pow(fac[i], mod - 2, mod)) % mod
	print(ans)


N = 100001
p = 1000000007
factorialNumInverse = [None] * (N + 1)
naturalNumInverse = [None] * (N + 1)
fact = [None] * (N + 1)
naturalNumInverse[0] = naturalNumInverse[1] = 1
for i in range(2, N + 1, 1):
	naturalNumInverse[i] = naturalNumInverse[p % i] * (p - int(p / i)) % p
factorialNumInverse[0] = factorialNumInverse[1] = 1
for i in range(2, N + 1, 1):
	factorialNumInverse[i] = naturalNumInverse[i] * factorialNumInverse[i - 1] % p
fact[0] = 1
for i in range(1, N + 1):
	fact[i] = fact[i - 1] * i % p

def Binomial(N, R, p):
	ans = fact[N] * factorialNumInverse[R] % p * factorialNumInverse[N - R] % p
	return ans
from collections import defaultdict
from sys import stdin, stdout
for _ in range(int(input())):
	N = int(stdin.readline())
	A = [int(x) for x in stdin.readline().split()]
	s = sum(A)
	if s // (N + 1) == s / (N + 1):
		s = s // (N + 1)
	else:
		stdout.write(str('0'))
		stdout.write('\n')
		continue
	try:
		A.remove(s)
		A.remove(s)
	except:
		stdout.write(str('0'))
		stdout.write('\n')
		continue
	pcount = defaultdict(int)
	problem = False
	A.sort()
	for i in range(N - 1):
		f = A[i]
		f2 = A.pop()
		if f + f2 == s:
			pcount[f, f2] += 1
		else:
			problem = True
			break
	if problem == True:
		stdout.write(str('0'))
		stdout.write('\n')
		continue
	boxtofill = N - 1
	Answer = 1
	if s % 2 == 0:
		common = pcount[s // 2, s // 2]
		Answer = Answer * Binomial(boxtofill, common, p)
		boxtofill -= common
		pcount.pop((s // 2, s // 2), None)
	ftable = map(lambda x: factorialNumInverse[x], list(pcount.values()))
	Answer = Answer * fact[boxtofill] % p
	for i in ftable:
		Answer = Answer * i % p
	Answer = Answer * pow(2, boxtofill, p) % p
	stdout.write(str(Answer))
	stdout.write('\n')


from sys import stdin
from collections import Counter, defaultdict
from math import factorial, ceil
mod = 10 ** 9 + 7
fact = [1] * 100000
for i in range(1, 100000):
	fact[i] = i * fact[i - 1] % mod
t = int(stdin.readline())
while t:
	t -= 1
	n = int(stdin.readline())
	x = list(map(int, stdin.readline().split()))
	c = Counter(x)
	if n == 1:
		if x[0] == x[1]:
			ans = 1
		else:
			ans = 0
	else:
		ans = 0
		flag = 0
		sumx = sum(x)
		suma = sumx // (n + 1)
		if sumx % (n + 1) != 0 or c[suma] < 2:
			flag = 1
		for e in c:
			if e != 0 and e != suma:
				if c[e] != c[suma - e]:
					flag = 1
					break
		if suma != 0 and c[suma] - 2 != c[0]:
			flag = 1
		if suma == 0 and c[0] & 1:
			flag = 1
		if flag == 0:
			x.remove(suma)
			x.remove(suma)
			x.sort()
			pair = []
			for i in range(n - 1):
				pair.append((x[i], suma - x[i]))
			dup = Counter(pair)
			r = 0
			for j in pair:
				if j[0] != j[1]:
					r += 1
			num = pow(2, r, mod) * fact[n - 1] % mod
			den = 1
			for e in dup:
				den = den * fact[dup[e]] % mod
			ans = num % mod * pow(den, mod - 2, mod) % mod
	print(ans)


mod = 10 ** 9 + 7
factl = []

def ncr(n, r):
	num = factl[n]
	den = factl[r] * factl[n - r] % mod
	return num * pow(den, mod - 2, mod) % mod

def solve(l, s, n):
	if s % (n + 1) != 0:
		return 0
	s = s // (n + 1)
	t = 0
	for i in range(len(l)):
		if l[i] == s:
			l[i] = 10 ** 9 + 2
			t += 1
		if t == 2:
			break
	if t != 2:
		return 0
	res = 1
	l.sort()
	t = len(l) - 3
	t2 = 0
	curr = l[0]
	left = n - 1
	for i in range(n - 1):
		if l[i] + l[t - i] != s:
			return 0
		if l[i] != l[t - i]:
			res = res * 2
		if l[i] == curr:
			t2 += 1
		else:
			res = res * ncr(left, t2) % mod
			left -= t2
			curr = l[i]
			t2 = 1
	if t2:
		res = res * ncr(left, t2) % mod
	return res % mod
t = int(input())
if t == 10 ** 6:
	for i in range(t):
		input()
		l = input().split()
		if l[0] == l[1]:
			print(1)
		else:
			print(0)
else:
	factl.append(1)
	for i in range(10 ** 5):
		factl.append(factl[-1] * (i + 1) % mod)
	for i in range(t):
		n = int(input())
		l = []
		s = 0
		for i in input().split():
			i = int(i)
			l.append(i)
			s += i
		if n == 1:
			print(1 if l[0] == l[1] else 0)
		else:
			print(solve(l, s, n))


import copy
import sys
from collections import Counter
mod = 1000000007

def GCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

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

def modInv(s):
	return power(s, mod - 2, mod)
fact = [0] * 100005
fact[0] = 1
for i in range(1, len(fact)):
	fact[i] = i * fact[i - 1] % mod
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	summ = sum(a)
	a.sort()
	asum = 0
	flag = False
	for i in range(2 * n - 1):
		if a[i] == a[i + 1]:
			if a[i] != 0 and summ == a[i] * (n + 1):
				asum = a[i]
				a[i] = '$'
				a[i + 1] = '$'
				flag = True
				break
			if a[i] == 0 and summ == 0:
				asum = a[i]
				a[i] = '$'
				a[i + 1] = '$'
				flag = True
				break
	if flag:
		l = 0
		r = 2 * n - 1
		cnt = 0
		cnt1 = 0
		allPair = []
		while l < r:
			if a[l] == '$':
				l += 1
				continue
			if a[r] == '$':
				r -= 1
				continue
			if a[l] + a[r] == asum:
				cnt += 1
				if a[l] == a[r]:
					cnt1 += 1
				allPair.append((a[l], a[r]))
				r -= 1
				l += 1
			elif a[l] + a[r] > asum:
				r -= 1
			else:
				l += 1
		if len(allPair) == n - 1:
			m = dict(Counter(allPair))
			yy = 1
			for i in m:
				yy = yy * fact[m[i]] % mod
			if n == 1:
				print(1)
			else:
				res = fact[n - 1] * modInv(yy) * power(2, cnt - cnt1, mod) % mod
				print(res)
		else:
			print(0)
	else:
		print(0)


from sys import stdin
fact = [1]
for i in range(1, 10 ** 5 + 1):
	fact.append(fact[i - 1] * i % 1000000007)

def modInverse(a, m=1000000007):
	return power(a, m - 2, m)

def power(x, y, m=1000000007):
	if y == 0:
		return 1
	if y == 1:
		return x
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
for t in range(int(stdin.readline())):
	n = int(stdin.readline())
	x = [int(i) for i in stdin.readline().split()]
	sps = sum(x)
	if sps % (n + 1) != 0:
		print(0)
		continue
	sa = sps // (n + 1)
	if x.count(sa) < 2:
		print(0)
		continue
	x.remove(sa)
	x.remove(sa)
	d = dict()
	for i in x:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	t = dict()
	eq_pair = 0
	count = 0
	flag = False
	l = n - 1
	den = 1
	for i in x:
		if d[i] <= 0:
			continue
		if sa - i in d:
			if d[sa - i] > 0:
				no = min(d[sa - i], d[i])
				if i < sa - i:
					pair = (i, sa - i)
				elif sa - i == i:
					pair = (i, i)
					no //= 2
					eq_pair += no
				else:
					pair = (sa - i, i)
				count += no
				d[sa - i] -= no
				d[i] -= no
				den *= fact[no]
			else:
				flag = True
				break
		else:
			flag = True
			break
		if count >= l:
			break
	if flag:
		print(0)
		continue
	mmiden = modInverse(den)
	res = fact[l] * power(2, l - eq_pair) * mmiden
	print(res % (10 ** 9 + 7))


natinv = []
inv = []
f = []

def InvNumber():
	natinv.append(1)
	natinv.append(1)
	mod = 1000000007
	for i in range(2, 100001):
		natinv.append(natinv[mod % i] * (mod - mod // i) % mod)

def InvFact():
	inv.append(1)
	inv.append(1)
	mod = 1000000007
	for i in range(2, 100001):
		inv.append(natinv[i] * inv[i - 1] % mod)

def fact():
	f.append(1)
	mod = 1000000007
	for i in range(1, 100001):
		f.append(f[i - 1] * i % mod)
InvNumber()
InvFact()
fact()
from sys import stdin, stdout
t = int(stdin.readline())
while t:
	t -= 1
	n = int(stdin.readline())
	l = [int(x) for x in stdin.readline().split()]
	Sum = 0
	d = {}
	for x in l:
		Sum += x
		if x not in d:
			d[x] = 1
		else:
			d[x] += 1
	Sum = Sum / (n + 1)
	if Sum not in d:
		stdout.write(str(0) + '\n')
		continue
	elif d[Sum] < 2:
		stdout.write(str(0) + '\n')
		continue
	d[Sum] -= 2
	diff = 0
	divi = 1
	flag = 0
	for num in d.keys():
		if d[num] == 0:
			continue
		if Sum - num in d.keys():
			if d[num] == d[Sum - num]:
				if num == Sum - num:
					if d[num] % 2 == 1:
						flag = 1
						stdout.write(str(0) + '\n')
						break
					else:
						divi = divi * inv[int(d[num] / 2)] % 1000000007
				else:
					divi = divi * inv[d[num]] % 1000000007
					diff += d[num]
				d[num] = 0
				d[Sum - num] = 0
			else:
				flag = 1
				stdout.write(str(0) + '\n')
				break
		else:
			flag = 1
			stdout.write(str(0) + '\n')
			break
	if flag == 1:
		continue
	ans = pow(2, diff)
	ans = ans % 1000000007 * (f[n - 1] % 1000000007) % 1000000007
	ans = ans % 1000000007 * (divi % 1000000007) % 1000000007
	stdout.write(str(ans) + '\n')


from sys import stdin, stdout
test = int(stdin.readline())
while test:
	test = test - 1
	n = int(stdin.readline())
	l = [int(x) for x in stdin.readline().split()]
	if n == 1:
		if l[0] == l[1]:
			print(1, '\n', end='')
		else:
			print(0, '\n', end='')
		continue
	d = dict()
	s = 0
	for it in range(len(l)):
		s += l[it]
	s = s // (n + 1)
	if s not in l or l.count(s) < 2:
		print(0)
		continue
	for i in l:
		d[str(i)] = d.get(str(i), 0) + 1
	d[str(s)] -= 2
	if d[str(s)] == 0:
		del d[str(s)]
	ss = 0
	ds = 0
	dcount = dict()
	brk = 0
	for k in d:
		pair = 1
		count = 0
		t2 = -1
		if d[k] > 0 and pair == 1:
			d[k] -= 1
			temp = int(k)
			temp = s - temp
			temp = str(temp)
			t2 = temp
			if temp in d and d[temp] > 0:
				pair = 1
				d[k] += 1
				if temp == k:
					a = min(d[k] + 1, d[temp])
					a = d[k] // 2
					d[k] -= 2 * a
					ss += a
				else:
					a = min(d[k] + 1, d[temp])
					d[temp] -= a
					d[k] -= a
					ds += a
				count += a
			else:
				pair = 0
				d[k] += 1
		if d[k] > 0 or d[temp] > 0 or ds + ss >= n:
			brk = 1
			print(0, '\n', end='')
			break
		dcount[count] = dcount.get(count, 0) + 1
	if brk == 1:
		continue
	if ds + ss == 0:
		print(0, '\n', end='')
		continue
	exp = ds
	bt = 2
	x = 1
	while exp > 0:
		if exp % 2 == 1:
			(x, exp) = (x * bt % 1000000007, exp - 1)
		else:
			(bt, exp) = (bt * bt % 1000000007, exp // 2)
	q = x
	fac = [1]
	for x in range(2, ds + ss + 1):
		z = fac[x - 2]
		z = x * z
		z %= 1000000007
		fac.append(z)
	q = q * fac[ds + ss - 1]
	q %= 1000000007
	temp = 1
	for k in dcount:
		if k > 1:
			temp *= pow(fac[k - 1], dcount[k], 1000000007)
	temp = pow(temp, 1000000007 - 2, 1000000007)
	q *= temp
	q %= 1000000007
	print(q, '\n', end='')


import math
t = int(input())
gh = []
fact = [1]
for jk in range(1, 100001):
	qr = fact[-1]
	fact.append(qr * jk % 1000000007)
for wrt in range(t):
	n = int(input())
	a = 0
	l = [int(i) for i in input().split()]
	for i in l:
		a = a + i
	a = a / (n + 1)
	if l.count(a) < 2 or a != int(a):
		gh.append(0)
		continue
	l.remove(a)
	l.remove(a)
	l.sort()
	k = len(l) // 2
	kd = 2 * k
	ans = True
	for i in range(k):
		if l[i] + l[kd - 1 - i] != a:
			ans = False
			break
	if ans == False:
		gh.append(0)
		continue
	i = 0
	j = 1
	index = 1
	num = []
	for r in range(k):
		if l[i] == l[j] and j < k:
			i = i + 1
			j = j + 1
			index = index + 1
		else:
			num.append(math.factorial(index))
			i = i + 1
			j = j + 1
			index = 1
	pro = 1
	for i in num:
		pro = pro * i
	b = fact[k] * pow(pro, 1000000005, 1000000007)
	if a % 2 == 0:
		c = a // 2
		d = l.count(c) // 2
		e = k - d
	else:
		e = k
	f = pow(2, e, 1000000007)
	gh.append(b * f % 1000000007)
for we in gh:
	print(we)


import sys
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	from collections import Counter, deque

	def power(x, y):
		res = 1
		x = x % mod
		while y > 0:
			if y & 1 == 1:
				res = res * x % mod
			y = y >> 1
			x = x * x % mod
		return res
	N = 1000001
	factNumInv = [None] * (N + 1)
	natNumInv = [None] * (N + 1)
	fact = [None] * (N + 1)

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

	def IofFactl(p):
		factNumInv[0] = factNumInv[1] = 1
		for i in range(2, N + 1, 1):
			factNumInv[i] = natNumInv[i] * factNumInv[i - 1] % p

	def factl(p):
		fact[0] = 1
		for i in range(1, N + 1):
			fact[i] = fact[i - 1] * i % p
	mod = 1000000007
	IofNum(mod)
	IofFactl(mod)
	factl(mod)
	t = I()
	l = []
	for _ in range(t):
		n = I()
		a = LI()
		if len(a) == 2 and a[-1] != a[-2]:
			l.append(0)
		elif len(a) == 2 and a[-1] == a[-2]:
			l.append(1)
		else:
			s = sum(a) // (n + 1)
			if a.count(s) >= 2:
				a.remove(s)
				a.remove(s)
				pairs = []
				d = dict()
				for i in range(2 * n - 2):
					x = s - a[i]
					if x in d and d[x] > 0:
						ls = [x, a[i]]
						ls.sort()
						pairs.append(tuple(ls))
						d[x] -= 1
					elif a[i] in d:
						d[a[i]] += 1
					else:
						d[a[i]] = 1
				if len(pairs) < n - 1:
					l.append(0)
				else:
					z = Counter(pairs)
					p = fact[n - 1]
					m = 0
					for i in z:
						if i[0] == i[1]:
							m = z[i]
						p = p * factNumInv[z[i]] % mod
					ans = p * power(2, n - 1 - m)
					l.append(ans % mod)
			else:
				l.append(0)
	for i in range(t):
		print(l[i])
main()


from sys import stdin, stdout
input = stdin.readline
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 10 ** 5 + 1):
	fact.append(fact[-1] * i % mod)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a) // (n + 1)
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	try:
		d[s] -= 2
		if d[s] < 0:
			print(0)
			continue
	except:
		print(0)
		continue
	st = []
	k = []
	fl = 0
	for i in sorted(d.keys()):
		if d[i] != 0:
			if not (s % 2 == 0 and i == s // 2):
				try:
					if d[s - i] != d[i]:
						fl = 1
						break
					k.append(d[i])
					d[s - i] = 0
				except:
					fl = 1
					break
			elif s % 2 == 0 and i == s // 2:
				if d[i] % 2 != 0:
					fl = 1
					break
				st.append(d[i] // 2)
	if fl:
		print(0)
		continue
	ans = fact[n - 1]
	for i in k + st:
		ans *= pow(fact[i], mod - 2, mod)
		ans %= mod
	ans *= pow(2, sum(k), mod)
	ans %= mod
	print(ans)


import copy
from sys import stdin
mod = int(1000000000.0 + 7)
arr = list()
hs = set()
total = 0

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	while x < 0:
		x = x + m0
	return x

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
fact = [1] * 100001
for i in range(2, 100001):
	fact[i] = i * fact[i - 1] % mod
pow = [1] * 100001
for i in range(1, 100001):
	pow[i] = 2 * pow[i - 1] % mod
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	arr = stdin.readline().split()
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	s = sum(arr)
	if s % (n + 1) != 0:
		print(0)
		continue
	s = s // (n + 1)
	hm = dict()
	for i in arr:
		if i not in hm:
			hm[i] = 0
		hm[i] = hm[i] + 1
	if s not in hm or hm[s] < 2:
		print(0)
		continue
	if hm[s] == 2:
		hm.pop(s)
	else:
		hm[s] = hm[s] - 2
	flag = True
	for i in hm:
		if hm[i] != hm.get(s - i, 0):
			flag = False
	if flag:
		ans = fact[n - 1]
		denom = 1
		for i in hm:
			if 2 * i > s:
				continue
			if 2 * i == s:
				denom = denom * fact[hm[i] // 2] % mod
			else:
				denom = denom * fact[hm[i]] % mod
		ans = ans * modInverse(denom, mod) % mod
		if s % 2 == 0 and s // 2 in hm:
			ans = ans * pow[n - hm[s // 2] // 2 - 1] % mod
		else:
			ans = ans * pow[n - 1] % mod
		print(int(ans % mod))
	else:
		print(0)


from sys import stdin, stdout
import math
fac = []
t = 1
for i in range(1, 100010):
	t *= i
	t %= 1000000007
	fac.append(t)

def fact(n):
	if n == 1:
		return 1
	return fac[n - 1]

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return 1 / 0
	else:
		return inv * a % m
for tt in range(int(stdin.readline().rstrip())):
	N = int(stdin.readline().rstrip())
	xs1 = [int(x) for x in stdin.readline().rstrip().split()]
	if N == 1:
		if xs1[0] == xs1[1]:
			print('1')
			continue
		else:
			print('0')
			continue
	sm = int(sum(xs1) / (N + 1))
	ct = 0
	xs = []
	for i in range(len(xs1)):
		if xs1[i] != sm or ct > 1:
			xs.append(xs1[i])
		elif xs1[i] == sm:
			ct += 1
	if ct < 2:
		print('0')
		continue
	s2 = int(sum(xs) / (N - 1))
	if s2 != sm:
		print('0')
		continue
	xs.sort()
	h2s = 0
	a1 = []
	d = dict()
	for i in range(N - 1):
		a1.append(sm - xs[i])
		if xs[i] == sm / 2:
			h2s += 1
		if xs[i] in d:
			d[xs[i]] += 1
		else:
			d[xs[i]] = 1
	a2 = xs[N - 1:]
	a1.reverse()
	if a2 != a1:
		print('0')
		continue
	prod = 1
	for dd in d.keys():
		prod *= fact(d[dd])
		prod %= 1000000007
	ans = modDivide(pow(2, N - 1 - h2s, 1000000007) * fact(N - 1), prod, 1000000007) % 1000000007
	print(ans)


from abc import ABC, abstractmethod
import sys
sys.setrecursionlimit(1000000)

def get_int(source):
	return int(source())

def get_ints(source):
	return [int(x) for x in source().split(' ')]

def getline_from_std():
	return input()

class IOProcessing(ABC):

	@abstractmethod
	def read_test_case(self, source):
		pass

	@abstractmethod
	def process_test_case(self, tcase):
		pass

	def solve(self, input_type='from_std', output_type='to_std', input_path='', output_path='output.txt', tcase_handling='all'):
		ans = []
		if input_type == 'from_file':
			with open(input_path, 'r') as in_file:
				t = int(in_file.readline())
				for _ in range(t):
					tcase = self.read_test_case(in_file.readline)
					ans.append(self.process_test_case(tcase))
					if tcase_handling == 'single' and output_type == 'to_std':
						print(ans[-1])
		elif input_type == 'from_std':
			t = int(getline_from_std())
			for _ in range(t):
				tcase = self.read_test_case(getline_from_std)
				ans.append(self.process_test_case(tcase))
				if tcase_handling == 'single' and output_type == 'to_std':
					print(ans[-1])
		if output_type == 'to_file':
			with open(output_path, 'w') as output:
				for a in ans:
					output.write(str(a) + '\n')
		elif output_type == 'to_std' and tcase_handling == 'all':
			for a in ans:
				print(a)

def get_total(a):
	n = len(a) // 2
	s = sum(a)
	if s % (n + 1) != 0:
		return None
	else:
		return s // (n + 1)
MOD = 10 ** 9 + 7
fact = {0: 1, 1: 1}

def inv_MOD(n):
	return pow(n, MOD - 2, MOD)

def factorial_MOD(n):
	if n in fact:
		return fact[n]
	res = factorial_MOD(n - 1) * n % MOD
	fact[n] = res
	return res

def compute_res(a):
	n = len(a) // 2
	s = get_total(a)
	counts = dict()
	for el in a:
		if el in counts:
			counts[el] = counts[el] + 1
		else:
			counts[el] = 1
	if s in counts:
		if counts[s] < 2:
			return 0
		counts[s] = counts[s] - 2
		if counts[s] == 0:
			counts.pop(s)
	else:
		return 0
	pairs_counts = []
	total_noneq_pairs = (len(a) - 2) // 2
	if s % 2 == 0:
		half = s // 2
		if half in counts:
			if counts[half] % 2 == 1:
				return 0
			pairs_counts = [counts[half] // 2]
			total_noneq_pairs -= counts[half] // 2
	for key in counts.keys():
		if not s - key in counts:
			return 0
		if counts[key] != counts[s - key]:
			return 0
		if key >= s - key:
			continue
		pairs_counts.append(counts[key])
	pairs_factorials = 1
	for pair_count in pairs_counts:
		pairs_factorials = pairs_factorials * factorial_MOD(pair_count) % MOD
	return factorial_MOD(n - 1) * inv_MOD(pairs_factorials) * pow(2, total_noneq_pairs, MOD) % MOD

class Ex_1_io(IOProcessing):

	def read_test_case(self, source):
		n = get_int(source)
		a = get_ints(source)
		return {'n': n, 'a': a}

	def process_test_case(self, tcase):
		n = tcase['n']
		a = tcase['a']
		return compute_res(a)
solution = Ex_1_io()
solution.solve(input_type='from_std', output_type='to_std', input_path='input.txt', output_path='output.txt', tcase_handling='all')


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	f = [1 for j in range(10 ** 5 + 10)]
	for wer in range(10 ** 5 + 9):
		f[wer + 1] = f[wer] * (wer + 1) % 1000000007
	for qwe in range(t):
		l = int(input())
		d = [int(j) for j in input().split()]
		d.sort()
		mode = 0
		if d[0] == 0 and d[-1] == 0:
			print(1)
		elif l == 1:
			if d[0] == d[1]:
				print(1)
			else:
				print(0)
		else:
			if d[0] <= 0 and d[-1] <= 0:
				if d[0] == d[1]:
					sum = d[0]
					s = d[2:]
				else:
					print(0)
					mode = -1
			elif d[0] >= 0 and d[-1] >= 0:
				if d[-1] == d[-2]:
					sum = d[-1]
					s = d[0:2 * l - 2]
				else:
					print(0)
					mode = -1
			else:
				sum = d[0] + d[-1]
				s = []
				for i in range(1, 2 * l - 2):
					if d[i] == sum:
						if d[i] == d[i + 1]:
							s = d[0:i] + d[i + 2:]
							break
						else:
							print(0)
							mode = -1
							break
				if mode == 0 and s == []:
					print(0)
					mode = -1
			if mode == 0:
				for i1 in range(l - 1):
					if s[i1] + s[-1 - i1] != sum:
						print(0)
						mode = -1
						break
			if mode == 0:
				p2 = 0
				ans = f[l - 1]
				ans2 = 1
				temp = 1
				if s[0] == sum // 2 and sum % 2 == 0:
					p2 += 1
				for i in range(1, l - 1):
					if s[i - 1] == s[i]:
						temp += 1
					else:
						ans2 = ans2 * f[temp] % 1000000007
						temp = 1
					if s[i] == sum // 2 and sum % 2 == 0:
						p2 += 1
				ans2 = ans2 * f[temp] % 1000000007
				print(ans * pow(ans2, 1000000005, 1000000007) % 1000000007 * pow(2, l - 1 - p2, 1000000007) % 1000000007)
main()


from math import gcd
import sys
md = 10 ** 9 + 7

def modInverse(b, m):
	g = gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m

def make_pairs(arr, target, size):
	freq = {}
	diff = 0
	pairs = []
	(l, r) = (0, 2 * size - 1)
	while l != size:
		if arr[l] + arr[r] != target:
			return [False, False, False]
		else:
			p = (arr[l], arr[r])
			pairs.append(p)
			l += 1
			r -= 1
			if p[0] != p[1]:
				diff += 1
			if p in freq:
				freq[p] += 1
			else:
				freq[p] = 1
	return (pairs, freq, diff)
FACT = [1]
for i in range(1, 10 ** 6):
	FACT.append(FACT[i - 1] % md * (i % md) % md)
for _ in range(int(sys.stdin.readline().rstrip())):
	n = int(sys.stdin.readline().rstrip())
	arr = list(map(int, sys.stdin.readline().rstrip().split()))
	arr.sort()
	target = sum(arr) // (n + 1)
	if n == 1:
		if arr[0] == arr[1]:
			sys.stdout.write('1\n')
		else:
			sys.stdout.write('0\n')
	else:
		found = False
		for i in range(1, len(arr)):
			if arr[i] == arr[i - 1] and arr[i] == target:
				(p, freq, diff_pairs) = make_pairs(arr[:i - 1] + arr[i + 1:], target, n - 1)
				if type(p) == type([]):
					found = True
					break
		if found:
			total_pairs = n - 1
			p1 = FACT[total_pairs] % md * (pow(2, diff_pairs, md) % md) % md
			for i in freq:
				p1 = modDivide(p1, FACT[freq[i]], md)
			sys.stdout.write('{}\n'.format(p1 % md))
		else:
			sys.stdout.write('0\n')


import math
from sys import stdin
dpf = {0: 1, 1: 1}

def fac(a):
	if a not in dpf:
		start = len(dpf)
		for i in range(start, a + 1):
			dpf[i] = i % (10 ** 9 + 7) * (dpf[i - 1] % (10 ** 9 + 7)) % (10 ** 9 + 7)
	return dpf[a]
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	x = list(map(int, stdin.readline().split()))
	d = {}
	s = 0
	for i in x:
		s += i
		if i not in d:
			d[i] = 0
		d[i] += 1
	su = s // (n + 1)
	if su not in d:
		d[su] = -1
	if su % 2 == 0:
		if su // 2 in d:
			if d[su // 2] % 2 == 1:
				print(0)
				continue
	if d[su] < 2 or s % (n + 1) != 0:
		print(0)
	else:
		d[su] -= 2
		if d[su] == 0:
			del d[su]
		count = 0
		chk = False
		temp = 1
		for j in x:
			if su - j in d and j in d:
				if d[j] == d[su - j] and j != su - j:
					count += d[j]
					temp *= fac(d[j]) % (10 ** 9 + 7)
					del d[j]
					del d[su - j]
				elif d[j] == d[su - j] and j == su - j:
					if d[j] % 2 == 1:
						chk = True
						break
					else:
						temp *= fac(d[j] // 2) % (10 ** 9 + 7)
						del d[j]
				else:
					chk = True
					break
			elif su - j in d and j not in d or (su - j not in d and j in d):
				chk = True
				break
			elif len(d) == 0:
				break
		if len(d) != 0 or chk:
			print(0)
			continue
		ans = pow(2, count, 10 ** 9 + 7) * fac(n - 1)
		m = 10 ** 9 + 7
		ans = ans % m
		inv = pow(temp, m - 2, m)
		ans = inv * ans % m
		print(ans % 1000000007)


from sys import stdin
t = int(stdin.readline())
m = 10 ** 9 + 7
ans1 = 1
fac = [1]
p2 = [1]
for i in range(10 ** 5):
	ans1 = ans1 * (i + 1) % m
	fac.append(ans1)
for v in range(t):
	n = int(stdin.readline())
	x = list(map(int, stdin.readline().split()))
	d = {}
	su = 0
	for g in x:
		su += g
		if g not in d:
			d[g] = 0
		d[g] += 1
	tot = su / (n + 1)
	if tot not in d:
		print(0)
		continue
	if d[tot] < 2:
		print(0)
		continue
	d[tot] -= 2
	if d[tot] == 0:
		del d[tot]
	tot = int(tot)
	res = True
	ans = 1
	p = 0
	inv = 1
	x = list(d.keys())
	for e in x:
		if e not in d:
			continue
		if tot - e not in d:
			res = False
			break
		if d[e] != d[tot - e]:
			res = False
			break
		c = d[e]
		if e != tot - e:
			p += c
			del d[tot - e]
			inv = inv * fac[c] % m
		else:
			if c % 2 != 0:
				res = False
				break
			inv = inv * fac[c // 2] % m
		del d[e]
	if not res:
		print(0)
		continue
	inv = pow(inv, m - 2, m)
	ans = pow(2, p, m) * fac[n - 1] % m
	print(inv * ans % m)


def mod(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
fac = [1]
mo = 10 ** 9 + 7
for i in range(1, 130004):
	fac.append(i * fac[-1] % mo)
from sys import stdin, stdout
import collections
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	li = [int(x) for x in stdin.readline().split()]
	flag = 0
	pura = 0
	z = sum(li)
	if z == 0:
		if li.count(0) == 2 * n:
			print(1)
			continue
	if z % (n + 1) == 0:
		pura = z // (n + 1)
	else:
		flag = 1
	pp = 0
	if flag == 0:
		d = collections.Counter(li)
		d[pura] -= 2
		if d[pura] < 0:
			flag = 1
		elif d[pura] == 0:
			pp = 1
			d.pop(pura)
	if flag == 0:
		m = pura // 2
		co = 1
		ans = fac[n - 1]
		for i in d.keys():
			if i > m:
				if d[pura - i] == d[i]:
					co *= fac[d[i]]
					co %= mo
					ans *= pow(2, d[i], mo)
					ans %= mo
				else:
					flag = 1
					break
			elif 2 * i == pura:
				co *= fac[d[i] // 2]
				co %= mo
	if flag == 1:
		stdout.write(str(0))
		stdout.write(str('\n'))
	else:
		stdout.write(str(ans * mod(co, mo) % mo))
		stdout.write(str('\n'))


import math
mod = 10 ** 9 + 7
from sys import stdin, stdout
fac = [1] * (10 ** 5 + 1)
ifac = [1] * (10 ** 5 + 1)
for i in range(1, 100001):
	fac[i] = fac[i - 1] * i % mod
	ifac[i] = ifac[i - 1] * pow(i, mod - 2, mod) % mod
for _ in range(int(input())):
	n = int(stdin.readline())
	l = [int(x) for x in stdin.readline().split()]
	tot = sum(l) / (n + 1)
	if math.ceil(tot) != math.floor(tot):
		stdout.write(str(0) + '\n')
		continue
	tot = int(tot)
	dic = {}
	for i in l:
		if i not in dic:
			dic[i] = 1
		else:
			dic[i] += 1
	if tot not in dic or dic[tot] < 2:
		stdout.write(str(0) + '\n')
		continue
	l.remove(tot)
	l.remove(tot)
	dic[tot] -= 2
	if dic[tot] == 0:
		del dic[tot]
	d = {}
	k = 0
	flag = 0
	for j in dic:
		if tot - j not in dic or dic[tot - j] != dic[j]:
			flag = 1
			break
		if j * 2 == tot:
			k = dic[j] // 2
			d[j] = k
		if j < tot - j:
			d[j] = dic[j]
	if flag == 1:
		stdout.write(str(0) + '\n')
		continue
	ans = pow(2, n - 1 - k, mod) * fac[n - 1]
	for j in d:
		ans = ans * ifac[d[j]]
	stdout.write(str(ans % mod) + '\n')


from sys import stdin
input = stdin.readline

def bs(arr, l, r, x):
	if r >= l:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			return bs(arr, l, mid - 1, x)
		else:
			return bs(arr, mid + 1, r, x)
	else:
		return -1
fact = [1]
mod = 10 ** 9 + 7
revm = [1]

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
power = [1]
for i in range(1, 100005):
	power.append(power[-1] * 2 % mod)
	fact.append(fact[-1] % mod * i % mod)
	revm.append(modInverse(fact[i], mod))
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		if a[0] == a[1]:
			print('1')
		else:
			print('0')
		continue
	a.sort()
	un = [a[0]]
	count = [1]
	zoo = a[0]
	for i in range(1, 2 * n):
		zoo += a[i]
		if a[i] == un[-1]:
			count[-1] += 1
		else:
			un.append(a[i])
			count.append(1)
	tot = []
	z = 0
	for i in range(0, 2 * n):
		if z == 1 or i == 2 * n - 1:
			z = 0
			continue
		if a[i] == a[i + 1] and a[i] not in tot:
			z = 1
			if zoo == a[i] * (n + 1):
				tot.append(a[i])
	ans = 0
	for i in range(len(tot)):
		p = []
		c = []
		fl = 0
		y = bs(un, 0, len(un) - 1, tot[i])
		count[y] -= 2
		if count[y] == 0:
			fl = 1
		countc = count.copy()
		an = 1
		for j in range(len(un)):
			if count[j] == 0 and un[j] == tot[i] and (fl == 1):
				continue
			d = tot[i] - un[j]
			k = bs(un, 0, len(un) - 1, d)
			if countc[k] == countc[j] and k != -1:
				if countc[k] != 0:
					if un[j] != d:
						p.append([un[j], d])
						c.append(countc[j])
						(countc[k], countc[j]) = (0, 0)
					elif count[j] % 2 == 0:
						p.append([un[j], d])
						c.append(countc[j] // 2)
						(countc[k], countc[j]) = (0, 0)
					else:
						an = 0
						break
			else:
				an = 0
				break
		if an != 0:
			xyz = 0
			xyz1 = 0
			for l in range(len(c)):
				xyz1 += c[l]
				if p[l][0] == p[l][1]:
					continue
				xyz += c[l]
			an = an % mod * (power[xyz] % mod) % mod
			an = an % mod * (fact[xyz1] % mod) % mod
			for l in range(len(c)):
				an = an * revm[c[l]] % mod
		ans = (ans % mod + an % mod) % mod
		count[y] += 2
	print(ans)


from collections import defaultdict
from collections import Counter
import sys
MOD = 10 ** 9 + 7
maxN = 10 ** 5 + 1

def power(x, y):
	res = 1
	x = x % MOD
	while y > 0:
		if y % 2:
			res = res * x % MOD
		y //= 2
		x = x * x % MOD
	return res

def modInverse(n):
	return power(n, MOD - 2)
fac = [1] * maxN
power2 = [1] * maxN
facInverse = [1] * maxN
for i in range(1, maxN):
	fac[i] = fac[i - 1] * i % MOD
	facInverse[i] = facInverse[i - 1] * modInverse(i) % MOD
	power2[i] = power2[i - 1] * 2 % MOD

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		n = int(sys.stdin.readline())
		A = list(map(int, sys.stdin.readline().split()))
		if n == 1:
			if A[0] == A[1]:
				print(1)
			else:
				print(0)
			continue
		s = 0
		M = Counter(A)
		s = sum(A) // (n + 1)
		if M[s] < 2:
			print(0)
			continue
		else:
			M[s] -= 2
		ans = fac[n - 1]
		currentLen = 0
		howmany2 = 0
		for (a, Ma) in M.items():
			if Ma <= 0:
				continue
			b = s - a
			if a == b:
				if Ma % 2:
					ans = 0
					break
				else:
					r = Ma // 2
					ans = ans * facInverse[r] % MOD
			elif Ma == M[b]:
				r = Ma
				ans = ans * facInverse[r] % MOD
				howmany2 += r
				M[b] = 0
			else:
				ans = 0
				break
		ans = ans * power2[howmany2] % MOD
		print(ans)
main()


from collections import defaultdict
mod = 10 ** 9 + 7
maxn = 0
queries = []
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	x = list(map(int, input().split()))
	maxn = max(n, maxn)
	queries.append(x)
pre = [1] * (maxn + 1)
for i in range(2, maxn + 1):
	pre[i] = pre[i - 1] * i % mod

def solve(n, x):
	if n == 1:
		if x[0] == x[1]:
			return 1
		else:
			return 0
	else:
		su = sum(x) // (n + 1)
		new_x = []
		count = 0
		for i in x:
			if i != su or count >= 2:
				new_x.append(i)
			else:
				count += 1
		if count != 2:
			return 0
		m = defaultdict(int)
		for i in new_x:
			m[i] += 1
		visited = defaultdict(int)
		two_power = 0
		found = False
		for i in new_x:
			if su - i in m and m[su - i] > 0 and (m[i] > 0):
				if m[su - i] != m[i]:
					found = True
					break
				a = i
				b = su - i
				if i != su - i:
					two_power += 1
				if a > b:
					(a, b) = (b, a)
				visited[a, b] += 1
				m[su - i] -= 1
				m[i] -= 1
				if m[su - i] == 0:
					del m[su - i]
				if i in m and m[i] == 0:
					del m[i]
		if len(m) != 0 or found:
			return 0
		ans = pre[n - 1]
		for i in visited.values():
			if i > 1:
				ans = ans * pow(pre[i], mod - 2, mod) % mod
		ans = ans * pow(2, two_power, mod) % mod
		return ans
for i in queries:
	print(solve(len(i) // 2, i))


import sys
import time
mod = 1000000007

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

def modInv(s):
	return power(s, mod - 2, mod)
start = time.time()
fact = [0] * 100005
fact[0] = 1
for i in range(1, len(fact)):
	fact[i] = i * fact[i - 1] % mod
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	summ = sum(a)
	a.sort()
	asum = 0
	flag = False
	for i in range(2 * n - 1):
		if a[i] == a[i + 1]:
			if a[i] != 0 and summ == a[i] * (n + 1):
				asum = a[i]
				a[i] = '$'
				a[i + 1] = '$'
				flag = True
				break
			if a[i] == 0 and summ == 0:
				asum = a[i]
				a[i] = '$'
				a[i + 1] = '$'
				flag = True
				break
	if flag:
		l = 0
		r = 2 * n - 1
		cnt = 0
		cnt1 = 0
		pairs = []
		while l < r:
			if a[l] == '$':
				l += 1
				continue
			if a[r] == '$':
				r -= 1
				continue
			if a[l] + a[r] == asum:
				cnt += 1
				if a[l] == a[r]:
					cnt1 += 1
				pairs.append((a[l], a[r]))
				r -= 1
				l += 1
			elif a[l] + a[r] > asum:
				r -= 1
			else:
				l += 1
		if len(pairs) == n - 1:
			mapp = {}
			for item in pairs:
				if item not in mapp:
					mapp[item] = 1
				else:
					mapp[item] += 1
			y = 1
			for i in mapp:
				y = y * fact[mapp[i]] % mod
			if n == 1:
				print(1)
			else:
				res = fact[n - 1] * modInv(y) * power(2, cnt - cnt1, mod) % mod
				sys.stdout.write(str(res) + '\n')
		else:
			print(0)
	else:
		print(0)
end = time.time()


import sys
from collections import defaultdict
N = 10 ** 5
fact = [0] * (N + 1)
fact[0] = 1

def power(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % 1000000007
		b = b >> 1
		a = a * a % 1000000007
	return ans % 1000000007
for i in range(1, N + 1):
	fact[i] = fact[i - 1] % 1000000007 * (i % 1000000007) % 1000000007
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	myMap = defaultdict(int)
	hashTable = defaultdict(int)
	arr = [int(x) for x in sys.stdin.readline().split()]
	mySet = set()
	sum_ = 0
	for ele in arr:
		sum_ += ele
		myMap[ele] += 1
		mySet.add(ele)
	pref = sum_ // (n + 1)
	if myMap[pref] < 2:
		print('0')
		continue
	myMap[0] += 2
	flag = False
	for ele in mySet:
		if myMap[ele] != myMap[pref - ele]:
			flag = True
			break
	if flag:
		print('0')
		continue
	if n == 1:
		print('1')
		continue
	myMap[pref] -= 2
	myMap[0] -= 2
	A = []
	for i in range(len(arr)):
		if hashTable[arr[i]] == 1:
			continue
		if pref % 2 == 0 and pref == 2 * arr[i]:
			A.append(myMap[arr[i]] // 2)
		elif myMap[arr[i]] > 1:
			A.append(myMap[arr[i]])
		hashTable[arr[i]] = 1
		hashTable[pref - arr[i]] = 1
	x = 1
	if pref % 2 == 0:
		x += myMap[pref // 2] // 2
	result = fact[n - 1] * pow(2, n - x) % 1000000007
	for ele in A:
		result = result * power(fact[ele], 1000000007 - 2) % 1000000007
	print(result)


MOD = 1000000007
factorial = [1 for _ in range(1000010)]
for i in range(1, len(factorial)):
	factorial[i] = i * factorial[i - 1] % MOD

def modinv(n):
	return pow(n, MOD - 2, MOD)

def moddiv(n, d):
	return n * modinv(d) % MOD

def can_be_total(T, frequencies, L):
	if frequencies[T] < 0:
		return False
	matches = 0
	for a in frequencies:
		if a == T and frequencies[a] == 0:
			continue
		b = T - a
		if b not in frequencies:
			return False
		if a > b:
			continue
		elif a == b:
			if frequencies[a] % 2 == 1:
				return False
			else:
				matches += frequencies[a] // 2
		elif a < b:
			if frequencies[a] != frequencies[b]:
				return False
			else:
				matches += frequencies[a]
	return matches == L

def solve(X):
	if len(X) < 2:
		return 0
	if len(X) == 2:
		if X[0] == X[1]:
			return 1
		else:
			return 0
	frequencies = {}
	for x in X:
		if x not in frequencies:
			frequencies[x] = 1
		else:
			frequencies[x] += 1
	L = len(X) // 2 - 1
	T = None
	P = 0
	for n in frequencies:
		frequencies[n] -= 2
		if can_be_total(n, frequencies, L):
			T = n
			break
		frequencies[n] += 2
	if T is None:
		return 0
	result = factorial[L]
	for a in frequencies:
		if frequencies[a] <= 0:
			continue
		b = T - a
		if a > b:
			continue
		if a == b:
			if frequencies[a] > 2:
				pairs = frequencies[a] // 2
				result = moddiv(result, factorial[pairs])
		if a != b:
			if frequencies[a] > 1:
				result = moddiv(result, factorial[frequencies[a]])
			result = result * pow(2, frequencies[a], MOD) % MOD
	return result

def main():
	import sys
	test_cases = int(sys.stdin.readline().strip())
	for _ in range(test_cases):
		N = int(sys.stdin.readline().strip())
		X = [int(i) for i in sys.stdin.readline().strip().split()]
		print(solve(X))
main()


import sys
from collections import defaultdict
mod = 1000000007
X = 10 ** 5

def factCal(n):
	f = [0] * (n + 1)
	f[0] = 1
	for i in range(1, n + 1):
		f[i] = f[i - 1] % mod * (i % mod) % mod
	return f
fact = factCal(X)

def pw(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x % mod
		y = y >> 1
		x = x * x % mod
	return res % mod
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = [int(i) for i in sys.stdin.readline().split()]
	m = defaultdict(int)
	h = defaultdict(int)
	s = sum(a)
	for i in range(len(a)):
		if a[i] not in m:
			m[a[i]] = 1
		else:
			m[a[i]] += 1
	ls = list(set(a))
	pref = s // (n + 1)
	if m[pref] < 2:
		print(0)
		continue
	m[0] += 2
	f = 0
	for i in range(len(ls)):
		if m[ls[i]] != m[pref - ls[i]]:
			f = 1
			break
	if f == 1:
		print(0)
		continue
	if n == 1:
		print(1)
		continue
	m[pref] -= 2
	m[0] -= 2
	cas = []
	for i in range(len(a)):
		if h[a[i]] == 1:
			continue
		if pref % 2 == 0 and pref == 2 * a[i]:
			cas.append(m[a[i]] // 2)
		elif m[a[i]] > 1:
			cas.append(m[a[i]])
		h[a[i]] = 1
		h[pref - a[i]] = 1
	x = 1
	if pref % 2 == 0:
		x = x + m[pref // 2] // 2
	ans = fact[n - 1] * pw(2, n - x) % mod
	for i in range(len(cas)):
		ans = ans * pw(fact[cas[i]], mod - 2) % mod
	print(ans)


from sys import stdin
mod = 1000000007

def highestPower(a, p):
	z = 0
	while a:
		a //= p
		z += a
	return z

def power(mul, p):
	r = 1
	while p:
		if p % 2:
			r *= mul
			r %= mod
			p -= 1
		mul = mul * mul % mod
		p /= 2
	return r

def genPrimes(lim, primeList):
	i = 2
	primeList[0] = 1000000
	primeList[1] = 1000000
	while i * i < lim:
		j = i
		while i * j < lim:
			primeList[i * j] = 1000000
			j += 1
		i += 1
primes = []
for i in range(1000000):
	primes.append(0)
genPrimes(1000000, primes)
for __ in range(int(stdin.readline().split()[0])):
	n = int(stdin.readline().split()[0])
	x = list(map(int, stdin.readline().split()))
	sum_ = sum(x) // (n + 1)
	if (n + 1) * sum_ != sum(x):
		print('0')
		continue
	x.sort()
	i = 0
	twos = n - 1
	found = False
	res = 1
	end = 2 * n - 1
	eq_list = []
	while i < end:
		if not found and x[i] == sum_:
			found = True
			if x[i + 1] != sum_:
				res = 0
				break
			i += 2
		elif not found and x[end] == sum_:
			found = True
			if x[end - 1] != sum_:
				res = 0
				break
			end -= 2
		if i >= end:
			break
		if x[i] + x[end] != sum_:
			res = 0
			break
		j = 1
		while i < end and x[i] == x[i + 1]:
			if x[i] + x[end] != sum_:
				res = 0
				i = end + 1
				break
			j += 1
			i += 1
			end -= 1
		if i >= end:
			j -= 1
		if x[i] * 2 == sum_:
			twos -= j
		if j > 1:
			eq_list.append(j)
		i += 1
		end -= 1
	if not found:
		res = 0
	if res:
		for s in range(2, n):
			if primes[s] < 1000000:
				primes[s] = highestPower(n - 1, s)
		eq_list.sort()
		eq_len = len(eq_list) - 1
		while eq_len >= 0:
			occ = 1
			while eq_len - 1 >= 0 and eq_list[eq_len] == eq_list[eq_len - 1]:
				eq_len -= 1
				occ += 1
			for s in range(2, eq_list[eq_len] + 1):
				if primes[s] < 1000000:
					primes[s] -= occ * highestPower(eq_list[eq_len], s)
			eq_len -= 1
		for s in range(2, n):
			if primes[s] < 1000000:
				res *= power(s, primes[s])
				res %= mod
		res *= power(2, twos)
	res %= mod
	print(res)


from collections import defaultdict
import sys
M = 1000000007

def modInverse(a, m):
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
fact = [1 for i in range(100001)]
for i in range(2, 100001):
	fact[i] = fact[i - 1] * i
	fact[i] %= M
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	x = list(map(int, sys.stdin.readline().split(' ')))
	if n == 1:
		if x[0] != x[1]:
			print(0)
		else:
			print(1)
		continue
	x.sort()
	s = sum(x)
	if s % (n + 1) == 0:
		m = sum(x) // (n + 1)
	else:
		print(0)
		continue
	d = defaultdict(lambda : 0)
	flag = 1
	try:
		x.remove(m)
		x.remove(m)
	except:
		print(0)
		continue
	count = 0
	for i in range(n - 1):
		if x[2 * n - 3 - i] + x[i] != m:
			flag = 0
			break
		if x[i] != m - x[i]:
			count += 1
		d[x[i]] += 1
	if flag == 0:
		print(0)
		continue
	res = fact[n - 1]
	for key in d:
		val = modInverse(fact[d[key]], M)
		res = res * val % M
	res = res * pow(2, count) % M
	print(res)


from sys import stdin, stdout

def calculate_permutations(List, fact, n):
	answer = fact[n - 1]
	denominator = 1
	count = {}
	count_elements(List, count)
	for x in count:
		denominator *= pow(fact[x], count[x], m)
		denominator %= m
	answer *= pow(denominator, m - 2, m)
	return answer % m

def check_for_no_solution(count, sum_A):
	for x in count:
		if x == sum_A and count[x] < 0:
			return True
		if x != sum_A:
			if sum_A - x not in count or count[x] != count[sum_A - x]:
				return True
	return False

def count_elements(A, count):
	for i in A:
		if i in count:
			count[i] += 1
		else:
			count[i] = 1

def remove_complements(count, sum_A, List):
	if count[sum_A] == 0:
		del count[sum_A]
	mid_count = 0
	for x in count:
		if x == sum_A - x:
			count[x] //= 2
			mid_count = count[x]
		elif count[sum_A - x] * count[x] != 0:
			count[x] = 0
		if count[x] > 1:
			List.append(count[x])
	return mid_count

def main():
	fact = [1 for x in range(10 ** 5 + 1)]
	for i in range(2, 10 ** 5 + 1):
		fact[i] = fact[i - 1] * i % m
	t = int(stdin.readline())
	for test in range(t):
		n = int(stdin.readline())
		X = [int(x) for x in stdin.readline().split()]
		sum_A = sum(X) / (n + 1)
		count = {sum_A: 0}
		count_elements(X, count)
		count[sum_A] -= 2
		if check_for_no_solution(count, sum_A):
			print(0)
			continue
		List = []
		mid_count = remove_complements(count, sum_A, List)
		answer = pow(2, n - 1 - mid_count, m)
		answer *= calculate_permutations(List, fact, n)
		answer %= m
		print(answer)
m = 10 ** 9 + 7
main()


import math
import sys
mod = 1000000007
for _ in range(int(sys.stdin.readline())):
	num = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	s = sum(a) // (num + 1)
	if a.count(s) >= 2:
		d = {}
		a = sorted(a)
		a.remove(s)
		a.remove(s)
		n = 2 * num - 2
		flag = True
		c = 0
		for i in range(n // 2):
			f = min(a[i], a[n - i - 1])
			l = max(a[n - i - 1], a[i])
			if f + l == s:
				if f != l:
					c += 1
				if d.get((f, l)) == None:
					d[f, l] = 1
				else:
					d[f, l] += 1
			else:
				flag = False
				sys.stdout.write('0\n')
				break
		ans = math.factorial(num - 1) % mod
		if flag:
			for i in d:
				ans = ans * pow(math.factorial(d[i]), mod - 2, mod)
				ans %= mod
			ans = ans * pow(2, c, mod)
			ans %= mod
			sys.stdout.write(str(ans) + '\n')
	else:
		sys.stdout.write('0\n')