Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
p = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

D = uf.all_group_members()

ans = []

for L in D.values():
  temp = set()
  for i in L:
    temp.add(p[i]-1)
  for i in set(L)&temp:
    ans.append(i)
 
print(len(ans))

### FIXED CODE ###

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
P = list(map(int, input().split()))

uf = UnionFind(N)

for _ in range(M):
  x, y = map(lambda x: int(x)-1, input().split())
  uf.union(x, y)

ans = 0

for i, p in enumerate(P):
  if uf.same(i, p-1):
    ans += 1

print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
count=0

for x in range(0, K+1):
    for y in range(0, K+1):
        for z in range(0, K+1):
            if(x+y+z==S):
                count+=1

print(count)

### FIXED CODE ###

def main():
    K, S = map(int, input().split())
    count=0

    for x in range(0, K+1):
        for y in range(0, K+1):
            if(0<=S-x-y<=K):
                count+=1

    print(count)

main()
### BUGGY CODE ###

from math import gcd
x=int(input())
y=0
for a in range(x):
  for b in range(x):
    for c in range(x):
      y+=gcd(gcd(a+1,b+1),c+1)
print(y)

### FIXED CODE ###

from math import gcd
z=range(1,1+int(input()))
y=0
for a in z:
  for b in z:
    for c in z:
      y+=gcd(gcd(a,b),c)
print(y)
### BUGGY CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [0] * N

for i in range(N-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def propagate(node, acc, ancestors):
    counter[node] += acc
    acc = counter[node]
    ancestors.add(node)
    for c in neighbor[node]:
        if c not in ancestors:
            propagate(c, acc, ancestors)

propagate(0, 0, set())
print(*counter, sep=' ')


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)
N, Q = map(int, input().split())

neighbor = defaultdict(list)
counter = [0] * N
pcounter = [None] * N
depth = {0: 0}

for i in range(N-1):
    a, b = map(int, input().split())
    a_deper, b_deeper = False, False
    if a in depth and b not in depth:
        depth[b] = depth[a] + 1
    if b in depth and a not in depth:
        depth[a] = depth[b] + 1
    if a in depth and b in depth:
        if depth[a] < depth[b]:
            neighbor[a-1].append(b-1)
        else:
            neighbor[b-1].append(a-1)
    else:
            neighbor[a-1].append(b-1)
            neighbor[b-1].append(a-1)

for i in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

def solve():
    stack = [(0, None)]
    while stack:
        (node, parent) = stack.pop()
        pcounter[node] = counter[node]
        if parent is not None:
            pcounter[node] += pcounter[parent]
        for c in neighbor[node]:
            if pcounter[c] is None:
                stack.append((c, node))

solve()
print(*pcounter, sep=' ')
### BUGGY CODE ###

N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
D = {}
S = []
A = []
u, v, w = map(int, input().split())
if w % 2 == 0:
  D[u], D[v] = 0, 0
else:
  D[u], D[v] = 0, 1
for i in range(N - 2):
  u, v, w = map(int, input().split())
  if u in D:
    D[v] = (D[u] + w) % 2
  elif v in D:
    D[u] = (D[v] + w) % 2
  else:
    if w % 2 == 0:
      S.append([u, v])
    else:
      A.append([u, v])
while len(D) != N:
  for i in range(len(S)):
    if S[i][0] in D:
      D[S[i][1]] = D[S[i][0]]
    elif S[i][1] in D:
      D[S[i][0]] = D[S[i][1]]
  for i in range(len(A)):
    if A[i][0] in D:
      D[A[i][1]] = (D[A[i][0]] + 1) % 2
    elif A[i][1] in D:
      D[A[i][0]] = (D[A[i][1]] + 1) % 2
