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

import bisect

D = 10 ** 4

X = int(input())

L = [i**5 for i in range(-D, D)]
L2 = [i for i in range(-D, D)]

idx = bisect.bisect_left(L, X)-1

B = L[:idx]
A = L[idx:]

for a in A:
    for b in B:
        if a - b == X:
            break
    else:
        continue
    break

print(L2[L.index(a)], L2[L.index(b)])


### FIXED CODE ###

import bisect
import math

D = 120

X = int(input())

for a in range(-D, D):
    for b in range(-D-1, D-1):
        if a**5 - b**5 == X:
            break
    else:
        continue
    break

print(a, b)
### BUGGY CODE ###


N, K=map(int,input().split())
arr = list(map(int,input().split()))
if(K>= N):
  print('0')
else:
  if (K > 0):
    for i in range(K):
      arr.remove(max(arr))

  print(sum(arr))


### FIXED CODE ###

N, K=map(int,input().split())
arr = list(map(int,input().split()))
if(K>= N):
  print('0')
else:
  if (K > 0):
    new_arr = sorted(arr)
    arr = new_arr[:-K]
  print(sum(arr))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)
    ans = [0]*n
for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)
dfs()
print(*ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
n,q = map(int, input().split())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

ans = [0]*n

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

def dfs(i = 0, r = -1):
    for j in e[i]:
        if j != r:
            ans[j] += ans[i]
            dfs(j, i)

dfs()

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

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

num_without_s = m/4
num_with_s = 0
m_tmp = m
n_tmp = n
while m_tmp > 1 and n_tmp > 0:
    num_with_s += 1
    m_tmp = m_tmp - 2
    n_tmp = n_tmp - 1

while m_tmp > 3:
    num_with_s += 1
    m_tmp = m_tmp - 4

if num_with_s > num_without_s:
    print(int(num_with_s))
else:
    print(int(num_without_s))
    

### FIXED CODE ###

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

num_without_s = m/4
num_with_s = 0
m_tmp = m
n_tmp = n
""" while m_tmp > 1 and n_tmp > 0:
    num_with_s += 1
    m_tmp = m_tmp - 2
    n_tmp = n_tmp - 1
 """

if m >= (2 * n):
    num_with_s = n
    if (m_tmp - 2*n) > 3:
        num_with_s = num_with_s + int(((m_tmp - 2*n) / 4))
else:
    num_with_s = int(m/2)

if num_with_s > num_without_s:
    print(int(num_with_s))
else:
    print(int(num_without_s))
### BUGGY CODE ###

class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [0] * (self.size * 2 - 1)
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

N = int(input())
S = input()
Q = int(input())

segt = SegT(N)
for i in range(N):
    x = ord(S[i]) - ord('a')
    segt.update(i, (1<<x))

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        x = ord(r) - ord('a')
        segt.update(int(l)-1, (1<<x))
    else:
        x = segt.get(int(l)-1,int(r))
        ans = 0
        for i in range(26):
            if x>>i&1: ans += 1
        print(ans)


### FIXED CODE ###

class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [0] * (self.size * 2 - 1)
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

N = int(input())
S = input()
Q = int(input())

segt = SegT(N)
for i in range(N):
    x = ord(S[i]) - ord('a')
    segt.update(i, (1<<x))

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        x = ord(r) - ord('a')
        segt.update(int(l)-1, (1<<x))
    else:
        x = segt.get(int(l)-1,int(r))
        ans = 0
        for i in range(26):
            if x>>i&1: ans += 1
        print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

def resolve():
    n = int(input())
    aaa = [int(input()) for _ in range(n)]
    maxa = max(aaa)
    for i in range(n):
        if maxa == aaa[i]:
            print(max(aaa[:i]+aaa[i+1:]))
        else:
            print(maxa)
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    aaa = [int(input()) for _ in range(n)]
    sorta = sorted(aaa, reverse=True)
    maxa = sorta[0]
    seconda = sorta[1]
    for i in range(n):
        if maxa == aaa[i]:
            print(seconda)
        else:
            print(maxa)
resolve()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=[a[0]]
l2=[]
def al(num):
    l1.append(num)
def n1(num):
    for j in range(num):
        if l1[j]==num1:
            break
    return j
def n2(num5):
    return num5 in l1
for i in range(n):
    num1=a[l1[-1]-1]
    str=n2(num1)
    if str==True:
        break
    else:
        al(num1)
num=n1(len(l1))
l2=l1[num:]
l1=l1[:num]
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l1=set([a[0]])
num1=a[0]
num2=1
l2=[]
def al(num):
    l1.add(num)
def n2(num5):
    return num5 in l1
for i in range(n):
    num1=a[num1-1]
    al(num1)
    if num2==len(l1):
        break
    else:
        num2=len(l1)
l1=list(l1)
num=l1.index(num1)
l2=l1[num:]
l1=l1[:num]
num1=len(l1)
num2=len(l2)
if k<=num1:
    print(l1[k-1])
else:
    num3=(k-num1)%num2
    print(l2[num3-1])
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
i2p = {0:1}
p2i = {1:0}
cur = A[0]
i = 1
while True:
    i2p[i] = cur
    p2i[cur] = i
    if A[cur-1] in i2p.values():
        break
    cur = A[cur-1]
    i+=1
i = p2i[A[cur-1]]
num_loop = len(i2p) - i 
if K < i:
    print(i2p[K])
else:
    print(i2p[i+(K-i)%num_loop])

### FIXED CODE ###

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

i2p = {0:1}
p2i = {1:0}
cur = A[0]
is_loop = {}
for i in range(N+1):
    is_loop[i] = False
i = 1
while True:
    i2p[i] = cur
    p2i[cur] = i
    is_loop[cur] = True
    if is_loop[A[cur-1]]:
        break
    cur = A[cur-1]
    i+=1
i = p2i[A[cur-1]]
num_loop = len(i2p) - i 
if K < i:
    print(i2p[K])
else:
    print(i2p[i+(K-i)%num_loop])
### BUGGY CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def factorize_list(n):
    result = []
    for val,perm in factorize(n):
        result+= [val]*perm
    return result

factorized = factorize_list(M)

def mul(args):
    r =1
    for v in args:
        r*= v
    return r


result=1
for i in range(len(factorized)//2+1):
    for vals in set(itertools.combinations(factorized,i)):
        A= mul(vals)
        B= M//A
        #print(A,B,vals)
        if A>=N:
            result = max(B,result)
        if B>=N:
            result = max(A,result)


print(result)

### FIXED CODE ###

import itertools


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def factorize_list(n):
    result = []
    for val,perm in factorize(n):
        result+= [val]*perm
    return result



def mul(args):
    r =1
    for v in args:
        r*= v
    return r

def getcomb(l):
    if len(l)==0:
        return [1]
    result = []
    v,perm = l[0]
    for i in range(perm+1):
        result+= [(v**i)*val for val in getcomb(l[1:])]
    return result


N,M=list(map(int,input().split()))
factorized = factorize(M)
result=1
for i in range(len(factorized)//2+1):
    for vals in getcomb(factorized):
        A= vals
        B= M//A
        #print(A,B,vals)
        if A>=N:
            result = max(B,result)
        if B>=N:
            result = max(A,result)


print(result)
### BUGGY CODE ###

N, X, Y = map(int, input().split())

g = [[] for _ in range(N)]
for i in range(N - 1):
    u = i
    v = i + 1
    g[u].append(v)
    g[v].append(u)
g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[0] * N for _ in range(N)]
def bfs(i):
    visited = [False] * N
    que = deque([i])
    dis[i][i] = 0
    visited[i] = True
    
    while que:
        p = que.popleft()
        for new in g[p]:
            if visited[new]:
                continue
            else:
                visited[new] = True
                que.append(new)
                dis[i][new] = dis[i][p] + 1
                count[dis[i][new] - 1] += 1

count = [0] * (N - 1)
for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)


### FIXED CODE ###

N, X, Y = map(int, input().split())

g = [[]  for i in range(N)]
for i in range(N):
    u = i
    v = i + 1
    if v < N:
        g[u].append(v)
        g[v].append(u)

g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[float('Inf')] * N for _ in range(N)]
count = [0] * (N - 1)
def bfs(i):
    d = [False] * N
    que = deque()
    #for j in g[i]:
    que.append(i)
    d[i] = True
    dis[i][i] = 0
    pre = i
    while que:
        p = que.popleft()

        for k in g[p]:
            if d[k]:
                continue
            else:
                d[k] = True
                que.append(k)
                dis[i][k] = dis[i][p] + 1
                dis[k][i] = dis[i][p] + 1
                count[dis[i][k] - 1] += 1 
                #count[dis[k][i] - 1] += 1
        pre = p

