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):
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
ans=0
if N%2!=0:
    c=list(Counter(A).items())
    c.sort(reverse=True)
    for a,b in c:
        if a!=0 and b==2:
            ans+=1
        elif a==0 and b==1:
            print(2**ans%(10**9+7))
        else:
            print(0)
            break
else:
    if A.count(0)>0:
        print(0)
    else:
        c=list(Counter(A).items())
        c.sort(reverse=True)
        for a,b in c:
            if a!=1 and b==2:
                ans+=1
            elif a==1 and b==2:
                ans+=1
                print(2**ans%(10**9+7))
            else:
                print(0)
                break

Solution (Python):

from collections import Counter
import sys
input = sys.stdin.readline

def main():
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    if N % 2:
        if C[0] != 1:
            return 0
        for key in C:
            if key == 0:
                continue
            if key % 2 or C[key] != 2:
                return 0
        ret = 1
        for i in range(N // 2):
            ret = ret * 2 % MOD
    else:
        for key in C:
            if key % 2 == 0 or C[key] != 2:
                return 0
    ret = 1
    for i in range(N // 2):
        ret = ret * 2 % MOD
    return ret

if __name__ == '__main__':
    print(main())

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

count = dict()
if N % 2:
	for a in A:
		if a % 2:
			print(0)
			exit()
		if a in count:
			count[a] += 1
		else:
			count[a] = 1
	if count[0] != 1:
		print(0)
		exit()
	del count[0]
	for c in count.values():
		if c != 2:
			print(0)
			exit()
else:
	for a in A:
		if not(a % 2):
			print(0)
			exit()
		if a in count:
			count[a] += 1
		else:
			count[a] = 1
	for c in count.values():
		if c != 2:
			print(0)
			exit()

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

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
from collections import Counter
MOD = 10**9+7
def is_ok(n, a_list):
    if N%2==0:
        
        c = Counter(a_list)
        for a in a_list:
            if a%2==0:
                return False
            elif c[a] != 2:
                return False
    else:
        
        c = Counter(a_list)
        for a in a_list:
            if a%2==1:
                return False
            elif a == 0:
                if c[a]!=1:
                    return False
            elif c[a] != 2:
                return False
    
    return True


if (is_ok(N, A)):
    print((2**(N//2))%MOD if N%2==0 else (2**((N-1)//2))%MOD)
else:
    print(0)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
if n %2 == 0:
    s = [2]*(n//2)
else:
    s = [2]*(n//2+1)
    s[0] = 1
if n%2 == 0:
    for a in A:
        if s[(a-1)//2] >0:
            s[(a-1)//2] -= 1
        else:
            continue
    if sum(s)==0:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)
else:
    for a in A:
        if s[a//2] >0:
            s[a//2] -= 1
        else:
            continue
    if sum(s) == 0:
        print(2**((n-1)//2)%(10**9+7))
    else:
        print(0)

Solution (Python):
import math


def mod_pow(a: int, n: int, mod: int)->int:
    ret = 1
    for _ in range(n):
        ret = (ret * a) % mod
    return ret


def lining_up(N: int, A: list)->int:
    pos = [0] * math.ceil(N / 2)

    for a in A:
        i = (N-a-1)//2
        pos[i] += 1

        if pos[i] > 2:
            return 0

    if N % 2 == 0 and any(p != 2 for p in pos):
        return 0
    if N % 2 == 1 and any(p != 2 for p in pos[:-1]) and pos[-1] != 1:
        return 0

    return mod_pow(2, N // 2, 10**9+7)


if __name__ == "__main__":
    N = int(input())
    A = [int(s) for s in input().split()]
    ans = lining_up(N, A)
    print(ans)

Solution (Python):
from functools import reduce
import bisect

def main():
    
    
    
    
    
    
    

    
    

    
    p=10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    

    N = int(input().rstrip())
    A = list(map(int, input().split()))
    
    
    A.sort()
    flag = False
    if A[0] == 0 and N%2 == 1:
        flag = True
        for i in range(N):
            if A[i] != (i + 1) // 2 * 2:
                flag = False
                break
    if A[0] == 1 and N%2 == 0:
        flag = True
        for i in range(N):
            if A[i] != i // 2 * 2 + 1:
                flag = False
                break
    if flag:
        print(2**(N//2) % p)
    else:
        print(0)
        
if __name__ == '__main__':
    main()

Solution (Python):
from functools import reduce
import bisect

def main():
    
    
    
    
    
    
    

    
    

    
    p=10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    

    N = int(input().rstrip())
    
    A = list(int(_) for _ in input().split())
    
    A.sort()
    flag = False
    if A[0] == 0 and N%2 == 1:
        flag = True
        for i in range(N):
            if A[i] != (i + 1) // 2 * 2:
                flag = False
                break
    if A[0] == 1 and N%2 == 0:
        flag = True
        for i in range(N):
            if A[i] != i // 2 * 2 + 1:
                flag = False
                break
    if flag:
        print(2**(N//2) % p)
    else:
        print(0)
        
if __name__ == '__main__':
    main()

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

A.sort()
ok = False
if A[0] == 0 and N % 2 == 1:
    ok = True
    for i in range(N):
        if A[i] != (i + 1) // 2 * 2:
            ok = False
            break
elif A[0] == 1 and N % 2 == 0:
    ok = True
    for i in range(N):
        if A[i] != i // 2 * 2 + 1:
            ok = False

if ok:
    print(2 ** (N // 2) % MOD)
else:
    print(0)

Solution (Python):


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

a.sort()

can = True

if a[0] == 0:
    for i in range(1,n):
        if i % 2 != 1:
            if a[i] != i:
                can = False
                break
        else:
            if a[i] != i + 1:
                can = False
                break
    if can:
        print((2 ** int((n-1)/2))% (10 ** 9 + 7))
    else:
        print(0)
elif a[0] == 1:
    for i in range(0,n):
        if i % 2 != 1:
            if a[i] != i + 1:
                can = False
                break
        else:
            if a[i] != i:
                can = False
                break
    if can:
        print((2 ** int(n/2))% (10 ** 9 + 7))
    else:
        print(0)
else:
    print(0)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
stack=[0]*(10**5+1)
p=10**9+7
for i in a:
  stack[i]+=1
if n%2==0:
  for j in range(1,n+1,2):
    if stack[j]!=2:
      print(0)
      exit()
  print(pow(2,n//2,p))
  exit()
for j in range(0,n+1,2):
  if j==0 and stack[j]==1:
    continue
  if j!=0 and stack[j]!=2:
    print(0)
    exit()
print(pow(2,n//2,p))
exit()

Solution (Python):
import sys
N = int(input())
alist = list(map(int,input().split()))
flg = True
if N == 1:
    if alist[0] == 0:
        print(1)
    else:
        print(0)
    sys.exit()
inf = 10 ** 9 + 7
alist.sort()
if N % 2 == 0:
    for i in range(N)[1::2]:
        if alist[i-1] != i or alist[i] != i:
            flg = False
            break
else:
    if alist[0] != 0:
        flg = False
    for i in range(N)[2::2]:
        if alist[i-1] != i or alist[i] != i:
            flg = False
            break
if flg:
    print((2 ** (N // 2)) %  inf)
else:
    print(0)

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

Solution (Python):
from collections import Counter
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c = c.most_common()
c.sort()

if n % 2 == 1:
    num = 0
    for i, v in c:
        k = 2
        if i == 0:
            k = 1
        
        if (i, v) != (num, k):
            print(0)
            exit()
        num += 2
else:
    num = 1
    for i, v in c:
        if (i, v) != (num, 2):
            print(0)
            exit()
        num += 2
print(2 ** (n//2) % mod)

Solution (Python):
from collections import Counter
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c = c.most_common()
c.sort()
if n % 2 == 1:
    if c[0] != (0, 1):
        print(0)
        exit()
        
    num = 2
    for i, v in c[1:]:
        if (i, v) != (num, 2):
            print(0)
            exit()
        num += 2
else:
    num = 1
    for i, v in c:
        if (i, v) != (num, 2):
            print(0)
            exit()
        num += 2
print(2 ** (n//2) % mod)

Solution (Python):
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)

Solution (Python):


















import math
import copy
from collections import defaultdict, Counter

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def s_inpl(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
INF = float("inf")

N = int(input())
A = inpl()

ans_l = []
if N % 2 == 0:
    for i in range(1, N):
        if i % 2 == 1:
            ans_l.append(i)
            ans_l.append(i)
else:
    for i in range(1, N):
        if i % 2 == 0:
            ans_l.append(i)
            ans_l.append(i)
    ans_l.append(0)

A.sort()
ans_l.sort()

if A == ans_l:
    print((2**(N//2))%(1000000007))
else:
    print(0)

Solution (Python):
n = int(input())
A = list(map(int, input().split()))
mod=int(1e9+7)

memo={i:0 for i in range(n)}
for a in A:
  memo[a]=memo.get(a,0)+1

answer=1
if n%2:
  if memo[0]!=1:
    print(0)
    exit()
  for i in range(1, (n+1)//2):
    if memo[2*i]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
elif not n%2:
  for i in range(n//2):
    if memo[2*i+1]!=2:
      print(0)
      exit()
    else:
      answer = 2*answer %mod
      
print(answer)

Solution (Python):
N = int(input())
a = sorted(list(map(int, input().split())))
MOD = 10 ** 9 + 7
if N % 2 == 0:
    for i in range(1, N, 2):
        if a[i - 1] == a[i] == i:
            continue
        break
    else:
        print(2 ** (N // 2) % MOD)
        exit()
else:
    if a[0] == 0:
        for i in range(2, N, 2):
            if a[i - 1] == a[i] == i:
                continue
            break
        else:
            print(2 ** (N // 2) % MOD)
            exit()
print(0)

Solution (Python):
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)

Solution (Python):
import sys
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
mod = 10**9 + 7
ans = 1
if N == 1:
    if A[0] == 0:
        print(ans)
        sys.exit()
    else:
        print(0)
        sys.exit()
if N%2 == 0:
    for i in range(N//2):
        if A[2*i] != 2*i+1 or A[2*i+1] != 2*i+1:
            print(0)
            sys.exit()
        else:
            ans = 2*ans%mod
    print(ans)
else:
    if A.pop(0) != 0:
        print(0)
        sys.exit()
    else:
        for i in range((N-1)//2):
            if A[2*i] != 2*i+2 or A[2*i+1] != 2*i+2:
                print(0)
                sys.exit()
            else:
                ans = 2*ans%mod
    print(ans)

Solution (Python):
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)

Solution (Python):
n = int(input())
a = sorted([int(i) for i in input().split()])

def f():
    global a
    cnt = 1 + (n%2)
    if n%2 == 1:
        if a[0] != 0:
            return 0
        a = a[1:]

    
    for i in range(len(a)):
        if a[i] != cnt:
            return 0

        if i%2 == 1:
            cnt+=2

    return 2**(n//2)

print(f()%(10**9+7))

Solution (Python):
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)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
ok = [0]*(n)
flag = 0
if n == 1 and A == [0]:
	print(1)
	exit()
for a in A:
	ok[a] += 1
if n%2 == 1:
	if ok[0] == 1 and set(ok[1::2]) == {0} and set(ok[2::2]) == {2}:
		flag = 1
else:
	if set(ok[::2]) == {0} and set(ok[1::2]) == {2}:
		flag = 1
if flag:
	print((2**(n//2))%(10**9+7))
else:
	print(0)

Solution (Python):








N = int(input())
MOD = 7 + 10**9
L = list(map(int,input().split()))
if N % 2 == 0:
    correct = []
    for i in range(N // 2):
        correct.append(i*2 + 1)
        correct.append(i*2 + 1)

    if sorted(L) == sorted(correct):
        print(2 ** (N // 2)% MOD)
    else:
        print(0)
else:
    correct = [0]
    for i in range(N // 2):
        correct.append((i+1)*2)
        correct.append((i+1)*2)
    if sorted(L) == sorted(correct):
        print(2 ** (N // 2) % MOD)
    else:
        print(0)

Solution (Python):
MOD = 10**9 + 7


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = [0] * (N//2+1)
    for a in A:
        cnt[(a+1)//2] += 1
    if (N % 2 == 0 and cnt[0] != 0) or (N % 2 == 1 and cnt[0] != 1):
        print(0)
        return
    ans = 1
    for i in range(1, N//2+1):
        if cnt[i] != 2:
            print(0)
            return
        ans = (ans * 2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

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

Solution (Python):
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)

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

else:
    for i in range(n):
        if i%2 == 0:
            if a[i] != i+1:
                print(0)
                exit()
        else:
            if a[i] != i:
                print(0)
                exit()

for k in range(n//2):
    ans *= 2
    ans%= MOD

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
ans = pow(2, N // 2)

check = [0 for p in range(0, N // 2 + N % 2)]
for o in A:
    check[o // 2] += 1

for q in range(0, N // 2 + N % 2):
    if q == 0 and N % 2 == 1:
        if check[q] != 1:
            ans = 0
            break
    else:
        if check[q] != 2:
            ans = 0
            break
print(ans % (pow(10, 9) + 7))

Solution (Python):
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)

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

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

b = [0 for i in range(10**5*1)]

for i in range(n):
    b[a[i]] += 1
if n % 2 == 0:
    if all(list(map(lambda x:x==2,b[1:n+1:2]))):
        print(2**(n//2)%(10**9+7))
    else:
        print(0)

else:
    if all(list(map(lambda x:x == 2,b[2:n+1:2]))) and b[0] == 1:
        print(2**(n//2)%(10**9+7))
    else:
        print(0)

Solution (Python):

N=int(input())
A=list(map(int,input().split()))
if N%2==1:
    if A.count(0)!=1:
        print(0)
        exit()
B=[0 for i in range(N//2)]
for a in A:
    if a == 0:
        continue
    elif a%2==(N+1)%2:
        B[a//2-N%2]+=1
    else:
        print(0)
        exit()
if B.count(2)==len(B):
    print(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

c = Counter(a)

if n % 2 == 0:
    temp = 1
    for _ in range(n // 2):
        if c[temp] != 2:
            print(0)
            exit()
        temp += 2
    print(2 ** (n // 2) % MOD)
else:
    if c[0] != 1:
        print(0)
        exit()
    temp = 2
    for _ in range(n // 2):
        if c[temp] != 2:
            print(0)
            exit()
        temp += 2
    print(2 ** (n // 2) % MOD)

Solution (Python):
a=1000000007
n=int(input())
l=list(map(int,input().split()))
l.sort()
if n%2==1:
  if l[0]!=0:
    print(0)
    exit()
  else:
    l.remove(0)
    sh=2
    f=0
    for i in l:
      if f==0:
        if i!=sh:
          print(0)
          exit()
        else:
          f=1
      else:
        if i!=sh:
          print(0)
          exit()
        else:
          sh+=2
          f=0
  sh=(n-1)//2
  b=1
  for i in range(sh):
    b*=2
    b%=a
  print(b)
else:
  sh=1
  f=0
  for i in l:
    if f==0:
      if i!=sh:
        print(0)
        exit()
      else:
        f=1
    else:
      if i!=sh:
        print(0)
        exit()
      else:
        sh+=2
        f=0
  sh=n//2
  b=1
  for i in range(sh):
    b*=2
    b%=a
  print(b)

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

A.sort()
if len(A) % 2 == 1:
  odd = True
else:
  odd = False

value = 1

if odd:
  for i in range(len(A)//2):
    if A[2*i+1] == A[2*i+2] and A[2*i+1] == 2*i+2:
      value *= 2
    else:
      value *= 0
      break
  if A[0] != 0:
    value *= 0
else:
  for i in range(len(A)//2):
    if A[2*i] == A[2*i+1] and A[2*i] == 2*i+1:
      value *= 2
    else:
      value *= 0

print(value % (10**9+7))

Solution (Python):
mod = 10**9+7
N = int(input())
A = list(map(int,input().split()))
if N % 2 == 1:
    ls = list(range(0,N,2))
    ls = sorted(ls+ls)
    ls.pop(0)
    if sorted(A) != ls:
        print(0)
    else:
        print(2**((N-1)//2) % mod)
else:
    ls = list(range(1,N,2))
    ls = sorted(ls+ls)
    if ls != sorted(A):
        print(0)
    else:
        print(2**(N//2) % mod)

Solution (Python):
from collections import Counter
mod = 10 ** 9 + 7
n = int(input())
A = Counter([int(i) for i in input().split()])

flag = 0
cnt = 0
if n % 2 == 1:
    for k, v in A.items():
        if  k != 0 and v == 2:
            cnt += 1
        elif k == 0 and v == 1:
            pass
        else:
            flag = 1
else:
    for k, v in A.items():
        if v == 2:
            cnt += 1
        else:
            flag = 1
            
if flag == 1:
    print(0)
else:
    print(2 ** cnt % mod)

Solution (Python):
from collections import Counter
mod = 10 ** 9 + 7
n = int(input())
A = Counter([int(i) for i in input().split()])

ans = 0
if n % 2 == 1:
    for k, v in A.items():
        if k == 0 and v != 1:
            ans = 0
            break
        elif v >= 3:
            ans = 0
            break
        elif v == 2:
            ans += 1
else:
    for k, v in A.items():
        if v != 2:
            ans = 0
            break
        else:
            ans += 1
            
if n == 1:
    if A[0] == 1:
        print(1)
    else:
        print(0)
elif ans == 0:
    print(0)
else:
    print(2 ** ans % mod)

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007






n = I()
a = LI()
d = defaultdict(int)
for i in a:
    d[i] += 1
for i in d.items():
    if i[0] != 0 and i[1] == 1:
        print(0)
        quit()
    elif i[1] > 2:
        print(0)
        quit()
print(pow(2,n//2,mod))

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    b=sorted(a)
    i=0
    while i<len(b):
        if not (b[i]==b[i+1] or b[i+2]==b[i]+2):
            print(0)
            exit()
        i+=2
    print((2**(len(b)//2))%(10**9+7))
else:
    b=sorted(a)
    if len(b)>1:
        if b[1]==0:
            print(0)
            exit()
    if b[0]!=0:
        print(0)
        exit()
    else:
        i=1
        while i<len(b):
            if not (b[i]==b[i+1] or b[i+2]==b[i]+2):
                print(0)
                exit()
            i+=2
        print(2**(len(b)//2)%(10**9+7))

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

else:
  flag = True
  if not(a[0]==a[1] and a[0]==1):
    flag = False
  for i in range(2,n,2):
    if not(a[i]==a[i+1] and a[i-1]!=a[i]):
      flag =False
  print((2**(n//2))%mod if flag else 0)

Solution (Python):
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)

Solution (Python):
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)

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

dic = {}
for i in range(N):
    if L[i] in dic:
        dic[L[i]] += 1
    else:
        dic[L[i]] = 1
        
res = 1
for d in dic:
    if d != 0:
        if dic[d] != 2:
            res = 0
            break
        else:
            res = (res*2)%(10**9+7)
    else:
        if N%2 == 0 and dic[d] != 0:
            res = 0
            break
        elif N%2 == 1 and dic[d] != 1:
            res = 0
            break

if res != 0:
    i = 0
    for _ in range(N+1):
        if N - 2*i - 1 < 1:
            break
        if (N - 2*i - 1 in dic) == False:
            res = 0
            break
        i += 1
        
print(res)

Solution (Python):
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7
countA= Counter(A)
if n%2==1:
  for k,v in countA.items():
    if k==0:
      if v!=1:
        print(0)
        exit()
    else:
      if v!=2:
        print(0)
        exit()
  print(2**((n-1)//2)%mod)
else:
  for k,v in countA.items():
    if v!=2:
      print(0)
      exit()
  print(2**(n//2)%mod)

Solution (Python):
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)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
res=1
for i in range(n//2):
    res=(res*2)%(10**9+7)
from collections import defaultdict
data=defaultdict(int)
for i in a:
    data[i]+=1
ans=0
if n%2==0:
    for i in range(n//2):
        if data[2*i+1]!=2:
            ans=1
            break
elif n%2==1:
    for i in range(n//2):
        if data[2*i+2]!=2:
            ans=1
            break
if ans==1:print(0)
elif ans==0:print(res)

Solution (Python):
MOD = 10**9 + 7

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

counter = {}
for a in A:
    if a in counter:
        counter[a] += 1
    else:
        counter[a] = 1

possible = True
for num, cnt in counter.items():
    if num == 0:
        possible &= cnt == 1
    else:
        possible &= cnt == 2

if possible:
    ans = 1
    for i in range(N // 2):
        ans = (ans*2) % MOD
    print(ans)
else:
    print(0)

Solution (Python):
N = int(input())
L = list(map(int,input().split()))
L = sorted(L,reverse=True)

flg = 0
for i in range(N) :
    if i % 2 == 0 :
        if L[i] == N-i-1 :
            continue
        flg = 1
        break
    else :
        if L[i] == N-i :
            continue
        flg = 1
        break
if flg == 1 :
    ans = 0
else :
    ans = 2**(len(L)//2) % (10**9+7)
print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from collections import Counter
n = int(input())
A = sorted(Counter([int(i) for i in input().split()]).most_common())

flag = 0
for i in range(len(A) - 1):
    if A[i + 1][0] - A[i][0] != 2:
        flag = 1

cnt = 0
for a in A:
    if a[0] == 0 and a[1] == 1:
        pass
    elif a[0] != 0 and a[1] == 2:
        cnt += 1
    else:
        flag = 1
        break
        
if flag == 1:
    print(0)
else:
    print(2 ** cnt % (10 ** 9 + 7))

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

if n % 2:
    for k in range(n):
        if a[k] != (k+1)//2*2:
            print(0)
            break
    else:
         print(2**((n-1)//2) % (10**9+7))
else:
    for k in range(n):
        if a[k] != k//2*2+1:
            print(0)
            break
    else:
        print(2**(n//2) % (10**9+7))

Solution (Python):
from collections import Counter

MOD = 10 ** 9 + 7

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

ans = 2 ** (N // 2) % MOD
flg = True
b = Counter(a)
if N % 2 == 1:
    for i in range(0, N, 2):
        if i == 0:
            if b[i] != 1:
                flg = False
                break
        else:
            if b[i] != 2:
                flg = False
                break

else:
    for i in range(1, N, 2):
        if b[i] != 2:
            flg = False
            break

print(ans if flg else 0)

Solution (Python):
from itertools import chain


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

A.sort()

if N % 2 == 1:
    B = [[n] if n == 0 else [2*n, 2*n] for n in range(N//2+1)]
    B = list(chain.from_iterable(B))
    if A != B:
        print(0)
    else:
        print(2 ** (N//2) % (10**9+7))
else:
    B = [[2*n-1, 2*n-1] for n in range(1, N//2+1)]
    B = list(chain.from_iterable(B))
    if A != B:
        print(0)
    else:
        print(2**(N//2) % (10**9+7))

Solution (Python):
import collections


def solve():
    N = int(input())
    A = [int(x) for x in input().split()]

    
    count = collections.Counter(A)

    if N%2 != 0 and (0 not in count or count[0] != 1):
        return 0

    i = 1 + (N%2)
    while i < N:
        if i not in count or count[i] != 2:
            return 0
        i += 2
    
    MOD = 10**9+7
    ans = 1
    M = N//2
    for i in range(M):
        ans = ans * 2 % MOD
    return ans


print(solve())

Solution (Python):
import collections
n = int(input())
a = sorted(list(int(i) for i in input().split()))
ct = collections.Counter(a)
odd = []
even = []
mod =10**9+7



if n % 2 == 0:
  for i in range(n//2):
    even.append(i*2+1)
    even.append(i*2+1)
  if a == even:
    print(2**(n//2)%mod)
  else:
    print(0)
else:
  odd.append(0)
  for i in range(n//2):
    odd.append(2+i*2)
    odd.append(2+i*2)
  if a == odd:
    print(2**(n//2)%mod)
  else:
    print(0)

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




dic = {}

for a in A:
    if a in dic.keys():
        dic[a] += 1
    else: dic[a] = 1

flag = True
ini = N
if N % 2 == 1:
    if 0 in A:
        if dic[0] == 1:
            ini = 2
        else:
            flag = False
    else:
        flag = False
else:
    ini = 1

for i in range(ini,N,2):
    if not flag: break
    if i in dic:
        if dic[i] != 2:
            flag = False
    else: flag = False

if flag:
    print(2**(N//2)%(10**9+7))
else:
    print(0)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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%2==n%2 and i+1!=a[i] or i%2==(n+1)%2 and i!=a[i]:A=0
print(A)

Solution (Python):
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%2==n%2 and i+1!=a[i] or i%2==(n+1)%2 and i!=a[i]:
    A=0
    break
print(A)

Solution (Python):
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))