AtCoder Beginner Contest 050 - Lining Up

There are N people, conveniently numbered 1 through N.
They were standing in a row yesterday, but now they are unsure of the order in which they were standing.
However, each person remembered the following fact: the absolute difference of the number of the people who were standing to the left of that person, and the number of the people who were standing to the right of that person.
According to their reports, the difference above for person i is A_i.
Based on these reports, find the number of the possible orders in which they were standing.
Since it can be extremely large, print the answer modulo 10^9+7.
Note that the reports may be incorrect and thus there may be no consistent order.
In such a case, print 0.

-----Constraints-----
 - 1≦N≦10^5
 - 0≦A_i≦N-1

-----Input-----
The input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the number of the possible orders in which they were standing, modulo 10^9+7.

-----Sample Input-----
5
2 4 4 0 2

-----Sample Output-----
4

There are four possible orders, as follows:
 - 2,1,4,5,3
 - 2,5,4,1,3
 - 3,1,4,5,2
 - 3,5,4,1,2

Source: atcoder | Difficulty: EASY


Solutions:
mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
c_dic = dict()
if n % 2 == 0:
	for num in a:
		if num % 2 == 0 or n < num:
			print(0)
			return
		if num in c_dic:
			c_dic[num] += 1
			if c_dic[num] > 2:
				print(0)
				return
		else:
			c_dic[num] = 1
	print(pow(2, n // 2, mod))
else:
	for num in a:
		if num % 2 == 1 or n < num:
			print(0)
			return
		if num in c_dic:
			c_dic[num] += 1
			if c_dic[num] > 2:
				print(0)
				return
		else:
			c_dic[num] = 1
	if c_dic[0] != 1:
		print(0)
		return
	print(pow(2, n // 2, mod))


N = int(input())
A = list(map(int, input().split()))
mod = pow(10, 9) + 7
A.sort()
if N % 2 == 0:
	for i in range(N // 2):
		if A[2 * i] != A[2 * i + 1] or A[2 * i] != 2 * i + 1:
			print(0)
			return
	ans = pow(2, N // 2)
	print(ans % mod)
else:
	if A[0] != 0:
		print(0)
		return
	for i in range(N // 2):
		if A[2 * i + 1] != A[2 * (i + 1)] or A[2 * i + 1] != 2 * (i + 1):
			print(0)
			return
	ans = pow(2, N // 2)
	print(ans % mod)


n = int(input())
A = list(map(int, input().split()))
flag = True
if n % 2 == 0:
	if 0 in A or len(set(A)) != n // 2:
		flag = False
elif A.count(0) != 1 or len(set(A)) != (n + 1) // 2:
	flag = False
if flag:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
A = 2 ** (n // 2) % (10 ** 9 + 7)
for i in range(n):
	if i + (i - n + 1) % 2 != a[i]:
		A = 0
print(A)


N = int(input())
A = [int(x) for x in input().split()]
from collections import defaultdict as dd
Dict = dd(lambda : 0)
for a in A:
	Dict[a] += 1
if N & 1:
	Dict[0] += 1
f = (lambda : (lambda x: 0 if x & 1 else 2) if N & 1 else lambda x: 2 if x & 1 else 0)()
Possible = {i: f(i) for i in range(N)}
for (key, value) in list(Dict.items()):
	if value != Possible[key]:
		print(0)
		return
else:
	print(2 ** (N // 2) % 1000000007)


m = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
check = True
if n % 2 == 0:
	if 0 in a or len(set(a)) != n // 2:
		check = False
elif len([0 for i in a if i == 0]) != 1 or len(set(a)) != n // 2 + 1:
	check = False
if check:
	print(2 ** (n // 2) % m)
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
flag = True
if n % 2 == 0:
	if 0 in a or len(set(a)) != n // 2:
		flag = False
elif len([0 for x in a if x == 0]) != 1 or len(set(a)) != n // 2 + 1:
	flag = False
print(2 ** (n // 2) % (10 ** 9 + 7) if flag else '0')


N = int(input())
A = list(map(int, input().split()))
A.sort()
n = N // 2
c = N - 1
for _ in range(n):
	(a, b) = (A.pop(), A.pop())
	if a != c or b != c:
		print(0)
		exit()
	c -= 2
if N % 2 == 1 and A[0] != 0:
	print(0)
	exit()
print(pow(2, n, 10 ** 9 + 7))


iN = int(input())
aA = [int(_) for _ in input().split()]
aA.sort()
iD = 10 ** 9 + 7
iRet = 0
if iN % 2 == 0:
	aR = [x if x % 2 == 1 else x + 1 for x in range(iN)]
else:
	aR = [x if x % 2 == 0 else x + 1 for x in range(iN)]
if aA == aR:
	print(pow(2, iN // 2, iD))
else:
	print(0)


N = int(input())
(*A,) = sorted(map(int, input().split()))

def f(x):
	for i in range(x, N, 2):
		if A[i - 1] != i or A[i] != i:
			return False
	return True
a = True
if N % 2 == 0:
	a = f(1)
elif A[0] != 0:
	a = False
else:
	a = f(2)
print(2 ** (N // 2) % (10 ** 9 + 7) if a else 0)


N = int(input())
A = list(map(int, input().split()))
A.sort()
if N % 2 == 0:
	B = list(range(1, N, 2)) * 2
else:
	B = [0] + list(range(2, N, 2)) * 2
B.sort()
if A != B:
	print(0)
else:
	result = 1
	for i in range(N // 2):
		result *= 2
		result %= 1000000007
	print(result)


n = int(input())
a = sorted(list(map(int, input().split())))
if len(a) % 2 == 1:
	tmp = [0]
	for i in range((len(a) - 1) // 2):
		tmp.append((i + 1) * 2)
		tmp.append((i + 1) * 2)
	if a == tmp:
		ans = 2 ** ((len(a) - 1) // 2) % (10 ** 9 + 7)
	else:
		ans = 0
else:
	tmp = []
	for i in range(len(a) // 2):
		tmp.append(2 * i + 1)
		tmp.append(2 * i + 1)
	if a == tmp:
		ans = 2 ** (len(a) // 2) % (10 ** 9 + 7)
	else:
		ans = 0
print(ans)


n = int(input())
if n == 1:
	if int(input()) == 0:
		print(n)
	else:
		print(0)
	exit()
a = list(map(int, input().split()))
m = 10 ** 9 + 7
x = []
if n % 2 == 1:
	x.append(0)
for i in range(n % 2 + 1, n, 2):
	x.append(i)
	x.append(i)
if sorted(a) == x:
	print(2 ** (n // 2) % m)
else:
	print(0)


n = int(input())
l = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n % 2 == 0:
	d = {i: 2 for i in range(1, n, 2)}
else:
	d = {i: 2 for i in range(0, n, 2)}
	d[0] = 1
for a in l:
	if a in d:
		d[a] -= 1
	else:
		print(0)
		return
for i in d.values():
	if i != 0:
		print(0)
		return
print(2 ** (n // 2) % mod)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n % 2 == 1:
	a.append(0)
a.sort()
odd = tuple(a[::2])
even = tuple(a[1::2])
if odd == even:
	ans = 2 ** (n // 2)
	ans %= mod
	print(ans)
else:
	print(0)


mod = 1000000007
N = int(input())
a = list(map(int, input().split()))
data = [0] * N
for i in a:
	data[i] += 1
cnt = 0
for i in range(1, len(data)):
	if data[i] == 2:
		cnt += 1
	elif data[i] == 0:
		continue
	else:
		print(0)
		exit()
print(pow(2, cnt) % mod)


N = int(input())
a = list(map(int, input().split()))
a_comb = []
mod = 10 ** 9 + 7
for i in range(N):
	a_comb.append(abs(i - (N - 1 - i)))
if sorted(a_comb) == sorted(a):
	print(2 ** (N // 2) % mod)
else:
	print(0)


from collections import Counter
n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
c = Counter(A)
flg = True
for (k, v) in c.items():
	if k == 0:
		if v != 1:
			flg = False
	elif v != 2:
		flg = False
if flg is False:
	print(0)
else:
	print(pow(2, n // 2, mod))


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
lis = [abs(n - 2 * i - 1) for i in range(n)]
a.sort()
lis.sort()
print(pow(2, n // 2, mod)) if a == lis else print(0)


def main():
	N = int(input())
	A = [int(a) for a in input().split(' ')]
	A.sort()
	if N % 2 == 1 and A.count(0) != 1:
		print(0)
		return 0
	elif N % 2 == 0 and A.count(0) > 0:
		print(0)
		return 0
	if N % 2 == 1:
		A.pop(0)
	cnt = 0
	while len(A) > 0:
		if A[0] != A[1] or (len(A) > 2 and A[0] == A[1] and (A[1] == A[2])):
			print(0)
			return 0
		elif A[0] == A[1] == 2 * cnt + N % 2 + 1:
			cnt += 1
			A.pop(0)
			A.pop(0)
		else:
			print(0)
			return 0
	ans = 1
	for p in range(cnt):
		ans = ans * 2 % 1000000007
	print(ans)
main()


N = int(input())
Al = list(map(int, input().split()))
Al.sort()
Bl = []
if N % 2 == 0:
	for i in range(1, N + 1, 2):
		Bl.append(i)
		Bl.append(i)
else:
	Bl.append(0)
	for i in range(2, N + 1, 2):
		Bl.append(i)
		Bl.append(i)
if Al != Bl:
	print(0)
else:
	print(2 ** (N // 2) % (10 ** 9 + 7))


from collections import Counter
n = int(input())
A = list(map(int, input().split()))
cnt_A = Counter(A)
if all([v == 2 for (k, v) in cnt_A.items() if k != 0]):
	print(pow(2, n // 2, 10 ** 9 + 7))
else:
	print(0)


n = int(input())
mod = 10 ** 9 + 7
l = list(map(int, input().split()))
l.sort()
if n % 2 == 1:
	ans = [2 * i for i in range(n // 2 + 1)] + [2 * i for i in range(1, n // 2 + 1)]
	ans.sort()
else:
	ans = [2 * i + 1 for i in range(n // 2)] * 2
	ans.sort()
if l == ans:
	print(2 ** (n // 2) % mod)
else:
	print(0)


n = int(input())
odd = n % 2 == 1
if sorted(list(input().split())) == ['0'] * odd + sorted([str(i) for i in range(1 + odd, n, 2)] * 2):
	cnt = 1
	for i in range(n // 2):
		cnt *= 2
		cnt = cnt % (10 ** 9 + 7)
	print(cnt)
else:
	print(0)


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A = sorted(A)
ans = 1
if N % 2 == 0:
	for i in range(N):
		xx = int(i / 2)
		if A[i] != 2 * xx + 1:
			ans = 0
		elif i % 2 == 1:
			ans *= 2
			ans %= mod
else:
	for i in range(N):
		xx = int((i + 1) / 2)
		if A[i] != 2 * xx:
			ans = 0
		elif i % 2 == 0 and i != 0:
			ans *= 2
			ans %= mod
print(ans)


n = int(input())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7
B = []
for i in range(n):
	if n % 2 == 1:
		B += [2 * ((i + 1) // 2)]
	else:
		B += [i // 2 * 2 + 1]
if A != B:
	print(0)
else:
	ans = 1
	for i in range(n // 2):
		ans *= 2
		ans %= MOD
	print(ans)


from collections import Counter
N = int(input())
A = Counter(list(map(int, input().split())))
Q = 10 ** 9 + 7
ans = 1
for i in range(N - 1, 0, -2):
	if A[i] == 1:
		ans = 0
		break
if N % 2 == 1:
	if A[0] != 1:
		ans = 0
print(ans * pow(2, N // 2, Q))


n = int(input())
l = list(map(int, input().split()))
s = 1
if n % 2 != 0:
	if l.count(0) != 1:
		s = 0
	else:
		l.remove(0)
		if len(set(l)) == (n - 1) // 2:
			s = 2 ** ((n - 1) // 2)
		else:
			s = 0
elif len(set(l)) == n // 2:
	s = 2 ** (n // 2)
else:
	s = 0
print(int(s) % (10 ** 9 + 7))


n = int(input())
a = [int(x) for x in input().split()]
line = [abs(i - (n - i - 1)) for i in range(n)]
if sorted(a) == sorted(line):
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
d = list(c.values())
if n % 2 == 1 and c[0] == 1 and (d.count(2) == (n - 1) // 2) or (n % 2 == 0 and d.count(2) == n // 2):
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = [int(i) for i in input().split()]
check = []
if n % 2 == 0:
	for i in range(1, n, 2):
		check += [i, i]
else:
	check += [0]
	for i in range(2, n, 2):
		check += [i, i]
if check == sorted(a):
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = sorted(list(map(int, input().split())))
if n % 2 == 0:
	for i in range(0, n, 2):
		if a[i] != i + 1 or a[i] != a[i + 1]:
			print(0)
			return
elif a[0] != 0:
	print(0)
	return
else:
	for i in range(1, n, 2):
		if a[i] != i + 1 or a[i] != a[i + 1]:
			print(0)
			return
ans = 1
for i in range(n // 2):
	ans = ans * 2 % (10 ** 9 + 7)
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if n % 2 == 0 and a[::2] == a[1::2]:
	print(2 ** (n // 2) % (10 ** 9 + 7))
elif n % 2 == 1 and a[1::2] == a[2::2]:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
A = sorted(list(map(int, input().split())))
amari = 10 ** 9 + 7
ans = []
han = 0
if N % 2 == 0:
	han = 1
else:
	han = 0
	A.insert(0, 0)
ans = list((int(i) for i in range(han, N, 2)))
ans += ans
ans.sort()
if ans == A:
	print(2 ** (N // 2) % amari)
else:
	print('0')


n = int(input())
a = list(map(int, input().split()))
a.sort()
f = 1
for i in range(n):
	if i % 2 == n % 2 and i + 1 != a[i] or (i % 2 == (n + 1) % 2 and i != a[i]):
		f = 0
		break
if f == 0:
	print(0)
else:
	print(2 ** (n // 2) % (10 ** 9 + 7))


n = int(input())
l = sorted(map(int, input().split()))[::-1]

def f(x):
	t = n + 1
	for i in l[x::2]:
		if t - 2 != i:
			return 0
		t = i
	return 1
print(pow(2, n // 2, 10 ** 9 + 7) * f(0) * f(1))


import collections
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
m = 1000000007
flag0 = 1
count = 0
if N % 2 == 0:
	colA = collections.Counter(A)
	for (key, val) in list(colA.items()):
		if key % 2 != 1 or val != 2:
			flag0 = 0
			break
	for i in range(1, N, 2):
		if i not in list(colA.keys()):
			flag = 0
			break
		else:
			count += 1
else:
	A.append(0)
	colA = collections.Counter(A)
	for (key, val) in list(colA.items()):
		if key % 2 != 0 or val != 2:
			flag0 = 0
			break
	for i in range(0, N, 2):
		if i not in list(colA.keys()):
			flag = 0
			break
		else:
			count += 1
	count -= 1
print(2 ** count % m * flag0)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
d = [0] * (n + 1)
for x in a:
	d[x] += 1
ans = 1
if n % 2 == 0:
	sw = 1
	for (i, x) in enumerate(d):
		if i % 2 != 0:
			if x == 2:
				ans *= 2
				ans %= mod
			else:
				sw = 0
				break
		elif x != 0:
			sw = 0
			break
else:
	sw = 1
	for (i, x) in enumerate(d):
		if i % 2 == 0:
			if i == 0:
				if x != 1:
					sw = 0
					break
			elif x == 2:
				ans *= 2
				ans %= mod
			else:
				sw = 0
				break
		elif x != 0:
			sw = 0
			break
if sw == 0:
	ans = 0
print(ans)


import sys
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
C = Counter(A)
C = sorted(C.items(), key=lambda x: x[0])
if N % 2 == 0:
	s = 1
	for (k, v) in C:
		if k != s or v != 2:
			print(0)
			return
		s += 2
	print(pow(2, N // 2, MOD))
else:
	s = 0
	for (k, v) in C:
		if k == 0:
			if k != 0 or v != 1:
				print(0)
				return
			s += 2
			continue
		if k != s or v != 2:
			print(0)
			return
		s += 2
	print(pow(2, (N - 1) // 2, MOD))


MOD = 1000000007
N = int(input())
A = sorted(list(map(int, input().split())))
m = N % 2
if m == 1 and A[0] != 0:
	print(0)
else:
	for i in range(N // 2):
		if A[2 * i + m] == A[2 * i + 1 + m] == 2 * i + 1 + m:
			continue
		else:
			print(0)
			exit()
	print(2 ** (N // 2) % MOD)


mod = int(1000000000.0) + 7
n = int(input())
a = list(map(int, input().split()))
lis = [0] * n
for i in a:
	lis[i] += 1
for i in range(1, n):
	if lis[i] % 2 == 1:
		print(0)
		exit()
print(pow(2, n // 2, mod))


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
a.sort()
if n % 2 == 1:
	if a[0] != 0:
		print(0)
		return
	else:
		a.remove(0)
		tmp = 2
else:
	tmp = 1
for i in range(n // 2):
	if tmp == a[0] and tmp == a[1]:
		a.remove(tmp)
		a.remove(tmp)
	else:
		print(0)
		return
	tmp += 2
if len(a) == 0:
	print(2 ** (n // 2) % mod)
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
sa = sorted(a)
if n % 2 == 0:
	k = 1
	l = 0
else:
	k = 0
	l = 1
a = 1000000007
flag = True
for (i, s) in enumerate(sa):
	if (i + l) // 2 * 2 + k != s:
		flag = False
if flag:
	print(2 ** (n // 2) % a)
else:
	print(0)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = pow(2, N // 2, mod)
c = Counter(A)
for e in c.items():
	if e[0] == 0 and e[1] >= 2 or e[1] >= 3:
		ans = 0
		break
print(ans)


N = int(input())
box = list(map(int, input().split()))
if N % 2 == 1:
	check = [1] + [2] * N
else:
	check = [2] + [2] * N
for i in box:
	check[i] -= 1
cnt = 0
for i in box:
	if check[i] == 0:
		cnt += 1
	else:
		print(0)
		break
if cnt == len(box):
	print(2 ** (N // 2) % (10 ** 9 + 7))


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
arr = [abs(i - (n - i - 1)) for i in range(n)]
ans = 2 ** (n // 2) % (10 ** 9 + 7) if Counter(a) == Counter(arr) else 0
print(ans)


n = int(input())
a = list(map(int, input().split()))
l = [0] * n
for x in a:
	l[x] += 1
for i in range(n):
	if l[i] > 2:
		print(0)
		return
	if l[i] > 0 and (i + n) % 2 == 0:
		print(0)
		return
if n % 2 == 1 and l[0] > 1:
	print(0)
	return
print(pow(2, n // 2, 10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
flag = 0
A = a.sort()
num = []
if n % 2 == 0:
	for i in range(1, n, 2):
		num.append(i)
		num.append(i)
if n % 2 == 1:
	num = [0]
	for i in range(2, n, 2):
		num.append(i)
		num.append(i)
if num == a:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print('0')


N = int(input())
A = sorted(list(map(int, input().split())))
if N % 2 == 0:
	B = [1 + 2 * (n // 2) for n in range(N)]
else:
	B = [2 * (n // 2) for n in range(1, 1 + N)]
if A == B:
	print(pow(2, N // 2, 10 ** 9 + 7))
else:
	print(0)


import math
n = int(input())
arr = list(map(int, input().split()))
a = True
if n % 2 != 0:
	if len([0 for c in arr if c == 0]) != 1 or len(set(arr)) != int(n / 2) + 1:
		a = False
elif 0 in arr or len(set(arr)) != int(n / 2):
	a = False
if a:
	print(2 ** math.floor(n / 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
b = list(map(int, input().split()))
a = set(b)
flag = 0
if n % 2 == 1:
	if all((i % 2 == 0 for i in a)) and len(a) == (n - 1) // 2 + 1 and (b.count(0) == 1):
		flag = 1
elif all((i % 2 == 1 for i in a)) and len(a) == (n - 1) // 2 + 1:
	flag = 1
print(2 ** (n // 2) % (10 ** 9 + 7) if flag == 1 else 0)


n = int(input())
a = [int(i) for i in input().split()]

def somosomo(a):
	ans = []
	if n % 2 == 1:
		ans.append(0)
		for i in range(1, n // 2 + 1):
			ans.append(i * 2)
			ans.append(i * 2)
		b = sorted(a)
		if b == ans:
			return True
		return False
	else:
		for i in range(1, n // 2 + 1):
			ans.append(i * 2 - 1)
			ans.append(i * 2 - 1)
		b = sorted(a)
		if b == ans:
			return True
		return False

def two_ride(n):
	ans = 1
	for i in range(n):
		ans *= 2
		ans %= 10 ** 9 + 7
	return ans
if somosomo(a):
	print(two_ride(n // 2))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
res = True
anse = list((i for i in range(1, n, 2)))
anso = list((i for i in range(2, n, 2)))
if n % 2 != 0:
	if a[0] != 0:
		res = False
		print(0)
	a = a[1:]
	for i in range(0, len(a), 2):
		if a[i] != anso[i // 2] or a[i + 1] != anso[i // 2]:
			print(0)
			res = False
			break
if n % 2 == 0:
	for i in range(0, len(a), 2):
		if a[i] != anse[i // 2] or a[i + 1] != anse[i // 2]:
			print(0)
			res = False
			break
p = 10 ** 9 + 7
if res:
	print(pow(2, n // 2, p))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
MOD = int(1000000000.0) + 7
if N % 2 == 0:
	c = Counter(A)
	if all((i == 2 for i in c.values())):
		print(pow(2, N // 2, MOD))
	else:
		print(0)
else:
	A.sort()
	A = A[1:]
	c = Counter(A)
	if all((i == 2 for i in c.values())):
		print(pow(2, N // 2, MOD))
	else:
		print(0)


n = int(input())
A = list(map(int, input().split()))
cnt = [abs(i - (n - i - 1)) for i in range(n)]
if sorted(A) == sorted(cnt):
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
	if n > (i + 1) * 2 - 1:
		b.append(n - ((i + 1) * 2 - 1))
	else:
		b.append((i + 1) * 2 - 1 - n)
a.sort()
b.sort()
if a == b:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
s = list(map(int, input().split()))
s_set = set(s)
count = 2 ** (n // 2)
if sum(s) == 2 * sum(s_set):
	print(count % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
flg = 0
a.sort()
if n % 2 == 0:
	if a[0] == 1 and a[1] == 1:
		for i in range(2, n, 2):
			if a[i] == a[i + 1] and a[i - 1] + 2 == a[i]:
				continue
			else:
				flg = 1
				break
	else:
		flg = 1
elif a[0] == 0:
	for i in range(1, n, 2):
		if a[i] == a[i + 1] and a[i - 1] + 2 == a[i]:
			continue
		else:
			flg = 1
			break
else:
	flg = 1
if flg == 1:
	print(0)
else:
	print(2 ** (n // 2) % (10 ** 9 + 7))


n = int(input())
l = sorted(list(map(int, input().split())))
INF = 10 ** 9 + 7
if n % 2 == 0:
	l_tmp = [i // 2 * 2 + 1 for i in range(n)]
else:
	l_tmp = [0] + [i // 2 * 2 + 2 for i in range(n - 1)]
if l != l_tmp:
	print(0)
	exit()
else:
	print(2 ** (n // 2) % INF)


N = int(input())
A = [int(x) for x in input().split()]
from collections import Counter

def f():
	cnt = Counter(A)
	m = N - 1
	for (k, v) in cnt.items():
		if k == 0 and v == 1:
			continue
		if v != 2 or k > m:
			return 0
	return pow(2, N // 2, 10 ** 9 + 7)
print(f())


n = int(input())
a = sorted(list(map(int, input().split())))
DIV = 10 ** 9 + 7
if n % 2 == 1:
	if a[0] != 0:
		print(0)
		exit(0)
	a = a[1:]
	for i in range(len(a)):
		a[i] = a[i] - 1
for i in range(len(a)):
	if a[i] != i + (i % 2 == 0):
		print(0)
		exit(0)
print(2 ** (len(a) // 2) % DIV)


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
N = int(input())
A = list(map(int, input().split()))
B = [0] * N
for a in A:
	B[a] += 1
ok = True
if N % 2 == 1:
	ok = ok and B[0] == 1
	for i in range(1, N):
		ok = ok and B[i] == (2 if i % 2 == 0 else 0)
else:
	for i in range(N):
		ok = ok and B[i] == (0 if i % 2 == 0 else 2)
ans = 1
MOD = int(1000000000.0) + 7
for _ in range(N // 2):
	ans *= 2
	ans %= MOD
print(ans if ok else 0)


import math
N = int(input())
A = list(map(int, input().split()))
flag = True
if N % 2 == 0:
	if 0 in A or len(set(A)) != N // 2:
		flag = False
elif len([0 for a in A if a == 0]) != 1 or len(set(A)) != N // 2 + 1:
	flag = False
if flag:
	print(2 ** math.floor(N / 2) % (10 ** 9 + 7))
else:
	print(0)


def main():
	mod = 1000000007
	n = int(input())
	a = sorted(list(map(int, input().split())))
	if n % 2 == 0:
		if a == [x // 2 * 2 + 1 for x in range(n)]:
			print(2 ** (n // 2) % mod)
			return
	elif a == [0] + [x // 2 * 2 + 2 for x in range(n - 1)]:
		print(2 ** (n // 2) % mod)
		return
	print(0)
main()


N = int(input())
s = list(map(int, input().split()))
if N % 2 == 1:
	s.remove(0)
s = list(sorted(s))
if s[0::2] == s[1::2]:
	print(2 ** (len(s) // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
print([0, 2 ** (n // 2) % (10 ** 9 + 7)][sorted(map(int, input().split())) == [(i + n % 2) // 2 * 2 + 1 - n % 2 for i in range(n)]])


N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N):
	if A[i] != i + (i % 2 == N % 2):
		print(0)
		exit()
print(2 ** (N // 2) % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
if n % 2 == 1:
	a.remove(0)
if a[0::2] == a[1::2]:
	ans = 2 ** (n // 2) % (10 ** 9 + 7)
print(ans)


n = int(input())
a = list(map(int, input().split()))
if n % 2 == 1:
	x = [i for i in range(n)]
	for i in range(n):
		if i % 2 == 1:
			x[i] += 1
else:
	x = [i for i in range(n)]
	for i in range(n):
		if i % 2 == 0:
			x[i] += 1
a.sort()
if x == a:
	print(pow(2, n // 2, 10 ** 9 + 7))
else:
	print(0)


import math
N = 5
ARR = [2, 4, 4, 0, 2]
N = 7
ARR = [6, 4, 0, 2, 4, 0, 2]
N = int(input())
ARR = list(map(int, input().split()))

def calculate(n, arr):
	if n % 2 == 0:
		n = n // 2
		start = 1
		finalResult = pow(2, n, 1000000000 + 7)
	else:
		n = n // 2 + 1
		start = 0
		finalResult = pow(2, n - 1, 1000000000 + 7)
	result = {}
	for i in range(n):
		index = start + 2 * i
		if index == 0:
			result.__setitem__(0, 1)
		else:
			result.__setitem__(index, 2)
	isOk = True
	for i in range(len(arr)):
		if result.get(arr[i]) == None:
			isOk = False
			break
		if result.get(arr[i]) == 0:
			isOk = False
			break
		result.__setitem__(arr[i], result.get(arr[i]) - 1)
	if isOk == False:
		print(0)
		return
	if sum(result.values()) == 0:
		print(finalResult)
	else:
		print(0)
calculate(N, ARR)


N = int(input())
print(2 ** (N // 2) % (10 ** 9 + 7) if sorted(list(map(int, input().split()))) == [i + (i + N + 1) % 2 for i in range(N)] else 0)


from typing import Counter
n = int(input())
lis = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 0
if n % 2 == 0:
	b = Counter(lis)
	flag = 1
	for i in list(b.values()):
		if i == 2:
			pass
		else:
			flag = 0
			break
	if flag:
		ans = 2 ** (n // 2)
		print(ans % mod)
	else:
		print(0)
else:
	lis = sorted(lis)
	lis = lis[1:]
	b = Counter(lis)
	flag = 1
	for i in list(b.values()):
		if i == 2:
			pass
		else:
			flag = 0
			break
	if flag:
		ans = 2 ** (n // 2)
		print(ans % mod)
	else:
		print(0)


from collections import Counter
n = int(input())
c = Counter(list(map(int, input().split())))
ans = 0
for (k, v) in list(c.items()):
	if k == 0:
		if n % 2 == 0 and v > 2:
			print(0)
			return
		elif n % 2 == 1 and v > 1:
			print(0)
			return
	else:
		ans += 1
		if v > 2:
			print(0)
			return
print(pow(2, ans, 10 ** 9 + 7))


N = int(input())
MOD = 10 ** 9 + 7
A = [int(x) for x in input().split()]
flag = 1
set1 = set()
set2 = set()
if N % 2 == 1:
	set1.add(0)
	for j in range(2, N + 1, 2):
		set1.add(j)
		set2.add(j)
	for i in range(N):
		now = A[i]
		if now in set1:
			set1.remove(now)
		elif now in set2:
			set2.remove(now)
		else:
			flag = 0
			break
	if len(set1) != 0 or len(set2) != 0:
		flag = 0
else:
	for k in range(1, N + 1, 2):
		set1.add(k)
		set2.add(k)
	for p in range(N):
		now = A[p]
		if now in set1:
			set1.remove(now)
		elif now in set2:
			set2.remove(now)
		else:
			flag = 0
			break
	if len(set1) != 0 or len(set2) != 0:
		flag = 0
if flag == 0:
	print(0)
else:
	ans = 1
	div2 = N // 2
	for q in range(div2):
		ans *= 2
		ans %= MOD
	print(ans)


N = int(input())
a = list(map(int, input().split()))
Sum = 1
mod = 1000000007
a.sort()
data = []
if N % 2 == 0:
	for i in range(int(N / 2)):
		data.append(1 + i * 2)
		data.append(1 + i * 2)
else:
	data.append(0)
	for i in range(1, N // 2 + 1):
		data.append(i * 2)
		data.append(i * 2)
if a == data:
	for i in range(N // 2):
		Sum *= 2
		Sum %= mod
	print(Sum)
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
a_set = set(a)
if n % 2 == 0:
	if n // 2 != len(a_set) or 0 in a_set:
		print(0)
	else:
		print(2 ** len(a_set) % (10 ** 9 + 7))
elif n // 2 + 1 != len(a_set) or a.count(0) != 1:
	print(0)
else:
	print(2 ** (len(a_set) - 1) % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)

def check():
	if n & 1:
		if c[0] != 1:
			return False
		for i in range((n - 1) // 2):
			if c[2 * (i + 1)] != 2:
				return False
	else:
		for i in range(n // 2):
			if c[2 * i + 1] != 2:
				return False
	return True
if not check():
	print(0)
	return
print(pow(2, n // 2, 10 ** 9 + 7))


mod = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
l = []
for i in range(N):
	l.append(abs(N - 2 * i - 1))
l.sort()
A.sort()
if l != A:
	ans = 0
else:
	ans = pow(2, N // 2, mod)
print(ans)


def main():
	N = int(input())
	A = list(map(int, input().split()))
	if N % 2 == 1:
		A.append(0)
	A.sort()
	ev = tuple(A[::2])
	od = tuple(A[1::2])
	if ev == od:
		comb = 2 ** (N // 2) % 1000000007
		print(str(comb))
	else:
		print('0')
main()


from collections import defaultdict
MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for num in A:
	d[num] += 1
d[0] += 1
if all((d[i] == 2 for i in range((N + 1) % 2, N, 2))):
	print(2 ** (N // 2) % MOD)
else:
	print(0)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mod = int(1000000000.0 + 7)
B = Counter(A)
c = (N + 1) % 2
ans = 1
for (k, v) in B.items():
	if k % 2 != c or (k != 0 and v != 2):
		ans = 0
		break
	ans = ans * v % mod
print(ans)


import sys
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
l = []
for i in range(n):
	li = abs(i - (n - 1 - i))
	l.append(li)
l.sort()
for (ai, li) in zip(l, a):
	if ai != li:
		print(0)
		return
d = Counter(l)
mod = 10 ** 9 + 7
ans = 1
for li in d:
	for j in range(1, d[li] + 1):
		ans *= j
		ans %= mod
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
ans = 2 ** (N // 2)
for i in range(N - 1):
	if i % 2 != 0:
		continue
	elif A[i] != N - (i + 1) or A[i + 1] != N - (i + 1):
		ans = 0
if N % 2 != 0 and A[-1] != 0:
	ans = 0
print(ans % (10 ** 9 + 7))


N = int(input())
(*A,) = sorted(map(int, input().split()))
f = lambda : 2 ** (N // 2) % (10 ** 9 + 7)
a = True
if N % 2 == 0:
	for i in range(1, N, 2):
		if A[i - 1] != i or A[i] != i:
			a = False
			break
elif A[0] != 0:
	a = False
else:
	for i in range(2, N, 2):
		if A[i - 1] != i or A[i] != i:
			a = False
			break
print(f() if a else 0)


n = int(input())
a = list(map(int, input().split()))
test = [abs(n - (2 * k + 1)) for k in range(n)]
if sorted(a) == sorted(test):
	print(pow(2, int(n / 2)) % (pow(10, 9) + 7))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
num_map = [0] * ((n + 2 - 1) // 2)
for i in range(n):
	num_map[a[i] // 2] += 1
res = 1
if n % 2 == 1:
	if num_map[0] != 1:
		print(0)
	else:
		for i in range(1, (n + 2 - 1) // 2):
			if num_map[i] != 2:
				print(0)
				break
			else:
				res = res * 2 % mod
		else:
			print(res)
else:
	for i in range((n + 2 - 1) // 2):
		if num_map[i] != 2:
			print(0)
			break
		else:
			res = res * 2 % mod
	else:
		print(res)


n = int(input())
a = list(map(int, input().split()))
dic = {}
for i in range(n):
	dic.setdefault(a[i], 0)
	dic[a[i]] += 1
ans = 1
for (key, value) in dic.items():
	if n % 2 == 0:
		if n > key and key % 2 == 1 and (value == 2):
			ans *= 2
		else:
			ans = 0
			break
	elif n > key and key % 2 == 0:
		if key == 0 and value == 1:
			ans *= 1
		elif value == 2:
			ans *= 2
		else:
			ans = 0
			break
	else:
		ans = 0
		break
print(ans % (10 ** 9 + 7))


from collections import Counter
(N, *A) = map(int, open(0).read().split())
ac = Counter(A)
if N % 2 == 0:
	for i in range(1, N, 2):
		if ac[i] != 2:
			print(0)
			break
	else:
		print(pow(2, N // 2, 1000000007))
elif ac[0] != 1:
	print(0)
else:
	for i in range(2, N, 2):
		if ac[i] != 2:
			print(0)
			break
	else:
		print(pow(2, N // 2, 1000000007))


N = int(input())
A = list(map(int, input().split()))
A.sort()
flag = N % 2 == 0
if not flag:
	flag = A[0] == 0
if flag:
	index = N % 2
	while index < N:
		if A[index] != index + 1 or A[index] != A[index]:
			flag = False
			break
		index += 2
if flag:
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
A = [int(i) for i in input().split()]
import itertools
count = 0
check = [int(abs(N - i + 1 - i)) for i in range(1, N + 1)]
flag = sorted(A) == sorted(check)
if flag:
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
a_count = Counter(a)
if n % 2 == 1:
	ans = 1
	for i in a_count:
		if i % 2 != 0:
			print(0)
			break
		elif i == 0:
			if a_count[i] != 1:
				print(0)
				break
		elif a_count[i] == 2:
			ans = ans * 2 % (10 ** 9 + 7)
		else:
			print(0)
			break
	else:
		print(ans)
else:
	ans = 1
	for j in a_count:
		if j % 2 != 1:
			print(0)
			break
		elif a_count[j] == 2:
			ans = ans * 2 % (10 ** 9 + 7)
		else:
			print(0)
			break
	else:
		print(ans)


n = int(input())
a = list(map(int, input().split()))
s = set(a)
limit = 10 ** 9 + 7
if sum(a) == 2 * sum(s):
	print(2 ** (n // 2) % limit)
else:
	print(0)


N = int(input())
A = sorted(map(int, input().split()))
print(pow(2, N >> 1, 10 ** 9 + 7) if N & 1 and sorted(list(range(0, N, 2)) + list(range(2, N, 2))) == A or (not N & 1 and sorted(list(range(1, N, 2)) + list(range(1, N, 2))) == A) else 0)


n = int(input())
a = sorted(map(int, input().split()))
if n % 2:
	b = [i if not i % 2 else i + 1 for i in range(n)]
else:
	b = [i if i % 2 else i + 1 for i in range(n)]
if a == b:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
(o, h) = (N % 2, N // 2)
arr = [0] * h
for a in map(int, input().split()):
	if a > 0:
		arr[a // 2 - o] += 1
if all((c == 2 for c in arr)):
	print((1 << h) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
count = [0] * (N + 1)
modz = 10 ** 9 + 7

def junretsu(a):
	if a <= 0:
		return 1
	if a & 1 == 1:
		return 2 * junretsu(a - 1) % modz
	else:
		rr = junretsu(a >> 1)
		return rr * rr % modz
pos = list(map(int, input().split()))
for i in range(N):
	count[pos[i]] += 1
diff = [0] * (N + 1)
for i in range(1, N + 1):
	d = abs(N - i - (i - 1))
	diff[d] += 1
invalid = False
total = 1
for i in range(N):
	if count[i] != diff[i]:
		invalid = True
		break
if invalid:
	print(0)
else:
	print(junretsu(int(N / 2)))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
MOD = 10 ** 9 + 7
for (k, v) in c.items():
	if v != 2:
		if N % 2 == 1 and k == 0:
			continue
		else:
			print('0')
			break
else:
	print(2 ** (N // 2) % MOD)


N = int(input())
A = map(int, input().split())
l = [abs(N - (n * 2 + 1)) for n in range(N)]
if sorted(A) == sorted(l):
	print(pow(2, int(N / 2)) % (pow(10, 9) + 7))
else:
	print(0)


N = int(input())
A = list(map(int, input().split()))
A.sort()
if N % 2 == 1:
	collect = list(range(0, N))[::2] * 2
	collect.remove(0)
elif N % 2 == 0:
	collect = list(range(1, N))[::2] * 2
collect.sort()
if collect != A:
	print(0)
else:
	print(2 ** (N // 2) % (10 ** 9 + 7))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
MOD = 10 ** 9 + 7
corrct = []
t = N - 1
for i in range(N):
	corrct.append(t)
	if i % 2 == 1:
		t -= 2
if all((corrct[i] == A[i] for i in range(N))):
	print(pow(2, N // 2, MOD))
else:
	print(0)


import collections
n = int(input())
a = list(map(int, input().split()))
counter = collections.Counter(a)
ans = 1
for (k, v) in counter.items():
	if k != 0:
		if v == 2:
			ans *= 2
		if v == 1:
			ans = 0
			break
print(ans % (10 ** 9 + 7))


(n, *A) = map(int, open(0).read().split())
if n % 2:
	d = {i: 2 for i in range(0, n, 2)}
	d[0] -= 1
else:
	d = {i: 2 for i in range(1, n, 2)}
for a in A:
	if a in d:
		d[a] -= 1
	else:
		print(0)
		exit()
if any(d.values()):
	print(0)
else:
	print(pow(2, n // 2, 10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n % 2 == 0:
	b = [2 if i % 2 == 1 else 0 for i in range(n)]
else:
	b = [2 if i % 2 == 0 else 0 for i in range(n)]
	b[0] = 1
c = [0 for i in range(n)]
for i in range(n):
	c[a[i]] += 1
if b != c:
	print(0)
else:
	ans = 1
	for i in range(n // 2):
		ans *= 2
		ans %= mod
	print(ans)


n = int(input())
a = list(map(int, input().split()))
l = [0] * n
for i in range(n):
	l[a[i]] += 1
if n % 2 == 1:
	if l[0] != 1:
		print(0)
		return
ans = 1
for i in range(n):
	if n % 2 == 0:
		if i % 2 == 0:
			if l[i] != 0:
				print(0)
				return
	elif i % 2 == 1:
		if l[i] != 0:
			print(0)
			return
	if l[i] == 2:
		ans *= 2
	elif l[i] > 2:
		print(0)
		return
	ans %= 10 ** 9 + 7
print(ans)


n = int(input())
a_list = sorted([int(x) for x in input().split()], reverse=True)
m = n
if m % 2 == 1:
	a_list.append(0)
	m += 1
for i in range(0, m, 2):
	if not a_list[i] == a_list[i + 1] == n - (i + 1):
		print(0)
		return
print(2 ** (n // 2) % (10 ** 9 + 7))


from collections import Counter
N = int(input())
abs_diffs = list(map(int, input().split()))
if N % 2 == 0:
	expected = [i // 2 * 2 + 1 for i in range(N)]
	dims = N // 2
else:
	expected = [(i + 1) // 2 * 2 for i in range(N)]
	dims = (N - 1) // 2
if sorted(abs_diffs) == expected:
	print(2 ** dims % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
import math
x = [0 for _ in range(n)]
if n % 2 != 0:
	x[0] += 1
for i in range(n):
	x[a[i]] += 1
j = True
for t in x:
	if t % 2 != 0:
		j = False
print(2 ** (n // 2) % (10 ** 9 + 7) if j else 0)


n = int(input())
A = list(map(int, input().split()))
d = {}
for a in A:
	d[a] = d.get(a, 0) + 1
zero_cnt = 0
two = 0
no = 0
for i in d:
	if i == 0:
		zero_cnt += 1
	elif d[i] == 2:
		two += 1
	else:
		no += 1
if no != 0 or (n % 2 == 0 and zero_cnt != 0) or (n % 2 == 1 and zero_cnt != 1):
	print(0)
else:
	ans = 1
	mod = 10 ** 9 + 7
	for i in range(two):
		ans *= 2
		ans %= mod
	print(ans % mod)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
mod = 10 ** 9 + 7

def p(p):
	ans = 1
	for i in range(p):
		ans *= 2
		ans %= mod
	return ans
if n % 2 == 1:
	res = True
	for i in range(n):
		if a[i] != (i + 1) // 2 * 2:
			res = False
	if res:
		print(p(n // 2))
	else:
		print(0)
else:
	res = True
	for i in range(n):
		if a[i] != i // 2 * 2 + 1:
			res = False
	if res:
		print(p(n // 2))
	else:
		print(0)


N = int(input())
A = list(map(int, input().split()))
A.sort()
check = [0] * N
for idx in range(N % 2, N, 2):
	check[idx] = idx + 1
	check[idx + 1] = idx + 1
ans = 0
if check == A:
	if N % 2 == 0:
		ans = 2 ** (N // 2) % (10 ** 9 + 7)
	elif N % 2 != 0:
		ans = 2 ** ((N - 1) // 2) % (10 ** 9 + 7)
print(ans)


n = int(input())
nums = sorted(map(int, input().split()))
if n % 2 == 0:
	if nums[::2] != nums[1::2]:
		print(0)
	else:
		print(2 ** (n // 2) % 1000000007)
elif nums[0] == 0 and nums[1::2] == nums[2::2]:
	print(2 ** (n // 2) % 1000000007)
else:
	print(0)


import sys

def input():
	return sys.stdin.readline().strip()
n = int(input())
aa = sorted(map(int, input().split()), reverse=True)
m = n - 1
for i in range(n // 2):
	if aa[2 * i] != m or aa[2 * i + 1] != m:
		print(0)
		sys.exit()
	m -= 2
print(2 ** (n // 2) % (10 ** 9 + 7))


from collections import Counter
(N, *A) = map(int, open(0).read().split())
l = [v for (_, v) in sorted(Counter(A).items())]
if all((v == 2 for v in l[N % 2:])) and (N % 2 == 0 or l[0] == 1):
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
A = list(map(int, input().split()))
set_A = set(A)
ans = 1
if n % 2 == 0:
	if n // 2 != len(set(A)):
		ans = 0
else:
	if A.count(0) != 1:
		ans = 0
	set_A.remove(0)
	if (n - 1) // 2 != len(set_A):
		ans = 0
if ans != 0:
	ans = 2 ** len(set_A)
print(ans % (10 ** 9 + 7))


n = int(input())
l = list(map(int, input().split()))
mod = 10 ** 9 + 7
if n % 2 == 0 and len(set(l)) == n // 2 and (l.count(0) == 0):
	print(2 ** (n // 2) % mod)
elif not n % 2 == 0 and l.count(0) == 1 and (len(set(l)) - 1 == n // 2):
	print(2 ** ((n - 1) // 2) % mod)
else:
	print(0)


N = int(input())
A = [int(x) for x in input().split()]
cnt = {}
if N & 1:
	bit = 1
else:
	bit = 0
for a in A:
	if a & bit:
		ans = 0
		break
	if a in cnt:
		cnt[a] += 1
	else:
		cnt[a] = 1
for key in list(cnt.keys()):
	if key == 0 and cnt[key] != 1:
		ans = 0
		break
	if key != 0 and cnt[key] != 2:
		ans = 0
		break
else:
	ans = 2 ** (N // 2) % 1000000007
print(ans)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
ans = 2 ** (n // 2) % mod
if n % 2 == 0:
	l = n ** 2
else:
	l = (n - 1) * (n + 1)
if sum(a) == l // 2:
	print(ans)
else:
	print(0)


n = int(input())
a = [int(i) for i in input().split()]
a.sort()
f = True
if n % 2 == 0:
	for i in range(n):
		if a[i] != i // 2 * 2 + 1:
			f = False
			break
else:
	for i in range(n):
		if a[i] != (i + 1) // 2 * 2:
			f = False
			break
print(2 ** (n // 2) % (10 ** 9 + 7) if f else 0)


def resolve():
	n = int(input())
	MOD = 10 ** 9 + 7
	S = list(map(int, input().split()))
	if n % 2 == 0:
		sn = (1 + (n - 1)) * (n // 2)
	else:
		sn = (2 + (n - 1)) * (n // 2)
	ss = sum(S)
	print(2 ** (n // 2) % MOD if ss == sn else 0)
resolve()


N = int(input())
A = [int(i) for i in input().split()]
A.sort()
f = True
mod = 10 ** 9 + 7
if N % 2:
	for i in range(N):
		if A[i] != (i + 1) // 2 * 2:
			f = False
else:
	for i in range(N):
		if A[i] != i // 2 * 2 + 1:
			f = False
if f:
	print(2 ** (N // 2) % mod)
else:
	print(0)


N = int(input())
A = map(int, input().split())
if N % 2 == 0:
	if sorted(A) == sorted([i * 2 + 1 for i in range(N // 2)] * 2):
		print(2 ** (N // 2) % (10 ** 9 + 7))
	else:
		print('0')
elif sorted(A) == sorted([(j + 1) * 2 for j in range(N // 2)] * 2 + [0]):
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print('0')


import collections
n = int(input())
list_a = list(map(int, input().split(' ')))
count = collections.Counter(list_a)
flag = True
for (key, value) in count.items():
	if value == 2 or (key == 0 and value == 1):
		pass
	else:
		flag = False
		break
if flag:
	print(2 ** (n // 2) % (7 + 10 ** 9))
else:
	print(0)


n = int(input())
mod = 10 ** 9 + 7
A = list(map(int, input().split()))
from collections import Counter
C = Counter(A)
if n % 2 == 0:
	for i in range(1, n, 2):
		if C.get(i) != 2:
			print(0)
			return
else:
	if C.get(0) != 1:
		print(0)
		return
	for i in range(2, n, 2):
		if C.get(i) != 2:
			print(0)
			return
n //= 2
print(pow(2, n, mod))


n = int(input())
A = sorted(map(int, input().split()))
if n % 2 == 1:
	ex = [0]
	for i in range(n // 2):
		a = 2 * (i + 1)
		ex += [a, a]
else:
	ex = []
	a = 1
	for i in range(n // 2):
		ex += [a, a]
		a += 2
ans = 0
if A == ex:
	ans = 2 ** (n // 2) % (10 ** 9 + 7)
print(ans)


n = int(input())
int_a = list(map(int, input().split()))
if n % 2 == 0:
	kakeru = n
else:
	kakeru = n + 1
if sum(int_a) == kakeru * (n // 2):
	syou = n // 2
	answer = 2 ** syou
	print(answer % (10 ** 9 + 7))
else:
	print('0')


import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(MAP())

def NIJIGEN(H):
	return [list(input()) for i in range(H)]
mod = 1000000007
N = INT()
L = LIST()
if N % 2 == 0:
	A = range(1, N, 2)
	B = range(1, N, 2)
else:
	A = range(0, N, 2)
	B = range(2, N, 2)
(A, B) = (list(A), list(B))
A = A + B
if sorted(A) == sorted(L):
	print(pow(2, N // 2, mod))
else:
	print(0)


import collections
N = int(input())
B = []
g = 10 ** 9 + 7
A = [int(i) for i in input().split()]
for i in A:
	B.append(((N - 1 + i) / 2, (N - 1 - i) / 2))
c = collections.Counter(B)
d = 1
for (i, j) in c.items():
	d *= j
	if j == 1 and i[0] != i[1]:
		d = 0
		break
	if d > g:
		d = d % g
print(d % g)


N = int(input())
A = sorted(list(map(int, input().split())))
P = 10 ** 9 + 7
if N % 2 == 0:
	check = [i if i % 2 == 1 else i + 1 for i in range(N)]
else:
	check = [i if i % 2 == 0 else i + 1 for i in range(N)]
if A == check:
	ans = 1
	for i in range(N // 2):
		ans *= 2
		ans %= P
else:
	ans = 0
print(ans)


n = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7
niseven = n % 2 == 0
cd = dict()
for a in A:
	cd.setdefault(a, 0)
	cd[a] += 1
	if a == 0 and cd[a] > 1:
		print(0)
		break
	if a > 0 and cd[a] > 2:
		print(0)
		break
	if (a % 2 == 0) == niseven:
		print(0)
		break
else:
	print(pow(2, n // 2, mod))


from collections import Counter
N = int(input())
A = [0] + list(map(int, input().split()))
p = 10 ** 9 + 7
l = Counter(A)
flag = True
for i in range(N % 2 == 0, N, 2):
	if l[i] != 2:
		flag = False
		break
if flag:
	print(pow(2, N // 2, p))
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
from collections import Counter
c = Counter(a)
for i in range(0 + (n % 2 ^ 1), n, 2):
	if i == 0 and c.get(0, 0) != 1:
		print(0)
		exit()
	elif i > 0 and c.get(i, 0) != 2:
		print(0)
		exit()
print(2 ** (n // 2) % mod)


N = int(input())
A = list(map(int, input().split()))
A.sort()
mod = 10 ** 9 + 7
if N % 2 == 0:
	for i in range(N):
		if A[i] != 1 + i // 2 * 2:
			print(0)
			break
	else:
		print(pow(2, N // 2, mod))
elif A[0] == 0:
	for i in range(1, N):
		if A[i] != (i + 1) // 2 * 2:
			print(0)
			break
	else:
		print(pow(2, N // 2, mod))


n = int(input())
a = sorted(list(map(int, input().split())))
if n % 2 == 0:
	if a == sorted(2 * [2 * x + 1 for x in range(int(n / 2))]):
		print(2 ** int(n / 2) % 1000000007)
	else:
		print(0)
elif a == sorted(list(2 * [2 * x for x in range(n // 2 + 1)])[1:]):
	print(2 ** (n // 2) % 1000000007)
else:
	print(0)


N = int(input())
a = [int(i) for i in range(-(N % 2 - 1), N, 2)]
if sum(list(map(int, input().split()))) == sum(a) * 2:
	D = 10 ** 9 + 7
	print(2 ** (N // 2) % D)
else:
	print(0)


import collections
n = int(input())
l = list(input().split())
c = collections.Counter(l)
if n % 2 == 0:
	f = all((x == 2 for x in c.values()))
else:
	g = c.pop('0') == 1
	f = all((x == 2 for x in c.values())) and g
print(2 ** (n // 2) % 1000000007 if f == True else 0)


N = int(input())
S = list(map(int, input().split()))
lenS = len(S)
T = []
for i in range(1, N + 1):
	T.append(abs(i - (N + 1 - i)))
T.sort()
S.sort()
for i in range(N):
	if T[i] != S[i]:
		print(0)
		return
ans = 1
nagasa = lenS // 2
for i in range(nagasa):
	ans = ans * 2 % (10 ** 9 + 7)
print(ans)


import collections
N = int(input())
A = list(map(int, input().split()))
ans = 1
if 0 in A:
	A.remove(0)
Acounter = collections.Counter(A)
for i in Acounter.values():
	if i == 2:
		continue
	else:
		ans = 0
		break
if ans == 0:
	pass
if ans != 0:
	for i in range(N // 2):
		ans = ans * 2 % (10 ** 9 + 7)
print(ans)


import sys
n = int(input())
a = sorted(list(map(int, input().split())))
for i in range(n):
	if a[i] != 2 * ((i + 2 - n % 2) // 2) + n % 2 - 1:
		print(0)
		sys.exit()
print(pow(2, n // 2, 1000000007))


import collections
n = int(input())
a = list(map(int, input().split()))
cnt = collections.Counter(a)
mod = 7 + 10 ** 9
if n % 2 == 0:
	for i in range(1, 1 + n // 2):
		if i * 2 - 1 not in cnt.keys() or cnt[i * 2 - 1] != 2:
			print(0)
			return
else:
	if 0 not in cnt.keys() or cnt[0] != 1:
		print(0)
		return
	for i in range(1, 1 + n // 2):
		if i * 2 not in cnt.keys() or cnt[i * 2] != 2:
			print(0)
			return
print(2 ** (n // 2) % mod)


N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [abs(i) for i in range(-N + 1, N, 2)]
B.sort()
result = pow(2, N // 2, 10 ** 9 + 7) if A == B else 0
print(result)


n = int(input())
a = sorted(list(map(int, input().split())))
flag = 0
if n % 2 == 1 and a.pop(0) != 0:
	flag = 1
for i in range(n // 2):
	if a[i * 2] == a[i * 2 + 1] == (i + 1) * 2 - 1 + n % 2:
		pass
	else:
		flag = 1
print(0 if flag else 2 ** (n // 2) % (10 ** 9 + 7))


from collections import Counter
N = int(input())
(l, m) = (N % 2, N // 2)
c = Counter([a // 2 - l for a in map(int, input().split())])
print((1 << m) % (10 ** 9 + 7) if all((c[i] == 2 for i in range(m))) else 0)


n = int(input())
l = sorted(list(map(int, input().split())))
if n % 2 == 1:
	testl = sorted([2 * i for i in range(len(l) // 2 + 1)] * 2)[1:]
else:
	testl = sorted([2 * i + 1 for i in range(len(l) // 2)] * 2)
if l == testl:
	print(2 ** (len(l) // 2) % (10 ** 9 + 7))
else:
	print(0)


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

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

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

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

def LSS():
	return input().split()

def resolve():
	N = I()
	A = LI()
	if N % 2 == 0:
		if sorted(A) == [i // 2 * 2 + 1 for i in range(N)]:
			print(pow(2, N // 2, MOD))
		else:
			print(0)
	elif sorted(A) == [(i // 2 + 1) * 2 for i in range(-1, N - 1)]:
		print(pow(2, (N - 1) // 2, MOD))
	else:
		print(0)

def __starting_point():
	resolve()
__starting_point()


N = int(input())
MOD = 1000000007
A = list(map(int, input().split()))
cnt = [0 for i in range(N)]
for i in range(N):
	cnt[A[i]] += 1
if N % 2 == 0:
	for i in range(1, N, 2):
		if cnt[i] != 2:
			print(0)
			break
	else:
		print(2 ** (N // 2) % MOD)
elif cnt[0] != 1:
	print(0)
else:
	for i in range(2, (N + 1) // 2, 2):
		if cnt[i] != 2:
			print(0)
			break
	else:
		print(2 ** ((N - 1) // 2) % MOD)


n = int(input())
a = list(map(int, input().split()))
a.sort()
try:
	for (i, a_i) in enumerate(a):
		if n % 2 == 1:
			assert a_i == (i + 1) // 2 * 2
		else:
			assert a_i == i // 2 * 2 + 1
	answer = pow(2, n // 2, 10 ** 9 + 7)
except AssertionError:
	answer = 0
print(answer)


i = input
n = int(i())
print([0, pow(2, n // 2, 10 ** 9 + 7)][sorted(i().split(), key=int) == [str((j + n % 2) // 2 * 2 + 1 - n % 2) for j in range(n)]])


n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
num = 0
judge = 0
if len(a) % 2 == 1:
	if a[0] == 0:
		for i in range(1, n, 2):
			if a[i] == i + 1 and a[i + 1] == i + 1:
				num += 1
			else:
				print(0)
				judge = 1
				break
	else:
		print(0)
		judge = 1
else:
	for i in range(0, n, 2):
		if a[i] == i + 1 and a[i + 1] == i + 1:
			num += 1
		else:
			print(0)
			judge = 1
			break
if judge == 0:
	result = 2 ** num % (10 ** 9 + 7)
	print(result)


n = int(input())
a = sorted(list(map(int, input().split())))
if n % 2 == 0:
	(b, s) = ([1, 1], 3)
else:
	(b, s) = ([0], 2)
for i in range(s, n, 2):
	b += [i, i]
if a == b:
	print(pow(2, n // 2, 1000000007))
else:
	print(0)


N = int(input())
A = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7
if N % 2:
	arr = sorted([0] + list(range(2, N))[::2] * 2)
else:
	arr = sorted(list(range(1, N))[::2] * 2)
print(2 ** (N // 2) % MOD if A == arr else 0)


N = int(input())
A = sorted([int(a) for a in input().split()])
B = [(i + 1) // 2 * 2 for i in range(N)] if N % 2 else [i // 2 * 2 + 1 for i in range(N)]
print(pow(2, N // 2, 10 ** 9 + 7) if A == B else 0)


N = int(input())
A = [int(a) for a in input().split()]
mod = 10 ** 9 + 7
A.sort(reverse=True)
i = 0
ans = 1
while i < N - 1:
	if A[i] == A[i + 1] and A[i] == N - i - 1:
		ans *= 2
		ans %= mod
		i += 2
	else:
		ans = 0
		break
if N % 2 == 1 and A[-1] != 0:
	ans = 0
print(ans)


import sys
from collections import deque
p = 10 ** 9 + 7

def main(n, a):
	h = n // 2
	g = n % 2
	a.sort()
	c = [2 * (x // 2) + g + 1 for x in range(n - g)]
	if g == 1:
		c.insert(0, 0)
	if a != c:
		return 0
	return 2 ** (h % (p - 1)) % p

def __starting_point():
	n = int(input())
	a = list(map(int, sys.stdin.readline().strip().split()))
	print(main(n, a))
__starting_point()


N = int(input())
N_List = sorted(list(map(int, input().split())))
flg = 0
ans = 1
if N % 2 == 1:
	if N_List[0] != 0:
		flg = 1
	else:
		for i in range(2, N, 2):
			if i * 2 != sum(N_List[i - 1:i + 1]):
				flg = 1
				break
			else:
				ans = ans * 2 % (10 ** 9 + 7)
else:
	for i in range(1, N, 2):
		if i * 2 != sum(N_List[i - 1:i + 1]):
			flg = 1
			break
		else:
			ans = ans * 2 % (10 ** 9 + 7)
if flg == 0:
	print(ans)
else:
	print(0)


n = int(input())
A = list(map(int, input().split()))
r = n % 2
d = [0] * n
for a in A:
	if a % 2 == r:
		print(0)
		break
	d[a] += 1
	if d[a] > 2 or (a == 0 and d[0] > 1):
		print(0)
		break
else:
	print(2 ** (n // 2) % (10 ** 9 + 7))


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
numbers = Counter(list(range(not N % 2, N, 2)) * 2)
if N % 2:
	numbers[0] = 1
if Counter(A) == numbers:
	print(pow(2, N // 2, int(10 ** 9 + 7)))
else:
	print(0)


from collections import Counter
N = int(input())
A = list(map(int, input().split()))
if N % 2 == 0:
	B = list(range(N - 1, 0, -2)) + list(range(1, N, 2))
else:
	B = list(range(N - 1, 0, -2)) + list(range(0, N, 2))
if Counter(A) != Counter(B):
	print(0)
else:
	mod = 10 ** 9 + 7
	print(2 ** (N // 2) % mod)


n = int(input())
A = sorted(map(int, input().split()))
G = sorted([2 * (i + 1) for i in range(n // 2)] * 2 + [0])
K = sorted([2 * i + 1 for i in range(n // 2)] * 2)
if n % 2:
	if A != G:
		print(0)
		exit()
elif A != K:
	print(0)
	exit()
print(2 ** (n // 2) % (10 ** 9 + 7))


import io
data = int(input())
array = list(map(int, input().split()))
array.sort()
modulus = 10 ** 9 + 7
result = 2 ** (data // 2) % modulus
array2 = []
for i in range(data):
	array2 += [abs(data + 1 - 2 * (i + 1))]
array2.sort()
if array == array2:
	print(result)
else:
	print(0)


N = int(input())
l = list(map(int, input().split()))
a = 1
if N % 2 == 0:
	if len(l) != len(set(l)) * 2:
		a = 0
elif l.count(0) == 1:
	l.remove(0)
	if len(l) != 2 * len(set(l)):
		a = 0
else:
	a = 0
if a:
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = sorted(list(map(int, input().split())))
if n % 2 == 1:
	if a[0] == 0 and all((a[i] == 2 * ((i + 1) // 2) for i in range(1, n))):
		print(2 ** (n // 2) % (10 ** 9 + 7))
	else:
		print(0)
elif all((a[i] == 2 * (i // 2) + 1 for i in range(n))):
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
A = list(map(int, input().split()))
ans = 0
A_test = sorted(list(set(A)))
if N % 2 == 1:
	judge = [i for i in range(0, N, 2)]
	if A_test == judge and A.count(0) == 1:
		ans = 2 ** (N // 2)
else:
	judge = [i for i in range(1, N, 2)]
	if A_test == judge:
		ans = 2 ** (N // 2)
ans = ans % (10 ** 9 + 7)
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
judge = 0
if n % 2 == 1:
	for i in range(n):
		if A[i] != 2 * ((i + 1) // 2):
			judge += 1
			break
else:
	for i in range(n):
		if A[i] != 2 * (i // 2) + 1:
			judge += 1
			break
if judge == 1:
	print(0)
else:
	print(2 ** (n // 2) % (10 ** 9 + 7))


def PowerMod(N, P, Mod):
	if N % Mod == 0:
		return 0
	else:
		PowM = 1
		for TP in range(1, P + 1):
			PowM = PowM * N % Mod
		return PowM
from collections import Counter
N = int(input())
A = sorted(Counter([int(T) for T in input().split()]).most_common(), key=lambda X: X[0])
PassFlag = True
if N % 2 == 1:
	for TA in range(0, (N + 1) // 2):
		if A[TA][0] != 2 * TA or A[TA][1] != 1 + (A[TA][0] != 0):
			PassFlag = False
			break
	print([0, PowerMod(2, (N - 1) // 2, 10 ** 9 + 7)][PassFlag])
else:
	for TA in range(0, N // 2):
		if A[TA][0] != 2 * TA + 1 or A[TA][1] != 2:
			PassFlag = False
			break
	print([0, PowerMod(2, N // 2, 10 ** 9 + 7)][PassFlag])


n = int(input())
s = list(map(int, input().split()))
s = list(sorted(s))
if n % 2 == 1:
	s.remove(0)
	for i in range(n - 1):
		s[i] -= 1
a = []
for i in range(n // 2):
	a.append(2 * i + 1)
if s[0::2] == s[1::2] and s[0::2] == a:
	print(2 ** (len(s) // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
(*l,) = map(int, input().split())
l.sort()
mod = 10 ** 9 + 7
A = 2 ** (n // 2) % mod
for i in range(n):
	if i + (i - n + 1) % 2 != l[i]:
		A = 0
print(A)


n = int(input())
A = list(map(int, input().split()))
A.sort()
MOD = 10 ** 9 + 7
ans = 0
if n % 2 != 0:
	a = list(range(0, n, 2))
	a = sorted(a + a[1:])
	if a == A:
		ans = 2 ** ((n - 1) // 2) % MOD
else:
	a = sorted(list(range(1, n, 2)) * 2)
	if a == A:
		ans = 2 ** (n // 2) % MOD
print(ans)


n = int(input())
from collections import Counter as co
c = co(map(int, input().split()))
ans = pow(2, n // 2, 10 ** 9 + 7)
if n % 2:
	if 0 not in c or c[0] > 1:
		ans = 0
	for i in range(1, n):
		if i % 2 == 0:
			if i not in c or c[i] != 2:
				ans = 0
				break
		elif i in c:
			ans = 0
			break
else:
	if 0 in c:
		ans = 0
	for i in range(1, n):
		if i % 2:
			if i not in c or c[i] != 2:
				ans = 0
				break
		elif i in c:
			ans = 0
			break
print(ans)


N = int(input())
A = list(map(int, input().split()))
A.sort()
if N % 2 == 0:
	check = [2 * i + 1 for i in range((N - 1) // 2 + 1)] * 2
	check.sort()
else:
	check = [2 * (i + 1) for i in range(N // 2)] * 2
	check.append(0)
	check.sort()
if check == A:
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


from collections import *
N = int(input())
if N % 2:
	if Counter(map(int, input().split())) == Counter((i // 2 * 2 for i in range(1, N + 1))):
		print(2 ** (N // 2) % (10 ** 9 + 7))
	else:
		print(0)
elif Counter(map(int, input().split())) == Counter((i // 2 * 2 + 1 for i in range(N))):
	print(2 ** (N // 2) % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
m = [2 * ((i - 1 + N % 2) // 2) + 1 - N % 2 for i in range(1, N + 1)]
for (i, a) in enumerate(sorted([int(a) for a in input().split()])):
	if m[i] != a:
		ret = 0
		break
else:
	ret = 2 ** (N // 2)
print(ret % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
arr = []
if n % 2 == 0:
	for i in range(1, n, 2):
		arr += [i, i]
else:
	arr += [0]
	for i in range(2, n, 2):
		arr += [i, i]
if sorted(a) != sorted(arr):
	print(0)
	exit()
print(pow(2, n // 2, MOD))


n = int(input())
A = [int(x) for x in input().split()]
Bi = []
if n % 2 == 0:
	half_Bi = list(range(1, n, 2))
	Bi = half_Bi + half_Bi
else:
	half_Bi = list(range(2, n, 2))
	Bi = half_Bi + half_Bi
	Bi.append(0)
A.sort()
Bi.sort()
if A != Bi:
	print(0)
	exit()
print(2 ** (n // 2) % (10 ** 9 + 7))


n = int(input())
q = [int(x) for x in input().split(' ')]
q_set = set(q)
if n % 2 == 1:
	count = 2 ** ((n - 1) // 2)
else:
	count = 2 ** (n // 2)
if sum(q) == 2 * sum(q_set):
	print(count % (10 ** 9 + 7))
else:
	print(0)


N = int(input())
K = [0 for i in range(N + 1)]
A = list(map(int, input().rstrip().split(' ')))
ans = 1
for i in A:
	K[i] += 1
for i in range(N):
	if i != 0 and K[i] != 0 and (K[i] != 2):
		ans = 0
		break
	if K[i] == 2:
		ans *= 2
		ans %= 10 ** 9 + 7
print(ans)


n = int(input())
ai = [int(x) for x in input().split()]
if (ai.count(0) == 0 or ai.count(0) == 1) and len(set(ai)) == -(-n // 2):
	ans = 1
	for i in range(n // 2):
		ans *= 2
		ans %= 10 ** 9 + 7
	print(ans)
else:
	print(0)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
if 1 in c.values() and c[0] != 1 or 3 in c.values():
	print(0)
elif n % 2 == 0:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(2 ** ((n - 1) // 2) % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)
check_ary = []
if n & 1:
	check_ary.append(0)
for i in range(n // 2):
	for _ in range(2):
		check_ary.append((i + 1) * 2 if n & 1 else i * 2 + 1)
c2 = Counter(check_ary)
if c != c2:
	print(0)
	return
print(pow(2, n // 2, 10 ** 9 + 7))


from collections import Counter
n = int(input())
a = Counter(list(map(int, input().split())))
ans = 1
for (i, v) in a.items():
	if i == 0:
		if v != 1:
			print(0)
			exit()
	elif v != 2:
		print(0)
		exit()
	else:
		ans = ans * 2 % (10 ** 9 + 7)
print(ans)


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
if n % 2 == 0 and c[0] != 0 or (n % 2 == 1 and c[0] != 1):
	print(0)
	return
ans = 1
mod = 10 ** 9 + 7
for i in c:
	if c[i] == 2:
		ans *= 2
		ans %= mod
	if c[i] >= 3:
		print(0)
		return
print(ans)


n = int(input())
l = sorted(map(int, input().split()))
mod = 10 ** 9 + 7
if n % 2 == 1:
	for i in range(n):
		if l[i] != i + i % 2:
			print(0)
			break
	else:
		print(pow(2, n // 2, mod))
else:
	for i in range(n):
		if l[i] != i + (i + 1) % 2:
			print(0)
			break
	else:
		print(pow(2, n // 2, mod))


N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
if N % 2 == 1:
	D = [0]
	for i in range(N - 1):
		D.append(i // 2 * 2 + 2)
	if B == D:
		print(2 ** ((N - 1) // 2) % (10 ** 9 + 7))
	else:
		print(0)
else:
	D = [i // 2 * 2 + 1 for i in range(N)]
	if B == D:
		print(2 ** (N // 2) % (10 ** 9 + 7))
	else:
		print(0)


MOD = 10 ** 9 + 7
n = int(input())
xs = list(map(int, input().split()))
cnt = [0 for _ in range(n)]
for x in xs:
	cnt[x] += 1
res = 1
if n % 2 == 0:
	s = 1
else:
	s = 2
	if cnt[0] != 1:
		res = 0
for i in range(s, n, 2):
	if cnt[i] != 2:
		res = 0
	res *= 2
	res %= MOD
print(res)


i = int(input())
a = list(sorted(map(int, input().split())))
if i % 2 == 1:
	b = [0] + [u for u in range(2, i, 2) for t in range(2)]
	if a == b:
		print(2 ** (i // 2) % (10 ** 9 + 7))
	else:
		print(0)
else:
	b = [u for u in range(1, i, 2) for t in range(2)]
	if a == b:
		print(2 ** (i // 2) % (10 ** 9 + 7))
	else:
		print(0)


MOD = 10 ** 9 + 7
num = [0] * (10 ** 5 + 1)
N = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
	num[A[i]] += 1
if N % 2 == 1:
	for i in range(0, N, 2):
		cnt = num[i]
		if i == 0:
			if cnt != 1:
				print(0)
				return
		elif cnt != 2:
			print(0)
			return
	print(2 ** (N // 2) % MOD)
else:
	for i in range(1, N, 2):
		cnt = num[i]
		if cnt != 2:
			print(0)
			return
	print(2 ** (N // 2) % MOD)


N = int(input())
A = sorted(list(map(int, input().split())), reverse=True)
n = N - 1
for i in range(N // 2):
	if A[2 * i] != n or A[2 * i + 1] != n:
		print(0)
		exit()
	n -= 2
if N & 1 and A[-1] != 0:
	print(0)
	exit()
print((1 << N // 2) % (10 ** 9 + 7))


from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
L = A[:]
L = list(set(L))
mod = 10 ** 9 + 7
d = defaultdict(int)
for i in range(N):
	d[A[i]] += 1
if N % 2 == 1:
	bfr = 0
	for i in L:
		if i - bfr != 2 and i != 0:
			print(0)
			return
		if i == 0:
			if d[i] != 1:
				print(0)
				return
			else:
				continue
		if d[i] != 2:
			print(0)
			return
		bfr = i
	print(2 ** (N // 2) % mod)
else:
	bfr = 1
	for i in L:
		if i - bfr != 2 and i != 1:
			print(0)
			return
		if d[i] != 2:
			print(0)
			return
		bfr = i
	print(2 ** (N // 2) % mod)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	(N, *A) = list(map(int, read().split()))
	A.sort()
	ok = True
	if len(A) % 2 == 0:
		for i in range(N // 2):
			if not A[2 * i] == A[2 * i + 1] == 2 * i + 1:
				ok = False
				break
	elif A[0] != 0:
		ok = False
	else:
		for i in range(N // 2):
			if not A[2 * i + 1] == A[2 * i + 2] == 2 * i + 2:
				ok = False
				break
	if ok:
		ans = pow(2, N // 2, MOD)
	else:
		ans = 0
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(10 ** 5 + 1)]
for i in a:
	b[i] += 1
if n % 2 == 0 and b[0] != 0 or (n % 2 == 1 and b[0] != 1):
	print(0)
	return
ans = 1
mod = 10 ** 9 + 7
for i in b:
	if i == 2:
		ans *= 2
		ans %= mod
	if i >= 3:
		print(0)
		return
print(ans)


n = int(input())
alst = list(map(int, input().split()))
num = n - 1
ans_lst = [abs(i) for i in range(-num, num + 1, 2)]
alst.sort()
ans_lst.sort()
if alst != ans_lst:
	print(0)
else:
	MOD = 10 ** 9 + 7
	ans = pow(2, n // 2, MOD)
	print(ans)


n = int(input())
A = list(map(int, input().split()))
if n % 2 == 0:
	l = n ** 2
else:
	l = (n - 1) * (n + 1)
if sum(A) == l // 2:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
mod = 10 ** 9 + 7
ans = 1
for i in range(n):
	if a[i] != n - 1 - 2 * int(i * 0.5):
		print(0)
		exit()
	elif i % 2 == 1:
		ans = ans * 2 % mod
print(ans)


n = int(input())
a = sorted([int(i) for i in input().split()], reverse=True)
x = n + 1
for i in range(len(a)):
	if i % 2 == 0:
		x -= 2
	if a[i] != x:
		print(0)
		break
else:
	print(2 ** (n // 2) % (10 ** 9 + 7))


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
A = tuple(sorted(A))
if N % 2 == 1:
	nums = [0]
	for i in range(2, N + 1, 2):
		nums.append(i)
		nums.append(i)
else:
	nums = []
	for i in range(1, N + 1, 2):
		nums.append(i)
		nums.append(i)
nums = tuple(nums)
if A != nums:
	print(0)
	return
print(2 ** (N // 2) % mod)


n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = False
if n % 2 == 1:
	for i in range(n):
		if a[i] != (i + 1) // 2 * 2:
			print('0')
			flag = True
			break
else:
	for i in range(n):
		if a[i] != i // 2 * 2 + 1:
			print('0')
			flag = True
			break
if flag == False:
	print(2 ** (n // 2) % 1000000007)


n = int(input())
a = [int(x) for x in input().split()]
d = {}
for x in a:
	d[x] = d.get(x, 0) + 1
ok = True
for i in range(1 + n % 2, n, 2):
	if i not in d or d[i] != 2:
		ok = False
		break
if ok:
	print(pow(2, n // 2, 10 ** 9 + 7))
else:
	print(0)


n = int(input())
l = list(map(int, input().split()))
s = set(l)
if sum(l) == 2 * sum(s):
	flg = True
else:
	flg = False
print(2 ** (n // 2) % (10 ** 9 + 7) if flg else 0)


n = int(input())
A = list(map(int, input().split()))
A.sort()
if n % 2 == 0:
	X = [int(i) for i in range(1, n + 1, 2)] * 2
elif n % 2 == 1 and n > 2:
	X = [int(i) for i in range(2, n + 1, 2)] * 2 + [0]
else:
	X = [0]
X.sort()
ans = 2 ** (n // 2) % (10 ** 9 + 7)
for (a, x) in zip(A, X):
	if a != x:
		ans = 0
print(ans)


MOD = 10 ** 9 + 7

def fast_pow(x, n, MOD):
	res = 1
	while n:
		if n & 1:
			res = res * x % MOD
		x = x * x % MOD
		n >>= 1
	return res
n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
	if n % 2:
		if i > 0 and i % 2:
			print(0)
			return
	elif i > 0 and i % 2 == 0:
		print(0)
		return
	if not i in d:
		d[i] = 1
	elif d[i] == 1:
		d[i] += 1
	else:
		print(0)
		return
if n % 2:
	if d[0] != 1:
		print(0)
		return
	print(fast_pow(2, len(d) - 1, MOD))
else:
	if 0 in d:
		print(0)
		return
	print(fast_pow(2, len(d), MOD))


a = 10 ** 9 + 7
n = int(input())
s = list(map(int, input().split()))
s.sort()
t = n // 2
ans = 0
if n % 2 == 0:
	check = [2 * i + 1 for i in range(t)]
	check *= 2
	check.sort()
else:
	check = [2 * i for i in range(t + 1)]
	check *= 2
	check.sort()
	check.remove(0)
if check == s:
	ans = 2 ** t % a
print(ans)


num = int(input())
t = [int(n) for n in input().split()]
t = sorted(t)
valid = True
if num % 2 == 1:
	check = list(range(0, num + 1, 2))[1:]
	valid1 = t[0] == 0
	valid2 = check == t[2::2]
	valid3 = check == t[1::2]
	valid = valid1 and valid2 and valid3
	if not valid:
		print(0)
	else:
		ans = 2 ** ((num - 1) // 2) % (10 ** 9 + 7)
		print(ans)
else:
	check = list(range(1, num, 2))
	valid1 = True
	valid2 = check == t[::2]
	valid3 = check == t[1::2]
	valid = valid1 and valid2 and valid3
	if not valid:
		print(0)
	else:
		ans = 2 ** (num // 2) % (10 ** 9 + 7)
		print(ans)


import math
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
half = math.floor(N / 2)
ans = 2 ** half
if N % 2 == 1 and A[-1] != 0:
	ans = 0
for i in range(half):
	if A[2 * i] == N - 2 * i - 1 and A[2 * i + 1] == N - 2 * i - 1:
		continue
	else:
		ans = 0
		break
print(ans % (10 ** 9 + 7))


from collections import Counter

def mod_pow(a, n, mod):
	result = 1
	a_n = a
	while n > 0:
		if n & 1:
			result = result * a_n % mod
		a_n = a_n * a_n % mod
		n >>= 1
	return result
N = int(input())
A = Counter(tuple(map(int, input().split(' '))))
MOD = 10 ** 9 + 7
if A[0] > 1:
	print(0)
elif sum([key for (key, value) in list(A.items()) if value == 1]) != 0:
	print(0)
else:
	print(mod_pow(2, N // 2, MOD))


N = int(input())
A = [int(x) for x in input().split()]
H = True
A.sort()
if N % 2 == 0:
	for i in range(N):
		if A[i] != 2 * (i // 2) + 1:
			H = False
else:
	if A[0] != 0:
		H = False
	for i in range(1, N):
		if A[i] != 2 * ((i - 1) // 2) + 2:
			H = False
print(2 ** (N // 2) % (10 ** 9 + 7) if H else '0')


n = int(input())
a = list(map(int, input().split()))
d = {}
for i in a:
	if (i + n) % 2 == 0 and i != 0:
		print(0)
		exit()
	if i in d:
		d[i] += 1
		if d[i] == 3 or i == 0:
			print(0)
			exit()
	else:
		d[i] = 1
ans = 1
for i in list(d.values()):
	ans *= i
print(ans % 1000000007)


N = int(input())
s = sorted([i for i in range((N + 1) % 2, N, 2)] * 2)
if N % 2 == 1:
	s.pop(0)
print(2 ** (N // 2) % 1000000007 if sorted([int(i) for i in input().split()]) == s else 0)


from collections import Counter
n = int(input())
a = tuple(map(int, input().split(' ')))
a_counter = Counter(a)
a_counter[int(n % 2 == 0)] = 2
if set(a_counter.values()) == {2}:
	print(2 ** (n // 2) % (10 ** 9 + 7))
else:
	print(0)


n = int(input())
a_list = list(map(int, input().split()))
zero = a_list.count(0)
D = 1000000000 + 7
a_set = set(a_list)
if zero == 1 and n - 1 == 2 * (len(a_set) - 1):
	print(2 ** ((n - 1) // 2) % D)
elif zero == 0 and n == 2 * len(a_set):
	print(2 ** (n // 2) % D)
else:
	print(0)


n = int(input())
a = list(map(int, input().split()))
a.sort()
flag = True
if n % 2 == 1:
	for i in range(n):
		if a[i] != i + i % 2:
			flag = False
else:
	for i in range(n):
		if a[i] != i + 1 - i % 2:
			flag = False
if not flag:
	print(0)
else:
	s = 1
	for _ in range(n // 2):
		s = s * 2 % 1000000007
	print(s)


N = int(input())
A = sorted(list(map(int, input().split())))
cr_A = []
if N % 2:
	cr_A.append(0)
	for i in range(1, N // 2 + 1):
		cr_A.extend([2 * i] * 2)
else:
	for i in range(1, N // 2 + 1):
		cr_A.extend([2 * i - 1] * 2)
if A == cr_A:
	if N > 1:
		print(2 ** (N // 2) % (10 ** 9 + 7))
	else:
		print(1)
else:
	print(0)


NUM = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
length = len(A)
if not length % 2 == 0:
	length -= 1
for i in range(0, length, 2):
	if not A[i] == A[i + 1]:
		print(0)
		exit()
print(2 ** (length // 2) % NUM)


import sys
n = int(input())
a = list(map(int, input().split(' ')))
record = {}
possible = True
for e in a:
	if e in record.keys():
		record[e] += 1
		if record[e] == 2:
			if e == 0:
				possible = False
				break
		if record[e] == 3:
			possible = False
			break
	else:
		record[e] = 1
if possible == False:
	print(0)
	return
multiCount = int(n / 2)
print(2 ** multiCount % (10 ** 9 + 7))


n = int(input())
a = input().split()
int_a = []
for i in range(len(a)):
	int_a.append(int(a[i]))
if n % 2 == 0:
	kakeru = n
else:
	kakeru = n + 1
if sum(int_a) == kakeru * (n // 2):
	syou = n // 2
	answer = 2 ** syou
	print(answer % (10 ** 9 + 7))
else:
	print('0')


N = int(input())
As = list(map(int, input().split()))
nums = {}
exists = True
if N % 2 == 0:
	for A in As:
		if A in nums:
			nums[A] += 1
		else:
			nums[A] = 1
	for (key, value) in list(nums.items()):
		if key == 0:
			exists = False
		if value != 2:
			exists = False
else:
	for A in As:
		if A in nums:
			nums[A] += 1
		else:
			nums[A] = 1
	for (key, value) in list(nums.items()):
		if key == 0:
			if value != 1:
				exists = False
		elif value != 2:
			exists = False
if not exists:
	print(0)
else:
	ans = 1
	if N % 2 == 0:
		for i in range(int(N / 2)):
			ans = ans * 2
			ans %= 10 ** 9 + 7
	else:
		for i in range(int((N - 1) / 2)):
			ans = ans * 2
			ans %= 10 ** 9 + 7
	print(ans)


N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7
if N % 2 == 1:
	A.append(0)
A.sort()
od = tuple(A[::2])
ev = tuple(A[1::2])
if od == ev:
	comb = 2 ** (N // 2) % MOD
	print(comb)
else:
	print(0)


N = int(input())
A = sorted(list(map(int, input().split())))
mod = 10 ** 9 + 7
if N % 2 == 0 and len(set(A)) == N // 2:
	print(2 ** (N // 2) % mod)
elif N % 2 != 0 and A.count(0) == 1:
	print(2 ** ((N - 1) // 2) % mod)
else:
	print(0)


n = int(input())
l = list(map(int, input().split()))
d = dict()
mod = 10 ** 9 + 7
for i in l:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
d2 = dict()
for i in range(1 + n % 2, n, 2):
	d2[i] = 2
if n % 2:
	d2[0] = 1
if d == d2:
	print(2 ** (n // 2) % mod)
else:
	print(0)