for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N = int(input().strip())
As = list(map(int, input().strip().split(' ')))

xs = [0] * N
for n in range(N):
    rotate = As[n:] + As[:n]
    xs[n] = sum(rotate[0::2]) - sum(rotate[1::2])
print(" ".join(map(str, xs)))

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input().strip())
As = list(map(int, input().strip().split(' ')))


xs = [0] * N
xs[0] = sum(As[0::2]) - sum(As[1::2])
for n in range(1, N):
    xs[n] = As[n-1] * 2 - xs[n - 1]
print(" ".join(map(str, xs)))
### BUGGY CODE ###

import math
import time

t = time.time()
def iip():
    return [int(i) for i in input().split()]

H, N = iip()
mp_for_damage = [10**9 for i in range(H+1)]
mp_for_damage[0] = 0

for i in range(N):
    a, b = iip()
    for j in range(H+1):
        if a < H and mp_for_damage[a] < b:
            continue

        for k in range(1, a):
            if k > H:
                break
            mp_for_damage[k] = min(mp_for_damage[k], b)

        if j + a > H:
            break
        mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

#print(mp_for_damage)
print(mp_for_damage[H])

#print(time.time() - t)

### FIXED CODE ###

import math
import time


t = time.time()
def iip():
    return [int(i) for i in input().split()]