for i in range(1, N+1):
  print(D[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
L = [-1 for i in range(N)]
flg = [0 for i in range(N)]
M = [[] for i in range(N)]
for i in range(N-1):
  u, v, w = map(int, input().split())
  M[u-1].append([v-1, w%2])
  M[v-1].append([u-1, w%2])
L[0] = 0
def dist(m, d):
  L[m] = d % 2
  for i in M[m]:
    if L[i[0]] == -1:
      dist(i[0], i[1] + d)
dist(0, 0)
for i in range(N):
  print(L[i])
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
A = 1
if a[0] == 0:
    A = 0
else: 
    for i in range(N):
        A = A * a[i]
if A > 1000000000000000000:
    print(-1)
else:
    print(A)


### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
A = 1
if 0 in a:
  print(0)
  exit()
for i in range(N):
  A = A * a[i]
  if A > 1000000000000000000:
    print(-1)
    exit()
print(A)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
    mn,mx=i,N//i*i
    ko=(mx-mn)//i+1
    ans+=(mn+mx)*ko//2
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
    mn,mx=i,N//i*i
    ko=(mx-mn)//i+1
    ans+=(mn+mx)*ko//2
print(ans)
### BUGGY CODE ###

import decimal

N, K = map(int, input().split())
n = decimal.Decimal(N)
result = decimal.Decimal(0.00000000000)

def check(i, K):
    count = 0
    while (K > i):
        i *= 2
        count += 1
    return count

for i in range(1,N+1):
    count = check(i, K)
    dec = decimal.Decimal(1.00000000000)
    for j in range(count):
        dec /= decimal.Decimal(2.00000000000)
    result += dec

print(result/n)

### FIXED CODE ###

N, K = map(int, input().split())
result = 0

def check(i, K):
    count = 0
    while (K > i):
        i *= 2
        count += 1
    return count

for i in range(1,N+1):
    count = check(i, K)
    dec = 1
    for j in range(count):
        dec /= 2.0
    result += dec

print(round(result/N, 12))
### BUGGY CODE ###



from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

    A = [list(map(int, input().split())) for _ in range(N)]

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j != 0:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
            b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    f = True
    while f:
        f = False
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
                    f = True
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###


from collections import deque

N = int(input())
match_order = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]


q = deque(range(N))
finish_by = [0] * N
next_opponent = [None] * N

while q:
    a = q.popleft()
    # aの残りの順で一番初めに戦う対戦相手を取り出す
    b = match_order[a].popleft()
    if next_opponent[b] == a:
        finish_by[a] = finish_by[b] = max(finish_by[a], finish_by[b]) + 1
        # a,bについて、まだ対戦相手が残っているならキューに積む
        if match_order[a]:
            q.append(a)
        if match_order[b]:
            q.append(b)
    # bの残りの順で戦う相手がaではないなら、順番が来るまで待つ
    else:
        next_opponent[a] = b

# 対戦相手が残っている人がいる場合、条件通りに終わることができない
if any(match_order):
    print(-1)
else:
    print(max(finish_by))
### BUGGY CODE ###

from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcdArr(a):
    return reduce(gcd, a)

n = int(input())
ret = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        for c in range(1, n + 1):
            ret += gcdArr((a, b, c))
print(ret)

### FIXED CODE ###

from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcdArr(a):
    return reduce(gcd, a)

n = int(input())
ret = 0
for a in range(1, n + 1):
    for b in range(1, n + 1):
        gcd_ = gcd(a, b)
        if gcd_ == 1:
            ret += n
            continue
        for c in range(1, n + 1):
            ret += gcd(gcd_, c)
print(ret)
### BUGGY CODE ###

n, m = map(int, input().split())
d = {}
for i in range(m):
    x, y = map(int, input().split())
    if x not in d.keys():
        d[x] = []
    d[x].append(y)
flag = False
for i in d.keys():
    if i == 1:
        l = d[i]
        for j in l:
            if j in d.keys():
                if n in d[j]:
                    flag = True
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
s = [0 for i in range(n)]
e = [0 for i in range(n)]
for i in range(m):
    x, y = map(int, input().split())
    if x == 1:
        s[y] = 1
    elif y == n:
        e[x] = 1
flag = False
for i in range(n):
    if s[i] == 1 and e[i] == 1:
        flag = True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
N, M, P = [int(x) for x in input().split()]
forward = {}
backward = {}
for _ in range(M):
  A, B, C = [int(x) for x in input().split()]
  forward[A] = forward.get(A, {})
  if B in forward[A]:
    forward[A][B] = max(forward[A][B], C-P)
  else:
    forward[A][B] = C-P
  backward[B] = backward.get(B, {})
  if A in backward[B]:
    backward[B][A] = max(backward[B][A], C-P)
  else:
    backward[B][A] = C-P
#print(forward)
#print(backward)
reachable = set([N])
to_track = set([N])
while to_track:
  x = to_track.pop()
  if x not in backward:
    continue
  for y in backward[x]:
    if y not in reachable:
      to_track.add(y)
      reachable.add(y)
#print(reachable)
if 1 not in reachable:
  print(-1)
  sys.exit()

forward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
           for k, v in forward.items() if k in reachable}
