CodeEff/ECCO huggingface dataset:
# Original solution
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def f(v, vs):
    kminmax = 0
    r = 0
    rkoma = 0
    fff = 0
    ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax = k1
            ffmx = ff
        kminmax = max(kminmax, k1)
        rkoma += koma
        fff += ff
    if kminmax > fff - ffmx:
        r1 = kminmax+ffmx-fff
    else:
        r1 = fff % 2
    rkoma += km[v]
#    print(v, r1 + rkoma, rkoma, fff + rkoma)
    return r1 + rkoma, rkoma, fff + rkoma

N = int(eval(input()))
km = [0] + [int(i) for i in str(input().strip())]
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    x, y = list(map(int, input().split()))
    d[x].add(y)
    d[y].add(x)

r = 10**10
#print(f(4, {4}))
for i in range(N):
    a, c, fff = f(i+1, {i+1})
#    print(i, a, c)
    if a == c:
        r = min(r, (fff-c)//2)
print((r if r != 10**10 else -1))


# Optimized solution
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def f(v, vs):
    kminmax = rkoma = fff = ffmx = 0
    for u in d[v]:
        if u in vs:
            continue
        vs.add(u)
        k1, koma, ff = f(u, vs)
        if k1 > kminmax:
            kminmax, ffmx = k1, ff
        rkoma += koma
        fff += ff
    r1 = kminmax+ffmx-fff if kminmax > fff - ffmx else fff % 2
    rkoma += km[v]
    return r1+rkoma, rkoma, fff+rkoma

N = int(eval(input()))
km = [0] + [int(i) for i in str(input().strip())]
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    x, y = list(map(int, input().split()))
    d[x].add(y)
    d[y].add(x)
r = 10**10
for i in range(N):
    a, c, fff = f(i+1, {i+1})
    if a == c:
        r = min((fff-c)//2, r)
print((r if r != 10**10 else -1))
# Original solution
N=int(eval(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!=S:
        print((0))
        exit()


ans=1
nagasa=lenS//2
for i in range(nagasa):
    
    ans=(ans*2)%(10**9+7)

print(ans)


    

# Optimized solution
N=int(eval(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))
        exit()


ans=1
nagasa=lenS//2
for i in range(nagasa):
    
    ans=(ans*2)%(10**9+7)

print(ans)
# Original solution
n=int(eval(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)))

# Optimized solution
n=int(eval(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)
# Original solution
N = int(eval(input()))
line = list(map(int, input().split()))
n = N - 1
ans = 1
while(len(line) >= 0):
    c = line.count(n)
    if (len(line) == 0):
        print((ans % (10**9+7)))
        break
    if len(line) == 1 and line[0] == 0:
        print((ans % (10**9+7)))
        break
    elif c != 2:
        print((0))
        break
    else:
        ans *= 2
        line = [i for i in line if i != n]
        n = n - 2


# Optimized solution
N = int(eval(input()))
line = list(map(int, input().split()))
n = N - 1
ans = 1
line.sort()
s = len(line)
index = s - 1
while(index > 1):
    if line[index] == n and line[index-1] == n:
        ans *= 2
        n = n - 2
        index = index - 2
    else:
        print((0))
        break

if index == 1:
    if line[index] == n and line[index-1] == n:
        ans *= 2
        print((ans % (10**9+7)))
    else:
        print((0))

elif index == 0:
    if line[0] == 0:
        print((ans % (10**9+7)))
    else:
        print((0))
# Original solution
n = int(eval(input()))
a = [int(i) for i in input().split()]

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

can = True
if n % 2 == 0:
    possible_list = [i for i in range(1, n, 2)]
    for k, v in list(a_dict.items()):
        if v != 2 or k not in possible_list:
            can = False
            break
else:
    possible_list = [i for i in range(0, n, 2)]
    if 0 not in a_dict:
        can = False
    elif a_dict[0] != 1:
        can = False
    else:
        a_dict[0] = 2
        for k, v in list(a_dict.items()):
            if v != 2 or k not in possible_list:
                can = False
                break

if can:
    print((2 ** (n // 2) % (10 ** 9 + 7)))
else:
    print((0))


# Optimized solution
n = int(eval(input()))
a = [int(i) for i in input().split()]

a_dict = {}
for v in a:
    if v in a_dict:
        a_dict[v] += 1
    else:
        a_dict[v] = 1

can = True
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in list(a_dict.items()):
        if v != 2 or k not in possible_list:
            can = False
            break
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if 0 not in a_dict:
        can = False
    elif a_dict[0] != 1:
        can = False
    else:
        a_dict[0] = 2
        for k, v in list(a_dict.items()):
            if v != 2 or k not in possible_list:
                can = False
                break

if can:
    print((2 ** (n // 2) % (10 ** 9 + 7)))
else:
    print((0))
# Original solution
import sys
n=int(eval(input()))
a=list(map(int,input().split()))
a.sort()
if(n%2==0):
  if(0 in a):
    print((0))
    sys.exit()
  else:
    num=0
    for i in range(1,n,2):
      if(a.count(i)==2):
        num+=1
        a.remove(i)
        a.remove(i)
      else:
        print((0))
        sys.exit()
    if(len(a)>0):
      print((0))
      sys.exit()
else:
  if(a.count(0)!=1):
    print((0))
    sys.exit()
  else:
    a.remove(0)
    num=0
    for i in range(2,n,2):
      if(a.count(i)==2):
        num+=1
        a.remove(i)
        a.remove(i)
      else:
        print((0))
        sys.exit()
print((int(2**num)%(10**9+7)))

# Optimized solution
import sys
n=int(eval(input()))
a=list(map(int,input().split()))
lis=[0 for i in range(n)]
for i in a:lis[i]+=1
if(1):
  if(lis[0]!=n%2):
    print((0))
    sys.exit()
  num=0
  for i in range(1,n):
    if(i%2==n%2):
      if(lis[i]!=0):
        print((0))
        sys.exit()
    else:
      if(lis[i]!=2):
        print((0))
        sys.exit()
      else:num+=1
  print(((2**num)%(10**9+7)))
# Original solution
n = int(eval(input()))
A = list(map(int,input().split()))

if n%2 == 0:
    for i in range(1,n,2):
        if not A.count(i) == 2:
            print((0))
            break
    else:
        print((2**(n//2)%(10**9+7)))
else:
    if not A.count(0) == 1:
        print((0))
    else:
        for i in range(2,n,2):
            if not A.count(i) == 2:
                print((0))
                break
        else:
            print((2**((n-1)//2)%(10**9+7)))

# Optimized solution
n = int(eval(input()))
A = list(map(int,input().split()))
A.sort()

if n%2 == 0:
    for i in range(n):
        if i%2 == 0:
            if not A[i] == i+1:
                print((0))
                break
        else:
            if not A[i] == i:
                print((0))
                break
    else:
        print((2**(n//2)%(10**9+7)))
else:
    if not A[0] == 0:
        print((0))
    else:    
        for i in range(1,n):
            if i%2 == 0:
                if not A[i] == i:
                    print((0))
                    break
            else:
                if not A[i] == i+1:
                    print((0))
                    break
        else:
            print((2**((n-1)//2)%(10**9+7)))
# Original solution
N = int(input().strip())
A = list(map(int, input().strip().split()))


if N % 2 == 1:
  if A.count(0) != 1:
    print((0))
  else:
    if not all([A.count(i) == 2 for i in range(2, N, 2)]):
      print((0))
    else:
      print((2 ** ((N - 1) // 2) % (10**9 + 7)))
else:
  if not all([A.count(i) == 2 for i in range(1, N, 2)]):
    print((0))
  else:
    print((2 ** ((N // 2) % (10**9 + 7))))


# Optimized solution
N = int(input().strip())
A = list(sorted(map(int, input().strip().split())))

if N % 2 == 0:
  for i in range(0, N, 2):
    if A[i] != A[i+1]:
      print((0))
      break
  else:
    print((2**(N // 2) % 1000000007))
else:
  if A[0] != 0:
    print((0))
  else:
    for i in range(1, N, 2):
      if A[i] != A[i+1]:
        print((0))
        break
    else:
      print((2**((N-1)//2) % 1000000007))
# Original solution
num = int(eval(input()))
mem = list(map(int, input().split()))

mod = 10 ** 9 + 7
flag = True
while 0 in mem:
    mem.remove(0)
for i in mem:
    if not mem.count(i) == 2:
        flag = False
        break
if flag:
    print((int((2 ** (int(len(mem)) / 2) % mod))))
else:
    print((0))

# Optimized solution
num = int(eval(input()))
mem = list(map(int, input().split()))

dic = {}
mod = 10 ** 9 + 7
zeros = 0
flag = True
for i in range(num):
    temp = mem[i]
    if not temp == 0:
        dic.setdefault(str(temp), 0)
        dic[str(temp)] += 1
    else:
        zeros += 1
for key in dic:
    if not dic[key] == 2:
        flag = False
        break
        
if (zeros == 0 or zeros == 1) and flag:
    print((int((2 ** (len(mem) // 2) % mod))))
else:
    print((0))
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))
set_A = set(A)

ans = 1

if n%2==0:
  for a_i in set_A:
    if A.count(a_i)!=2:
      ans = 0
      break
else:
  if A.count(0)!=1:
    ans = 0
  
  set_A.remove(0)
  for a_i in set_A:
    if A.count(a_i)!=2:
      ans = 0
      break
      
if ans!=0:
  ans = 2**(len(set_A))

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

# Optimized solution
n = int(eval(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)))
# Original solution
import sys
readline = sys.stdin.readline

def resolve():
    N = int(eval(input()))
    # A = input().replace(" ", "")
    A = readline().rstrip().split()
    import collections
    counter = collections.Counter(A)
    if N % 2 == 1:
        if counter["0"] != 1:
            print("0")
            return
        for k, v in list(counter.items()):
            if k == "0":
                continue
            if int(k) % 2 == 1:
                print("0")
                return
            if v != 2:
                print("0")
                return
    else:
        for k, v in list(counter.items()):
            if int(k) % 2 == 0:
                print("0")
                return
            if v != 2:
                print("0")
                return
    
    print(( (2**(N//2)) % (10**9+7) ))




if '__main__' == __name__:
    resolve()



# Optimized solution
import sys
readline = sys.stdin.readline

def resolve():
    N = int(eval(input()))
    # A = input().replace(" ", "")
    # A = readline().rstrip().split()
    A = input().split()
    import collections
    counter = collections.Counter(A)
    if N % 2 == 1:
        if counter["0"] != 1:
            print("0")
            return
        for k, v in list(counter.items()):
            if k == "0":
                continue
            if int(k) % 2 == 1:
                print("0")
                return
            if v != 2:
                print("0")
                return
    else:
        for k, v in list(counter.items()):
            if int(k) % 2 == 0:
                print("0")
                return
            if v != 2:
                print("0")
                return
    
    print(( (2**(N//2)) % (10**9+7) ))




if '__main__' == __name__:
    resolve()
# Original solution
import sys
readline = sys.stdin.readline

def resolve():
    N = int(eval(input()))
    # A = input().replace(" ", "")
    # A = readline().rstrip().split()
    A = input().split()
    import collections
    counter = collections.Counter(A)
    if N % 2 == 1:
        if counter["0"] != 1:
            print("0")
            return
        for k, v in list(counter.items()):
            if k == "0":
                continue
            if int(k) % 2 == 1:
                print("0")
                return
            if v != 2:
                print("0")
                return
    else:
        for k, v in list(counter.items()):
            if int(k) % 2 == 0:
                print("0")
                return
            if v != 2:
                print("0")
                return
    
    print(( (2**(N//2)) % (10**9+7) ))




if '__main__' == __name__:
    resolve()



# Optimized solution
def resolve():
    N = int(eval(input()))
    # A = list(input().replace(" ", "")) -> WA
    A = input().split() # -> AC
    import collections
    counter = collections.Counter(A)
    if N % 2 == 1:
        if counter["0"] != 1:
            print("0")
            return
        for k, v in list(counter.items()):
            if k == "0":
                continue
            if int(k) % 2 == 1:
                print("0")
                return
            if v != 2:
                print("0")
                return
    else:
        for k, v in list(counter.items()):
            if int(k) % 2 == 0:
                print("0")
                return
            if v != 2:
                print("0")
                return
    
    print(( (2**(N//2)) % (10**9+7) ))




if '__main__' == __name__:
    resolve()
# Original solution
n=int(eval(input()))
ai=[int(x) for x in input().split()]
if (ai.count(0)==1 or ai.count(0)==0)and all([ai.count(i)==0 or ai.count(i)==2 for i in range(1,n)]):
    nd=n//2
    ans=1
    for i in range(nd):
        ans*=2
        ans%=10**9+7
    print(ans)
else:
    print((0))

# Optimized solution
n=int(eval(input()))
ai=[int(x) for x in input().split()]
#print(len(set(ai)), -(-n // 2))
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))
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

A.sort()
mod = 10 ** 9 + 7
i = 0
res = 0
if N == 1:
  if A[0] == 0:
    print((1))
  else:
    print((0))
  exit(0)
if N % 2 == 1:
  res = 1
  i = 1
  if A[0] == A[1]:
    print((0))
    exit(0)
  if A[0] == 1:
    print((0))
    exit(0)
else:
  res = 2
  i = 2
  if A[0] != A[1]:
    print((0))
    exit(0)
  if A[0] == 0:
    print((0))
    exit(0)
while i < N - 1:
  if A[i] == A[i + 1]:
    if N % 2 == 0:
      if A[i] != 2 * (i / 2 + 1) - 1:
        res = 0
        break
    else:
      if A[i] != 2 * (i // 2 + 1):
        res = 0
        break
    res *= 2
    i += 2
  else:
    res = 0
    break
print((res % mod))

# Optimized solution
N = int(eval(input()))
A = sorted(map(int,input().split()))
B = []

if N%2:
	B = [0]
	for i in range(N//2):
		B += [(i + 1)*2]*2
else:
	for i in range(N//2):
		B += [i*2 + 1]*2	
#print(A, B)
#print(B)
if A==B:
	print((2**(N//2)%((10**9) + 7)))
else:
	print((0))
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
flag=0

if n%2==0:
    b=list(range(1,n,2))
    for i in range(n//2):
        if a.count(b[i])!=2:
            print("0")
            flag+=1
            break
if n%2==1:
    c=list(range(0,n,2))
    for i in range(n//2):
        if i==0:
            if a.count(c[i])!=1:
                print("0")
                flag+=1
                break

        else:
            if a.count(c[i])!=2:
                print("0")
                flag+=1
                break
        
if flag==0:
    print((2**(n//2)%(10**9+7)))

# Optimized solution
n=int(eval(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")
# Original solution
n = int(eval(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")


# Optimized solution
n = int(eval(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")
# Original solution
n = int(eval(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+1] != i+1:
      print((0))
      exit()
else: # 人数が奇数の場合に不整合があるか確認
  if a[0] != 0: # 差分が0存在していることを確認
    print((0))
    exit()
  else:
    for i in range(1,n,2):
      if a[i] != i + 1 or a[i+1] != i + 1:
        print((0))
        exit()
        
ans = 1        
for i in range(n//2):
  ans = ans*2%(10**9+7)
print(ans)

# Optimized solution
n = int(eval(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))
      exit()
else: # 人数が奇数の場合に不整合があるか確認
  if a[0] != 0: # 差分が0存在していることを確認
    print((0))
    exit()
  else:
    for i in range(1,n,2):
      if a[i] != i+1 or a[i] != a[i+1]:
        print((0))
        exit()

ans = 1
for i in range(n//2):
  ans = ans * 2 % (10**9+7) # 組み合わせとしては同じ差分の値を入れ替える2択になるので、結果を2倍にする
print(ans)
# Original solution
from collections import Counter
N = int( eval(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] == 2:
        ans *= 2
        ans %= Q
    else:
        ans = 0
        break
if N%2 == 1:
    if A[0] != 1:
        ans = 0
print(ans)


# Optimized solution
from collections import Counter
N = int( eval(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)))
# Original solution
import sys

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

def beki(n):
    ans = 1
    for _ in range(int(n)):
        ans = (ans * 2) % (10 ** 9 + 7)
    return int(ans)

if n % 2 == 0:
    i = 1
    while True:
        if i in a:
            a.remove(i)
        else:
            print((0))
            sys.exit()
        if i in a:
            a.remove(i)
        else:
            print((0))
            sys.exit()
        i += 2
        if a == []:
            break       
    print((beki(n / 2)))

elif n == 1:
    if a == [0]:
        print("1")
    else:
        print("0")
else:
    i = 2
    while True:
        if i in a:
            a.remove(i)
        else:
            print((0))
            sys.exit()
        if i in a:
            a.remove(i)
        else:
            print((0))
            sys.exit()
        i += 2
        if a == [0]:
            break
    print((beki((n - 1) / 2)))

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

def beki(n):
    ans = 1
    for _ in range(int(n)):
        ans = (ans * 2) % (10 ** 9 + 7)
    return int(ans)

if n % 2 == 0:
    hikaku = []
    for i in range(1, n, 2):
        hikaku += [i, i]
    if sorted(a) == hikaku:
        print((beki(n / 2)))
    else:
        print((0))

elif n == 1:
    if a == [0]:
        print((1))
    else:
        print((0))
else:
    hikaku = [0]
    for i in range(2, n, 2):
        hikaku += [i, i]
    if sorted(a) == hikaku:
        print((beki((n - 1) / 2)))
    else:
        print((0))
# Original solution
n=int(eval(input()));print(([0,2**(n//2)%(10**9+7)][sorted(map(int,input().split()))==[(i+n%2)//2*2+1-n%2for i in range(n)]]))

# Optimized solution
n=int(eval(input()));print(([0,pow(2,(n//2),(10**9+7))][sorted(map(int,input().split()))==[i+(i+n+1)%2for i in range(n)]]))
# Original solution
n=int(eval(input()));print(([0,pow(2,(n//2),(10**9+7))][sorted(map(int,input().split()))==[i+(i+n+1)%2for i in range(n)]]))

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

#データを並び替える
rowdata=[int(i) for i in input().split()]
rowdata.sort()

#nが偶数の時
if n%2==0:
    check=[]
    a=1
    for i in range(1,n,2):
        check.append(i)
        check.append(i)
    if check==rowdata:
        for i in range(int(n/2)):
            a*=2
            a=a%1000000007
        print(a)
    else:
        print((0))
        
#nが奇数の時
else:
    check=[]
    a=1
    if n==1:
        check=[0]
    else:
        for i in range(0,n,2):
            if i==0:
                check.append(i)
            else:
                check.append(i)
                check.append(i)
    if check==rowdata:
        for i in range(int((n-1)/2)):
            a*=2
            a=a%1000000007
        print(a)
    else:
        print((0))

# Optimized solution
n=int(eval(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))
# Original solution
mod = 10 ** 9 + 7
N = int(eval(input()))
A = [int(a) for a in input().split()]

# Nが偶数ならAiは全て奇数、Nが奇数なら Aiは全て偶数でなければならない,なぜなら、2x + Ai = N - 1を満たすxが自然数(非負整数)でなければならないから
# さらに、Nが奇数の時はfor i in range(0, N, 2) において 0が１個、それ以外のiが２個ずつ存在しなければならず(これはAiが全て偶数であることも満たしている)、
# Nが偶数の時はfor i in range(1, N, 2) において 全てのiが２個ずつ存在しなければならない(これはAiがすべて奇数であることも満たしている)
# これを踏まえた上でNが偶数の時は N/2人の位置が決まれば反対側の人の位置も決まり、Nが奇数の時は中央の人は固定として、それ以外 (N-1)/2人の位置が決まれば残りの人は反対側で位置が決まる。それぞれ２通りなので、
# よって
if N % 2 != 0:
    for i in range(0, N, 2):
        if A.count(i) == 2:
            continue
        elif A.count(0) == 1:
            continue
        print((0))
        exit()
    
    #order_count = 1
    #for i in range((N - 1) // 2):
    order_count = 2 ** ((N - 1) // 2) % mod

else:
    for i in range(1, N, 2):
        if A.count(i) != 2:
            print((0))
            exit()
    #order_count = 1
    #for i in range(N // 2):
    order_count = 2 ** (N // 2) % mod

print(order_count)




# Optimized solution
mod = 10 ** 9 + 7
N = int(eval(input()))
A = [int(a) for a in input().split()]
A.sort()

if N % 2 != 0:
    if A[0] == 0:
        for i in range(2, N, 2):
            if not (A[i] == i and A[i-1] == i):
                print((0))
                exit()
        order_count = 2 ** ((N - 1) // 2) % mod
    else:
        print((0))
        exit()

else:
    for i in range(1, N, 2):
        if not (A[i] == i and A[i-1] == i):
            print((0))
            exit()
    order_count = 2 ** (N // 2) % mod 

print(order_count)
# Original solution
import sys
from collections import Counter
MOD = 10 ** 9 + 7
n, *a = list(map(int, sys.stdin.read().split()))

def main():
  c = Counter(a)
  if n & 1:
    if c.get(0, 0) != 1:
      print((0)); return
  for i in range(1 + (n & 1), n, 2):
    if c.get(i, 0) != 2:
      print((0)); return 
  print((pow(2, n // 2, MOD)))

if __name__ ==  '__main__':
  main()

# Optimized solution
import sys
from collections import Counter
MOD = 10 ** 9 + 7
n, *a = list(map(int, sys.stdin.read().split()))

def main():
  c = Counter(a)
  if n & 1:
    if c[0] != 1:
      print((0)); return
  for i in range(1 + (n & 1), n, 2):
    if c[i] != 2:
      print((0)); return 
  print((pow(2, n // 2, MOD)))

if __name__ ==  '__main__':
  main()