def main():
    H, N = iip()
    mp_for_damage = [10**9 for i in range(H+1)]
    mp_for_damage[0] = 0
    ab = []

    for i in range(N):
        ab.append(iip())

    ab= sorted(ab, key=lambda x:x[0]/x[1], reverse=True)

    for i in range(N):
        a, b = ab[i]

        for k in range(1, min(a, H) + 1):
            mp_for_damage[k] = min(mp_for_damage[k], b)
            # print(k, b)

        if a >= H:
            mp_for_damage[H] = min(mp_for_damage[H], b)
            continue

        if a < H and mp_for_damage[a] < b:
            continue

        for j in range(H-a+1):
            mp_for_damage[j+a] = min(mp_for_damage[j+a], mp_for_damage[j] + b)

    #print(mp_for_damage)
    #print(mp_for_damage)
    print(mp_for_damage[H])

    #print(time.time() - t)

main()
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

if not 1 in list_a:
    dp[0]=1
    dp[1]=1
else:
    dp[0]=1
    dp[1]=0


for i in range(2,n+1):
    if i in list_a:
        dp[i]=0
    else:
        dp[i] = dp[i-1] + dp[i-2]
ans = dp[n] % big_prime
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

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

ans = 1
for x in range(N):
    ans *= A[x]

if ans > 1.0e+18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

"""
ans = 1
for x in range(N):
    ans *= A[x]
"""
A = sorted(A)

ans = 1
for x in A:
    ans *= x
    if ans == 0 or ans > 1.0e+18:
        break


if ans > 1.0e+18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == max(h)]
b = [i for i, x in enumerate(w) if x == max(w)]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
if flag:
  ans = c+d
else:
  ans = c+d-1
print(ans)


### FIXED CODE ###

H, W, M = map(int, input().split())
h = [0] * (H+1)
w = [0] * (W+1)
l = set()
for i in range(M):
  x, y = map(int, input().split())
  h[x] += 1
  w[y] += 1
  l.add((x, y))
  
c = max(h)
d = max(w)
a = [i for i, x in enumerate(h) if x == c]
b = [i for i, x in enumerate(w) if x == d]

flag = False
for s in a:
  for t in b:
    if (s, t) not in l:
      flag = True
      break
  if flag:
    break
ans = c+d
if not flag:
  ans -= 1
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] <= dist[h][w] + 1:
            continue
        dist[ny][nx] = dist[h][w] + 1
        ans = max(ans, dist[ny][nx])
        que.append(ny * W + nx)

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

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

import math

a, b, n = (int(x) for x in input().split())

x = 0
max_x = 0

while x <= n:
    val = math.floor(a * x / b) - a * math.floor(x / b)
    if val > max_x:
        max_x = val
    x += 1

print(max_x)

### FIXED CODE ###

import math

a, b, n = (int(x) for x in input().split())

if b > n:
    print(math.floor(a * n / b) - a * math.floor(n / b))
else:
    print(math.floor(a * (b -1) / b) - a * math.floor((b -1) / b))
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]


def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,b):
    k += num-1
    if seg[k]==set([b]):
        return ()
    seg[k] = set([b])
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

ide_ele =set()

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set() for i in range(2*num)]

for i in range(N):
    update(i,S[i])

for type,i,c in Query:

    if type=="1":
        update(int(i)-1,c)
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)


### FIXED CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = seg[k*2+1]|seg[k*2+2]

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)
### 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
		for i in [x*2 for x in range(1,int(N/2) + 1)]:
			if a.count(i) != 2:
				return 0
	else:
		for i in [x*2 - 1 for x in range(1,int(N/2) + 1)]:
			if a.count(i) != 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()))
a_ = list()

count=0
cont=1

#print(a)
#print(a[2])

while cont :
  for i in range(len(a)) :
    #print("for")
    #print(a[i])
    if a[i]%2 == 0 :
      a_.append(a[i]/2)
    else :
      cont=0
      break
  if cont==1 :
    #print("cont")
    #print(count)
    a=a_
    count += 1
  else :
    break

print(count)

### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))
#a_ = np.array()

count=0
cont=1

#print(a)
#print(a[2])

while cont :
  a_ = np.unique(a % 2)
  if a_[0]==0 and len(a_) == 1 :
    count += 1
  else :
    break

  a = a / 2

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

#!/usr/bin/env python3
import sys
import collections


def solve(S: int):
    S = str(S)

    count = collections.defaultdict(int)
    count[0] = 1
    tmp = ''
    for idx, s in enumerate(S[::-1]):
        digit = int(S[-idx:])
        count[digit % 2019] += 1
    
    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(S: int):
    S = list(map(int, list(str(S))))
    count = collections.defaultdict(int)

    count[0] = 1
    tmp = ''
    prev_modulo = 0
    for idx, s in enumerate(S[::-1]):
        prev_modulo = (s * pow(10, idx, 2019) + prev_modulo) % 2019
        count[prev_modulo] += 1

    result = 0
    for k, v in count.items():
        result += v * (v-1) // 2
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = int(next(tokens))  # type: int
    solve(S)

if __name__ == '__main__':
    main()