#print(forward)
# backward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
#            for k, v in backward.items() if k in reachable}
#print(backward)

dist = {k: -float('inf') for k in reachable} 
dist[1] = 0
#print(reachable)
#print(dist)
#print(forward)
for _ in range(len(reachable)):
  renewed = False
  for x, y_dict in forward.items():
    for y in y_dict:
 #     print(x, y, forward[x][y], dist[x], dist[y])
      if dist[y] < dist[x] + forward[x][y]:
        renewed = True
        dist[y] = dist[x] + forward[x][y]
if renewed:
  # print('loop')
  print(-1)
else:
  print(max(0,dist[N]))
  
  


### FIXED CODE ###

import sys
N, M, P = [int(x) for x in input().split()]
forward = {}
backward = {}
for _ in range(M):
  A, B, C = [int(x) for x in input().split()]
  forward[A] = forward.get(A, {})
  if B in forward[A]:
    forward[A][B] = max(forward[A][B], C-P)
  else:
    forward[A][B] = C-P
  backward[B] = backward.get(B, {})
  if A in backward[B]:
    backward[B][A] = max(backward[B][A], C-P)
  else:
    backward[B][A] = C-P
#print(forward)
#print(backward)
reachable = set([N])
to_track = set([N])
while to_track:
  x = to_track.pop()
  if x not in backward:
    continue
  for y in backward[x]:
    if y not in reachable:
      to_track.add(y)
      reachable.add(y)
#print(reachable)
if 1 not in reachable:
  print(-1)
  sys.exit()

forward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
           for k, v in forward.items() if k in reachable}
#print(forward)
# backward = {k: {k2: v2 for k2, v2 in v.items() if k2 in reachable}
#            for k, v in backward.items() if k in reachable}
#print(backward)

dist = {k: -float('inf') for k in reachable} 
dist[1] = 0
#print(reachable)
#print(dist)
#print(forward)
for _ in range(len(reachable)):
  renewed = False
  for x, y_dict in forward.items():
    for y in y_dict:
 #     print(x, y, forward[x][y], dist[x], dist[y])
      if dist[y] < dist[x] + forward[x][y]:
        renewed = True
        dist[y] = dist[x] + forward[x][y]
if renewed:
  # print('loop')
  print(-1)
else:
  print(max(0,dist[N]))
### BUGGY CODE ###

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

mod = int(1e9+7)
def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)

LR = [1]*(n+2) #LR[k] = (L+R)C(k)
LDR = [0]*(n+2)
LDDR = [0]*(n+2)

_LCR = [1] * (n+2) # _LCR[k] = (L+C+R)C(k)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
LDCR = [0] * (n+2) #最後に*2を忘れないこと
LDCDR = [0] * (n+2)

