Problem:
 Score : 300 points    Problem Statement 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 1 5
2 4 4 0 2      Sample Output 1 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        Sample Input 2 7
6 4 0 2 4 0 2      Sample Output 2 0  Any order would be inconsistent with the reports, thus the answer is 0 .       Sample Input 3 8
7 5 1 1 7 3 5 3      Sample Output 3 16

Solution (Python):
import sys



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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    from collections import Counter
    n = input_int()
    cnts = Counter(input_int_list())
    MOD = 10**9 + 7
    
    if n % 2 == 1:
        
        if cnts[0] != 1:
            print(0)
            return
        for i in range(2, n - 1, 2):
            if cnts[i] != 2:
                print(0)
                return
    else:
        
        for i in range(1, n, 2):
            if cnts[i] != 2:
                print(0)
                return
    print(pow(2, n // 2, MOD))
    return


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

N = int(input())
A = map(int, input().split())
MOD = 10**9+7
ac = Counter(A)

ans = 0
if N % 2 != 0:
    if ac[0] != 1:
        print(0)
        exit(0)
    for i in range(2, N, 2):
        if ac[i] != 2:
            print(0)
            exit(0)
    ans = 2**((N-1)//2)
else:
    for i in range(1, N, 2):
        if ac[i] != 2:
            print(0)
            exit(0)
    ans = 2**(N//2)
print(ans % MOD)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    
    n = I()
    a = LI()
    lst = [0 for _ in range(n)]
    mod = 10**9+7
    for x in a:
        lst[x] += 1

    if n%2 == 0:
        for x in lst[1::2]:
            if x!=2:
                print(0)
                exit(0)
        print(pow(2,n//2,mod))
    else:
        if lst[0]!=1:
            print(0)
        else:
            for x in lst[2::2]:
                if x != 2:
                    print(0)
                    exit(0)
            print(pow(2,(n-1)//2,mod))

    
main()

Solution (Python):
def power(x, n, mod):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = ans * x % mod
        n //= 2
        x = x * x % mod
    return ans

mod = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
a.sort()

ans = power(2, n//2, mod)
if n % 2:
    print(ans if all(a[i] == (i+1)//2*2 for i in range(n)) else 0)
else:
    print(ans if all(a[i] == i//2*2+1 for i in range(n)) else 0)

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A = Counter(A)

ideal = []
for i in range(1, N + 1):
    ideal.append(abs(N - 2 * i + 1))
ideal = Counter(ideal)

if dict(A) != dict(ideal):
    print(0)
else:
    print((2 ** (N // 2)) % (pow(10, 9) + 7))

Solution (Python):
import math

N = int(input())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

A.sort()

if N % 2 == 0:
    for i in range(N):
        if A[i] != 2 * (i // 2) + 1:
            print(0)
            exit()
else:
    for i in range(N):
        if A[i] != 2 * math.ceil(i / 2):
            print(0)
            exit()

print(2 ** (N // 2) % MOD)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
mod = 10**9+7


from collections import defaultdict
flag = True
if n % 2 == 0:
  dic = defaultdict(int)
  for a in A:
    dic[a] += 1
  for k, v in dic.items():
    if k % 2 == 0:
      flag = False
    if v != 2:
      flag = False
else:
  dic = defaultdict(int)
  for a in A:
    dic[a] += 1
  for k, v in dic.items():
    if k % 2 == 1:
      flag = False
    if k == 0:
      if v != 1:
        flag = False
    elif v != 2:
      flag = False

ans = (2 ** (n //2)) % mod
if flag:
  print(ans)
else:
  print(0)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

a.sort()


if n%2 == 1:
    b = [0]
    for i in range(1, (n-1)//2+1):
        b.append(i*2)
        b.append(i*2)
    if b == a:
        print((2**((n-1)//2))%mod)
    else:
        print(0)
else:
    b = []
    for i in range(n//2):
        b.append(1 + 2*i)
        b.append(1 + 2*i)
    if b == a:
        print((2**(n//2))%mod)
    else:
        print(0)

Solution (Python):

import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


def main():
    N = II()
    targets = LI()
    targets.sort()
    deque = cl.deque(targets)

    count = 1
    if N % 2 != 0:
        target = deque.popleft()
        if target != 0:
            print(0)
            return
        count = 2

    while len(deque) > 0:
        a = deque.popleft()
        b = deque.popleft()
        if a == b == count:
            count += 2
            continue
        else:
            print(0)
            return

    print(pow(2, (N//2), 10**9+7))


main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))

A = sorted(A)

if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            j = i + 1
        else:
            j = i
        if j == A[i]:
            continue
        else:
            print(0)
            exit()

else:
    for i in range(N):
        if i % 2 == 0:
            j = i
        else:
            j = i + 1
        if j == A[i]:
            continue
        else:
            print(0)
            exit()

print(2 ** (N // 2) % (10 ** 9 + 7))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))

c=[0 for i in range((n+1)//2)]
if n%2:
  c[0]+=1

for i in a:
  if i%2==n%2:
    break
  c[i//2]+=1

f=True
for i in c:
  if i!=2:
    f=False
    break
print(pow(2,n//2,10**9+7) if f else 0)

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,A=ilint()
C=counter()
for a in A:
    C.add(a)
ans=powmod(2,N//2,MOD)
for k in range((N-1)%2,N,2):
    if k not in C or C[k]!=2-(k==0):
        ans=0
        break
print(ans)

Solution (Python):
import sys
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 1
mod = 10**9+7

if n%2 == 0:
    for i in range(n//2):
        if 2*i+1 == a[2*i] == a[2*i+1]:
            ans *= 2
            ans %= mod
        else:
            print(0)
            sys.exit()
    print(ans)
else:
    if a[0] != 0:
        print(0)
        sys.exit()
    for i in range(1, n//2+1):
        if 2*i == a[2*i-1] == a[2*i]:
            ans *= 2
            ans %= mod
        else:
            print(0)
            sys.exit()
    print(ans)

Solution (Python):
n = int(input())

a_list = list(map(int, input().split()))
a_list.sort()
a_counter = {}
MOD = 10**9 + 7
for a in a_list:
    if a in a_counter.keys():
        a_counter[a] += 1
    else:
        a_counter[a] = 1

data_error = False

if n % 2 == 0:
    for i in range(1, n, 2):
        if i not in a_counter.keys():
            data_error = True
            break
        if a_counter[i] != 2:
            data_error = True
            break
else:
    for i in range(0, n, 2):
        if i not in a_counter.keys():
            data_error = True
        if a_counter[i] != 2:
            if i == 0 and a_counter[0] == 1:
                continue
            data_error = True
            break

if data_error:
    print(0)
else:
    ans = 2 ** (int(n / 2))
    ans %= MOD
    print(ans)

Solution (Python):
n = int(input())
a =  list(map(int, input().split()))

seen = {}

for ai in a:
    if ai in seen:
        seen[ai] += 1
    else:
        seen[ai] = 1

ans = True
cur = 0
if n%2 == 1:
    if not (0 in seen and seen[0] == 1):
        ans = False
    else:
        cur = 2
else:
    cur = 1

if ans:
    for i in range(cur, n, 2):
        if not (i in seen and seen[i] == 2):
            ans = False
            break

print((2**(n//2) % 1000000007) if ans else 0)

Solution (Python):
n=int(input())
a=sorted(map(int,input().split()))

l=[]
for x in range(n):
     l.append(abs(2*x-n+1))
l=sorted(l)
for x in range(n):
     if l[x]!=a[x]:print(0);exit()

print((2**(n//2))%(10**9+7))

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

Solution (Python):
N=int(input())
from collections import Counter
c=Counter(map(int,input().split()))
f=1
for i in range((N+1)%2,(N+1)//2,2):
    if i==0 and c[i]!=1 or 0<i and c[i]!=2:
        f=0
print(pow(2,N//2,10**9+7) if f else 0)

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    N = NI()
    A = NLI()
    cA = collections.Counter(A)
    
    sortedA = sorted(list(cA.items()))
    
    if N % 2 == 1:
        if sortedA[0] != (0,1):
            print(0)
            sys.exit()
        
        ans = 1
        for n in range(1,len(sortedA)):
            if sortedA[n] != (n*2 , 2):
                print(0)
                sys.exit()
            ans = ans * 2 % MOD
                
        print(ans)
        
        
    else:
        ans = 1
        for n in range(len(sortedA)):
            if sortedA[n] != tuple([n*2+1 , 2]):
                print(0)
                sys.exit()
            ans = ans * 2 % MOD
                
        print(ans)
    
 
 
if __name__ == '__main__':
    main()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)









INF = 1 << 50

def check(dic, N):
    if not N % 2:
        for i in range(1, N, 2):
            try:
                if dic[i] ==2:
                    continue
                else:
                    return False
            except:return False
        return True
    else:
        for i in range(0, N, 2):
            if i == 0:
                try:
                    if dic[i] == 1:continue
                    else:return False
                except:
                    return False
            else:
                try:
                    if dic[i]==2:continue
                    else:return False
                except:return False
        return True


def run():
    mod = 10 ** 9 + 7
    N, *A = map(int, read().split())
    dic = {}
    for a in A:
        if not a in dic.keys():
            dic[a] = 1
        else:
            dic[a] += 1

    
    if check(dic, N):
        ans = 1
        for key in dic.keys():
            ans *= dic[key]
            ans %= mod
        print(ans)
    else:
        print(0)




if __name__ == "__main__":
    run()

Solution (Python):
from collections import Counter

def solver(N, A):
    cnt = Counter(A)
    x = 1
    if N%2 == 1:
        if cnt[0] != 1:
            return 0
        x = 2
    for i in range(x, N, 2):
        if cnt[i] != 2:
            return 0
    
    return pow(2, N//2, 10**9+7)

N = int(input())
A = list(map(int, input().split()))

print(solver(N, A))

Solution (Python):
N=int(input())
*A,=map(int,input().split())
A.sort()
M=10**9+7
ans=0
B=[0]*N
if N%2:
    i=1
    while i<N:
        B[i]=B[i+1]=i+1
        i+=2
    if A==B:
        ans=pow(2,N//2,M)
else:
    i=0
    while i<N:
        B[i]=B[i+1]=i+1
        i+=2
    if A==B:
        ans=pow(2,N//2,M)
print(ans)

Solution (Python):
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007



def main():
	n = int(input())
	
	
	al = lin()
	cc = collections.Counter(al)
	if n % 2 == 1:
		if cc[0] != 1:
			return 0
		for c in range(2, n, 2):
			if cc[c] != 2:
				return 0
		else:
			return pow(2, n//2, mod)
	else:
		for c in range(1, n, 2):
			if cc[c] != 2:
				return 0
		else:
			return pow(2, n//2, mod)
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
from collections import defaultdict
N = int(input())
A = sorted(map(int, input().split()))
mod = 10 ** 9 + 7
if (N == 1 and A[0] != 0):
    print(0)
    exit()

d = defaultdict(int)
for i in range(N):
    if (N % 2 == 0):
        if (A[0] != 1):
            print(0)
            exit()
        else:
            if (d[A[i]] == 0):
                d[A[i]] = 1
            elif (d[A[i]] == 1):
                d[A[i]] += 1

    else:
        if (A[0] != 0):
            print(0)
            exit()
        else:
            if (d[A[i]] == 0):
                d[A[i]] = 1
            elif (d[A[i]] == 1):
                d[A[i]] += 1

for i, v in d.items():
    if not (N % 2 == 1 and i == 0):
        if v != 2:
            print(0)
            exit()

dic = sorted(d)
for i in range(len(dic)):
    if (i == len(dic) - 1):
        break
    if abs(dic[i] - dic[i + 1]) == 2:
        continue
    else:
        print(0)
        exit()

print((2 ** (N // 2)) % mod)

Solution (Python):






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





if N%2 == 0:
    mylist = sorted([i for i in range(1,N,2)]*2)
else:
    mylist = sorted([0] + [i for i in range(2,N,2)]*2)
if A != mylist:
    print(0)
else:
    print(2**(N//2) % (10**9+7))

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    A.sort()
    if N % 2 == 0:
        for i in range(0, N, 2):
            if A[i] == A[i + 1] == i + 1:
                continue
            else:
                print(0)
                sys.exit()
    else:
        for i in range(1, N, 2):
            if A[i] == A[i + 1] == i + 1:
                continue
            else:
                print(0)
                sys.exit()
        if A[0] != 0:
            print(0)
            sys.exit()
    print(pow(2, N // 2, MOD))


if __name__ == '__main__':
    main()

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

judge = sorted(list(set(a)))
c = Counter(a)
if not (judge[0] == 0 if n % 2 == 1 else 1):
    print(0)
    exit()

f = True
for v in judge:
    f &= (c[v] == 2 if v != 0 else 1)
if not f:
    print(0)
    exit()

f = True
for i in range(len(judge) - 1):
    f &= (judge[i + 1] - judge[i] == 2)
if not f:
    print(0)
    exit()

mod = 10**9+7
print(pow(2, n//2, mod))

Solution (Python):
from collections import Counter

n = int(input())
l = list(map(int, input().split()))
d = Counter(l)
if n%2 == 0 and 0 in l:
    print(0)
elif n%2 == 1 and d[0] != 1:
    print(0)
else:
    ans = 1
    for key, val in d.items():
        if key != 0 and val != 2:
            print(0)
            exit()
        if key == 0:
            continue
        ans*=2
        ans %= 1000000007
    print(ans)

Solution (Python):
n,*a=map(int,open(0).read().split());print(pow(2,n//2,10**9+7)*(sorted(a)[n&1::2]==[*range(1+n%2,n,2)])or 0)

Solution (Python):
n, *a = map(int, open(0).read().split())
print(pow(2, n // 2, 10**9 + 7)*(sorted(a)[n&1::2] == [*range(1 + n % 2, n, 2)]) or 0)

Solution (Python):

n, *a = map(int, open(0).read().split())
if sorted(a)[n&1:] == sorted([*range(1 + n % 2, n, 2)] * 2):
    print(pow(2, n // 2, 10**9 + 7))
else:
    print(0)

Solution (Python):
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

cnt = Counter(a)
if any(n % 2 == i % 2 for i in cnt):
    print(0); exit()
if any(cnt[i] != 2 for i in cnt if i != 0):
    print(0); exit()
print(pow(2, n // 2, mod))

Solution (Python):
N=int(input())
A=list(map(int,input().split()))
M=10**9+7

L=[0]*N
for a in A:
    L[a]+=1

if N%2:
    F=(L[0]==1)
    for i in range(1,N):
        if i%2:
            F&=(L[i]==0)
        else:
            F&=(L[i]==2)

    if F:
        print(pow(2,(N-1)//2,M))
    else:
        print(0)
else:
    F=True
    for i in range(N):
        if i%2:
            F&=(L[i]==2)
        else:
            F&=(L[i]==0)
    if F:
        print(pow(2,N//2,M))
    else:
        print(0)

Solution (Python):
def resolve():
    from collections import Counter
    mod = 10**9 + 7
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    if N % 2 == 0:
        pattern = sorted([i for i in range(1, N, 2)] * 2)
    else:
        pattern = [0] + sorted([i for i in range(2, N, 2)] * 2)
    if A != pattern:
        print(0)
    else:
        ans = 1
        for _ in range(N // 2):
            ans = ans * 2 % mod
        print(ans % mod)

resolve()

Solution (Python):
import sys
import math
import copy
import heapq
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)


input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        
        
        
        

def solve():
    n = getN()
    nums = getList()
    cnt = Counter(nums)
    parity = (n+1) % 2
    
    if Counter(cnt.values())[1] != n % 2:
        print(0)
        return
    for k, v in cnt.items():
        if v == 1 and k != 0:
            print(0)
            return
        if k >= n:
            print(0)
            return
        if k == 0 and v != 1:
            print(0)
            return

        if k % 2 != parity:
            print(0)
            return
        if v != 1 and v != 2:
            print(0)
            return

    print(pow(2, n//2, MOD))
    return

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()

flag = True
if N % 2 == 0:
  for i in range(N):
    if A[i] != 1 + 2*(i//2):
      flag = False
      break
  if flag:
    ans = 2 ** (N//2)
  else:
    ans = 0
else:
  for i in range(N):
    if A[i] != 2*((i+1)//2):
      flag = False
      break
  if flag:
    ans = 2 ** (N//2)
  else:
    ans = 0
ans = ans % (10**9+7)
print(ans)

Solution (Python):
import collections

N = int(input())
A = list(map(int,input().split()))

A_count = collections.Counter(A)

mod = 10**9+7
if N%2 == 1:
    for i in range(0,N,2):
        if (i == 0) and (A_count[i]==1):
            ans = 1
        elif (i!=0) and (A_count[i]==2):
            ans = (ans * 2) % mod
        else:
            ans = 0
            break
else:
    for i in range(1,N,2):
        if (i == 1) and (A_count[i]==2):
            ans = 2
        elif (i!=1) and (A_count[i]==2):
            ans = (ans * 2) % mod
        else:
            ans = 0
            break
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
As.sort()
mod = 10**9 + 7

if N%2==0:
    half = N//2
    for i in range(N):
        if i%2==0:
            x = i+1
        else:
            x = i
        if As[i]!=x:
            print(0)
            break
    else:
        print(pow(2, half, mod))
else:
    half = N//2
    if As[0]!=0:
        print(0)
        exit(0)
    for i in range(1, N):
        if i%2==1:
            x = i+1
        else:
            x = i
        if As[i]!=x:
            print(0)
            break
    else:
        print(pow(2, half, mod))

Solution (Python):

import collections
MOD = 10**9 + 7

N = int(input())
A = list(map(int, input().split()))

C = collections.Counter(A)
ret = 2**(N//2)
if N % 2 == 0:
    for i in range(1, N, 2):
        if C[i] != 2:
            ret = 0
            break
else:
    if C[0] != 1:
        ret = 0
    for i in range(2, N, 2):
        if C[i] != 2:
            ret = 0
            break

print(ret % MOD)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

a.sort()
b = [ abs((n-1-i) - i)  for i in range(n)]
b.sort()

for ai,bi in zip(a,b):
    if(ai!=bi):
        print(0)
        exit()

ans = pow(2, n//2 ,mod)
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

if n%2==0:
    c=Counter(a)
    for x in c:
        if x%2==0 or c[x]!=2:
            print(0)
            break
    else:
        print(pow(2,n//2,mod))
else:
    c=Counter(a)
    if 0 not in c or c[0]!=1:
        print(0)
        exit()
    for x in c:
        if x==0:
          continue
        if x%2==1 or c[x]!=2:
            print(0)
            break
    else:
        print(pow(2,(n-1)//2,mod))

Solution (Python):
n=int(input())
ar=sorted(list(map(int,input().split())))
re=[]
if(n%2==1):
    re.append(0)
    for e in range(2,n,2):
        re.append(e)
        re.append(e)
else:
    for e in range(1,n,2):
        re.append(e)
        re.append(e)

if(ar!=re):
    print(0)
else:
    print(pow(2,n//2,10**9+7))

Solution (Python):
def main():
    import sys

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

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




if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] 


import string

from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = defaultdict(int)
    for e in a:
        cnt[e] += 1
    
    xd = 0
    for c in cnt:
        if cnt[c] == 2:
            xd += 1
    target = n // 2
    if n % 2 == 0:
        if xd == target and cnt[0] == 0:
            print(pow(2, xd, MOD))
            return
    else:
        if xd == target and cnt[0] == 1:
            print(pow(2, xd, MOD))
            return
        
    print(0)



    
t = 1

for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
num=n-1
num2=0
num3=1
ans=pow(2,n//2,10**9+7)
for i in range(n//2):
    for j in range(2):
        if a[num2]!=num:
            num3=0
            break
        num2+=1
    num-=2
    if num3==0:
        break
if n%2==1:
    if a[-1]!=num:
        ans=0
if num3==0:
    ans=0
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))

b=[0 for _ in range((n+1)//2)]
for i in range(n):
    b[a[i]//2]+=1
if n%2==0:
  for i in range(n//2):
    if b[i]!=2:
      print(0)
      break
  else:
    print(pow(2,n//2,10**9+7))
else:
  if b[0]!=1:
    print(0)
  else:
    for i in range(1,n//2+1):
      if b[i]!=2:
        print(0)
        break
    else:
      print(pow(2,n//2,10**9+7))

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    N = NI()
    A = sorted(NLI())
    if N % 2:
        for i in range(N):
            if i % 2 == 0 and A[i] == i:
                continue
            elif i % 2 == 1 and A[i] == i + 1:
                continue
            else:
                print(0)
                exit()
        print(pow(2, (N//2), MOD))

    else:
        for i in range(N):
            if i % 2 == 0 and A[i] == i + 1:
                continue
            elif i % 2 == 1 and A[i] == i:
                continue
            else:
                print(0)
                exit()
        print(pow(2, (N//2), MOD))


if __name__ == "__main__":
    main()

Solution (Python):
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

C = Counter(A)
D = {}
MOD = 10**9+7
for i in range(N-1, -1, -2):
    if i == 0:
        D[i] = 1
    else:
        D[i] = 2

if C != D:
    print(0)
else:
    ans = pow(2, N//2, MOD)
    print(ans)

Solution (Python):
def main():
    mod = 1000000007
    N = int(input())
    A = list(map(int, input().split()))

    exist = True
    res = 0
    if N % 2 == 0:
        check = [2] * (N // 2)
        for a in A:
            if a % 2 == 1:
                if check[(a-1)//2] > 0:
                    check[(a-1)//2] -= 1
                else:
                    exist = False
            else:
                exist = False
        if exist:
            res = 1
            for i in range(N//2):
                res *= 2
                res %= mod
    else:
        check = [2] * ((N+1) // 2)
        check[0] = 1
        for a in A:
            if a % 2 == 0:
                if check[a//2] > 0:
                    check[a//2] -= 1
                else:
                    exist = False
            else:
                exist = False
        if exist:
            res = 1
            for i in range((N-1)//2):
                res *= 2
                res %= mod

    print(res)

if __name__ == "__main__":
    main()