for k in range(1,n+2):
  LR[k] = LR[k-1] * (L+R+1-k) // k
  LDR[k] = LR[k-1]
  LDDR[k] = LDR[k-1]
  
  _LCR[k] = _LCR[k-1] * (L+C+R+1-k) // k
  
  LCR[k] = _LCR[k] - LR[k]
  LDCR[k] = LCR[k-1]
  LDCDR[k] = LDCR[k-1]
  
  print((LR[k] + LDR[k] + LDDR[k] + LCR[k] + 2*LDCR[k] + LDCDR[k])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)

### FIXED CODE ###

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

mod = int(1e9+7)
def powermod(p,n,mod):
    #if n==0: return 1
    if n==1:
        return p%mod
    if n%2:
        return powermod(p,n//2,mod)**2 * p %mod
    else:
        return powermod(p,n//2,mod)**2 %mod


memo={}
for i, a in enumerate(A):
  if a in memo:
    L = memo[a]
    C = i - memo[a] -1
    R = len(A) - i-1
    break
  else:
    memo[a] = i
    
#print(L,C,R)
_LR = [0]*(n+3)
_LCR = [0] * (n+3) # _LCR[k] = (L+C+R)C(k)
_k = [0] * (n+3)
_LR[0] = _LCR[0] = _k[0] = 1

LR = [0]*(n+2) #LR[k] = (L+R)C(k)
LR[0] = 1
#LDR = [0]*(n+2)
#LDDR = [0]*(n+2)

LCR = [0] * (n+2) # LCR[k] = _LCR[k] - LR[k]
#LDCR = [0] * (n+2) #最後に*2を忘れないこと
#LDCDR = [0] * (n+2)

for k in range(1,n+2):
  _LR[k] = (_LR[k-1] * (L+R+1-k)) %mod
  _LCR[k] = (_LCR[k-1] * (L+C+R+1-k))% mod
  _k[k] = (_k[k-1] * powermod(k, mod-2, mod)) %mod
  
  LR[k] = (_LR[k] * _k[k])%mod
#  LDR[k] = LR[k-1]
#  LDDR[k] = LDR[k-1]
  
  LCR[k] = (_LCR[k] * _k[k])%mod - LR[k]
#  LDCR[k] = LCR[k-1]
#  LDCDR[k] = LDCR[k-1]
  #print(LR, LCR)
  print((LR[k] + LR[k-1] + LR[k-2] + LCR[k] + 2*LCR[k-1] + LCR[k-2])%mod)
  
#print(LR)
#print(LDR)
#print(LDDR)
#print(_LCR)
#print(LCR)
#print(LDCR)
#print(LDCDR)
### BUGGY CODE ###

N= int(input())
from collections import Counter

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

Q = int(input())

li = [list(map(int,input().split())) for i in range(Q)]


memo2=0

S = sum(A)
cou = Counter(A)

for i in range(Q):
    global ohno
    S+=cou[li[i][0]]*(li[i][1]-li[i][0])
    print(S)
    a = cou[li[i][0]]
    cou[li[i][1]]+=a
    cou[li[i][0]]=0
    
    if set(cou.values())==1:
        global ohno
        memo1=i
        memo2=cou[max(cou.values())]
        for i in range(memo1+1,Q):
            if li[i][0]==memo2:
                print(N*li[i][1])
                memo2=li[i][1]
            else:
                print(memo2*N)

### FIXED CODE ###

N = int(input())


A = list(map(int,input().split()))
ok = [0]*pow(10,6)
Q = int(input())

li = [list(map(int,input().split())) for i in range(Q)]

for i in range(N):
    ok[A[i]]+=1
memo1=0
memo2=0

S = sum(A)
for i in range(Q):

    S+=ok[li[i][0]]*(li[i][1]-li[i][0])
    print(S)
    a = ok[li[i][0]]
    ok[li[i][1]]+=a
    ok[li[i][0]]=0
### BUGGY CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))
    # print("deb", Xms, Xml, p2m, Xim, n1)
    cnt = f(Xim) + 1
    print(cnt)



### FIXED CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

N = int(raw_input())
A = list(map(int,raw_input().split()))
MOD = 10**9 + 7
def calc(a):
	if 0 in a:
		if a.count(0) != 1:
			return 0
		a.remove(0)
		b = [a.count(i*2) for i in range(1,int(N/2) + 1)]
		if b.count(2) != int(N/2):
			return 0
	else:
		b = [a.count(i*2-1) for i in range(1,int(N/2) + 1)]
		if b.count(2) != int(N/2):
			return 0

	return 2 ** int(N/2)
if N % 2 is 0:
	if len(filter(lambda n:n%2==0, A)) > 0:
		print(0)
	else:
		print(calc(A) % MOD)
else:
	if len(filter(lambda n:n%2==1, A)) > 0:
		print(0)
	else:
		print(calc(A) % MOD)

### FIXED CODE ###

N = int(raw_input())
A = list(map(int,raw_input().split()))
A.sort()
MOD = 10**9 + 7
def calc(a):
	if N % 2 == 0:
		B = [int(i/2)*2 + 1 for i in range(0,N)]
		if A != B:
			return 0
	else:
		B = [int(i/2)*2 for i in range(1,N+1)]
		if A != B:
			return 0
	return 2 ** int(N/2)

print(calc(A) % MOD)
### BUGGY CODE ###

n=int(input())

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

ans=1

for i in range(n):
  ans=ans*a[i]

if ans>(10**18):
  print("-1")
else:
  print(ans)

### FIXED CODE ###

n=int(input())

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

ans=1

for i in range(n):
  if ans>0 or a[i]==0:
    ans=ans*a[i]
  if ans>10**18:
    ans=-1

print(ans)
### BUGGY CODE ###

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

for i in a:
  c = a.count(i)
  
  if c >=2:
    print("NO")
    exit()
    
print("YES")

### FIXED CODE ###

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

a.sort()

for i in range(n-1):  
  if a[i] == a[i+1]:
    print("NO")
    exit()

print("YES")
### BUGGY CODE ###

s = input()
k = int(input())

s1 = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        s1.append(s[i:j])
s1.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s1[i] not in substring:
            substring.append(s1[i])
        i = i + 1
    except:
        break
print(substring[k - 1])

### FIXED CODE ###

s = input()
k = int(input())

s1 = []
for i in range(len(s)):
    for j in range(i + 1, i + k + 1):
        s1.append(s[i:j])
s1.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s1[i] not in substring:
            substring.append(s1[i])
        i = i + 1
    except:
        break
print(substring[k - 1])
### BUGGY CODE ###

k,s = map(int,input().split())

count = 0
num = range(k+1)
for x in num:
  for y in num:
    for z in num:
      if x + y + z == s:
        count += 1

print(count)

### FIXED CODE ###

k,s = map(int,input().split())

count = 0
for x in range(k+1):
  for y in range(k+1):
    a = s - x - y
    if a >= 0 and a <= k:
      count += 1

print(count)
### BUGGY CODE ###

x = int(input())

def bin_s(l, r, a):
    while l <= r:
        mid = l + r // 2
        if a ** 5 - mid ** 5 == x:
            return (mid, True)
        elif a ** 5 - mid ** 5 > x:
            l = mid + 1
        else:
            r = mid - 1
    return (-1, False)

def search(x: int) -> (int, int):
    a = 1
    while True:
        if a ** 5 - (a - 1)** 5 <= x <= a ** 5 + (a - 1)** 5:
            b, j = bin_s(-a + 1, a - 1, a)
            if j:
                return (a, b)
        a += 1

a, b = search(x)
print(f"{a} {b}")


### FIXED CODE ###

x = int(input())

def search(x: int) -> (int, int):
    for a in range(-1000, 1001):
        for b in range(-1000, 1001):
            if a ** 5 - b ** 5 == x:
                return (a, b)
    return (-2000, -2000)

a, b = search(x)
print(f"{a} {b}")