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

import sys
sys.setrecursionlimit(10**6+5)

class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    def add(self, s, bucket, idx_s):
        c = s[idx_s]
        if self.child[c] is None:
            self.child[c] = Node()
        for i, cnt in enumerate(bucket):
            if cnt:
                self.counts[i] += 1
        bucket[c] -= 1
        if idx_s >= 1:
            self.child[c].add(s, bucket, idx_s-1)

    def get(self, s, idx_s):
        c = s[idx_s]
        if idx_s > 0:
            return self.child[c].get(s, idx_s-1)
        else:
            return self.counts[c]

trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b, len(s)-1)
ans = -N
for s in S:
    ans += trie.get(s, len(s)-1)
print(ans)


### FIXED CODE ###

class Node:
    def __init__(self):
        self.child = [None] * 26
        self.counts = [0] * 26

    # def add(self, s, bucket, idx_s):
    #     c = s[idx_s]
    #     if self.child[c] is None:
    #         self.child[c] = Node()
    #     for i, cnt in enumerate(bucket):
    #         if cnt:
    #             self.counts[i] += 1
    #     bucket[c] -= 1
    #     if idx_s >= 1:
    #         self.child[c].add(s, bucket, idx_s - 1)
    #     else:
    #         Leaves.append(self.counts)

    def add(self, s, bucket):
        node = self
        for idx_s, c in zip(range(len(s)-1, -1, -1), s[::-1]):
            if node.child[c] is None:
                node.child[c] = Node()
            for i, cnt in enumerate(bucket):
                if cnt:
                    node.counts[i] += 1
            bucket[c] -= 1
            if idx_s > 0:
                node = node.child[c]
        Leaves.append(node.counts)

    # def get(self, s, idx_s):
    #     c = s[idx_s]
    #     if idx_s > 0:
    #         return self.child[c].get(s, idx_s-1)
    #     else:
    #         return self.counts[c]

Leaves = []
trie = Node()
N = int(input())
S = [[ord(c)-97 for c in input()] for _ in range(N)]
for s in S:
    b = [0] * 26
    for c in s:
        b[c] += 1
    trie.add(s, b)
ans = -N
# for s in S:
#     ans += trie.get(s, len(s)-1)
for s, l in zip(S, Leaves):
    ans += l[s[0]]
print(ans)
### BUGGY CODE ###

from collections import deque
N=int(input())
data=deque([int(input()) for i in range(N)])
mae=N//2+N%2
i=1
count=0

while i<N:
    data2=list(data)
    #print(data)
    if (data[i]+1) in data2[:i]:
        #print("unko",i)
        t=data[i]
        if t<=mae:

            data.remove(t)
            data.appendleft(t)
            count+=1
        else:
            t+=1
            data.remove(t)
            data.append(t)
            count+=1
        i=0
    i+=1

#print(data)
print(count)


### FIXED CODE ###

N=int(input())
data=[int(input()) for i in range(N)]
count=0
dic={}
for i in data:

    if i-1 in dic:
        num=dic.pop(i-1)
        dic.update({i:num+1})
    else:
        dic.update({i:1})
print(N-max([dic[i] for i in dic]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
### BUGGY CODE ###

n,m = map(int, input().split())
A = list(map(int, input().split()))
sumb = 0
for i in range(m):
    b,c = map(int, input().split())
    for j in range(b): A.append(c)
    sumb += b
A.sort()
print(sum(A[n+sumb:sumb-1:-1]))

### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(lambda x:list((int(x),1)), input().split()))
#print(A)
for i in range(m):
    b,c = map(int, input().split())
    A.append([c,b])
A.sort(reverse = True)
sum = 0
rem = n
for i in range(len(A)):
    sum += A[i][0] * min(A[i][1],rem)
    rem -= min(A[i][1],rem)
    if rem == 0: break
print(sum)
### BUGGY CODE ###

l = []
r = []
n,q = input().split()
N = int(n)
Q = int(q)
S = input()
for i in range(Q):
    L,R = input().split()
    l.append(int(L)-1)
    r.append(int(R)-1)
for j in range(Q):
    count = 0
    for i in range(l[j],r[j]):
        if((S[i] == "A")&(S[i+1] == "C")):
            count = count + 1
    print(count)

### FIXED CODE ###

n,q = (int(x) for x in input().split())
s = input()
l = []
r = []
for i in range(q):
    temp1,temp2 = (int(x) for x in input().split())
    l.append(temp1-1)
    r.append(temp2-1)

bb = []
bb.append(0)
# print(l)
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        bb.append(bb[i-1] + 1)
    else:
        bb.append(bb[i-1])

for i in range(q):
    print(bb[r[i]] - bb[l[i]])
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
  x = dp[i-1] + abs(h[i]-h[i-1])
  for j in range(2, K+1):
    if i-j >= 0:
      x = min(dp[i-j] + abs(h[i]-h[i-j]), x)
    else:
      pass
  dp[i] = x
print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [10 ** 9 for _ in range(N)]
dp[0] = 0
for i in range(1, N):
  x = dp[i-1] + abs(h[i]-h[i-1])
  for j in range(2, K+1):
    if i-j >= 0:
      x = min(dp[i-j] + abs(h[i]-h[i-j]), x)
    else:
      pass
  dp[i] = x
print(dp[N-1])
### BUGGY CODE ###

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

ans = 0

for i in range(len(a)):
    a[i] %= m

x = 0

for i in range(n):
    for j in range(n-i):
        x += a[i+j]
        x %= m
        if x == 0:
            ans += 1
    x = 0

print(ans)


### FIXED CODE ###

from itertools import accumulate
from collections import Counter
import math


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

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

a = [0]+a
b = list(accumulate(a))

for i in range(len(b)):
    b[i]%=m


c = Counter(b)

ans = 0

for x in c:
    if c[x]>1:
        ans += combinations_count(c[x],2)

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

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

student_turn = [0] * (n + 1)
for i in range(n):
  student_turn[a[i] - 1] = a.index(a[i]) + 1
student_turn.pop()
print(" ".join(map(str,student_turn)))

### FIXED CODE ###

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

student_turn = [0] * (n + 1)
for i in range(n):
  student_turn[a[i] - 1] = i + 1
student_turn.pop()
print(" ".join(map(str,student_turn)))
### BUGGY CODE ###

#coding: utf-8
import sys
import math
import heapq
import bisect

sys.setrecursionlimit(200000)
MOD = 10**9+7

def dfs(x,node,edge,color):
    color[x]=1
    for i in edge[x]:
        if color[i]==0:
            node[i]+=node[x]
            dfs(i,node,edge,color)
    color[x]=2

N,Q = map(int, input().split())

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*N

for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

dfs(0,node,edge,color)

for n in node:
    print(n)

### FIXED CODE ###

#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

N,Q = map(int, input().split())

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*N

for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

stack = [0]
while stack:
    s = stack.pop()
    color[s] = 1
    for t in edge[s]:
        if color[t]==0:
            stack.append(t)
            node[t] += node[s]
    color[s]=2

for n in node:
    print(n)
### BUGGY CODE ###

X, K, D = map(int, input().split())

x = X
done = False
while K:
    K -= 1
    pre = x
    if x >= 0:
        x -= D
    else:
        x += D
    if pre * x <=0:
        if K % 2 == 0:
            ans = abs(x)
        else:
            ans = abs(pre)
        done = True
        break

if not done:
    ans = abs(x)

print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())

aX = abs(X)
if aX // D >= K:
    ans = aX - K * D
else:
    if (K - (aX // D )) % 2 == 0:
        ans = aX % D
    else:
        ans = (aX % D) - D
    
print(abs(ans))
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.pop()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict,deque
    sys.setrecursionlimit(10**5+2)

    N,M=list(map(int,sys.stdin.readline().split()))
    dic=defaultdict(list)
    for i in range(M):
        A,B=list(map(int,sys.stdin.readline().split()))
        dic[A].append(B)
        dic[B].append(A)
    
    L=[-1]*(N+1)
    R=[-1]*(N+1)


    d = deque()
    d.append((1,1))
    while len(d):
        now,count=d.popleft()
        for goto in dic[now]:
            if L[goto]==-1 or count<L[goto]:
                L[goto]=count
                R[goto]=now
                d.append((goto,count+1))

    if any(x+1 for x in R[2:]):
        print('Yes')
        for x in R[2:]:
            print(x)
    else:
        print('No')
    


main()
### BUGGY CODE ###

def main():
  n=int(input())
  l=list(map(int,input().split()))
  k=[0]*n
  for i in range(1,n+1):
    k[i-1]=str(l.index(i)+1)
  print(" ".join(k))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
  n=int(input())
  l=list(map(int,input().split()))
  k=[0]*n
  for i in range(1,n+1):
    k[l[i-1]-1]=str(i)
  print(" ".join(k))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

for i in range(len(p)):
    p[i] = (p[i]+1)/2

res = -1

for i in range(N):
    if i+1 < K:
        continue
    val = sum(p[i+1-K:i+1])
    if val > res:
        res = val

print(res)


### FIXED CODE ###

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

for i in range(N):
    p[i] = (p[i]+1)/2

sum_list = [0] * N

for i in range(N):
    if i == 0:
        sum_list[i] = p[i]
    else:
        sum_list[i] = sum_list[i-1]+p[i]
res = sum_list[K-1]

for i in range(N):
    if i < K:
        continue
    if sum_list[i] - sum_list[i-K] > res:
        res = sum_list[i] - sum_list[i-K]

print(res)
### BUGGY CODE ###

import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
def dfs(u, prev, ans):
    # result : {k: (kを通ってuで終わるパスの数=kを通らないと到達できない頂点数)}, (u以下の部分木のサイズ)
    k = cs[u]
    if len(ns[u])==1 and prev in ns[u]:
        eend, ss = {k : 1}, 1
    else:
        ss = 1
        eend = defaultdict(int)
        for v in ns[u]:
            if v==prev:
                continue
            end, s = dfs(v, u, ans)
            ss += s
            tmp = s - end.get(k, 0)
            ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
            for kk,vv in end.items():
                if kk!=k:
                    eend[kk] += end[kk]
        eend[k] = ss
#     print(eend, ss, ans)
    return eend, ss
    
end, s = dfs(1, -1, ans)
for k in range(1, n+1):
    if k==cs[0]:
        continue
    tmp = s - end.get(k, 0)
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

from collections import deque

S = input()
num_of_query = int(input())
querys = []
for _ in range(num_of_query):
    # querys.append(list(input().split()))
    query = list(input().split())
    if query[0] == '1':
        S = S[::-1]
    else:
        if query[1] == '1':
            S = deque(S)
            S.appendleft(query[2])
            S = list(S)
        else:
            S = deque(S)
            S.append(query[2])
            S = list(S)


# for query in querys:
#     if query[0] == '1':
#         S = S[::-1]
#     else:
#         if query[1] == '1':
#             S = deque(S)
#             S.appendleft(query[2])
#             S = list(S)
#         else:
#             S = deque(S)
#             S.append(query[2])
#             S = list(S)

print(''.join(S))

### FIXED CODE ###

from collections import deque

S = deque(input())
num_of_query = int(input())
querys = []
is_reverse = False

for _ in range(num_of_query):
    # querys.append(list(input().split()))
    query = list(input().split())
    
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if query[1] == '1':
            if is_reverse:
                S.append(query[2])
            else:
                S.appendleft(query[2])

        else:
            if is_reverse:
                S.appendleft(query[2])
            else:
                S.append(query[2])

S = list(S)
if is_reverse:
    S = S[::-1]

# for query in querys:
#     if query[0] == '1':
#         S = S[::-1]
#     else:
#         if query[1] == '1':
#             S = deque(S)
#             S.appendleft(query[2])
#             S = list(S)
#         else:
#             S = deque(S)
#             S.append(query[2])
#             S = list(S)

print(''.join(S))
### BUGGY CODE ###

N=int(input())
p=list(map(float, input().split()))
dp=[[0]*(N+1) for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1]+=dp[i][j]*p[i]
        dp[i+1][j]+=dp[i][j]*(1-p[i])
print(sum(dp[N][N//2+1:]))

### FIXED CODE ###

N=int(input())
p=list(map(float, input().split()))
dp=[[0]*(N+1) for _ in range(N+1)]
dp[0][0]=1
for i in range(N):
    for j in range(N):
        dp[i+1][j+1]+=dp[i][j]*p[i]
        dp[i+1][j]+=dp[i][j]*(1-p[i])
print(sum(dp[N][N//2+1:]))
### BUGGY CODE ###

l,r=map(int,input().split())
if l-r+1>=2019:
  print(0)
else:
  L=[]
  R=[]
  for i in range(l,r):
    L.append(i%2019)
    R.append((i+1)%2019)
  m=2019
  for j in L:
    for k in R:
      if j!=k:
        if (j*k)%2019<m:
          m=(j*k)%2019
  print(m)


### FIXED CODE ###

import sys
l,r=map(int,input().split())

if 2018<=r-l:
  print(0)
  sys.exit()

L=l%2019
R=r%2019
m=2018

if L>R:
  print(0)
  sys.exit()

  
for i in range(L,R):
  for j in range(i+1,R+1):
    m=min((i*j)%2019,m)

print(m)
### BUGGY CODE ###

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

K = set()
K.add(S[0:3])

for i in range(3,N):   
    c = S[i]
    tmp = set()
    for k in K:
        tmp.add(k[0]+k[1]+c)
        tmp.add(k[0]+k[2]+c)
        tmp.add(k[1]+k[2]+c)
    K = K.union(tmp)

print(len(K))

### FIXED CODE ###

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

def f(n):
    n = str(n).zfill(3)
    # print(n)
    found = False
    for i in range(len(S)):
        if S[i] == n[0]:
            found = True
            break
    if found == False:
        return 0
    
    found = False
    for j in range(i+1, len(S)):
        if S[j] == n[1]:
            found = True
            break
    if found == False:
        return 0

    found = False
    for k in range(j+1, len(S)):
        if S[k] == n[2]:
            found = True
            break
    if found:
        return 1
    return 0

ans = 0
for i in range(1000):
    ans += f(i)

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

import numpy as np

# print('input >>')
N, K = map(int, (input().split()))
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()
hdiff = [h[i + 1] - h[i] for i in range(len(h) - 1)]
hdiff = np.array(hdiff)
ans = 10 ** 10
# print('hdiff: %s' % hdiff)
for i in range(N - K+1):
    # print('i %s' % i)
    # print('hdiff[i:i+K-1]: %s' % hdiff[i:i+K-1])
    ans = min(ans,np.sum(hdiff[i:i+K-1]))

# print('----------output----------')
print(ans)

### FIXED CODE ###

import numpy as np

# print('input >>')
N, K = map(int, (input().split()))
h = []
for _ in range(N):
    h.append(int(input()))

h.sort()
hdiff = [h[i + 1] - h[i] for i in range(len(h) - 1)]
hdiff = np.array(hdiff)
ans = np.sum(hdiff[0:0+K-1])
# print('hdiff: %s' % hdiff)
sum_ = np.sum(hdiff[0:0+K-1])
for i in range(1, N-K+1):
    # print('i %s' % i)
    # print('hdiff[i:i+K-1]: %s' % hdiff[i:i+K-1])]
    sum_ = sum_-hdiff[i-1]+hdiff[i+K-2]
    ans = min(ans, sum_)

# print('----------output----------')
print(ans)
### BUGGY CODE ###

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

s = [0]*(n+1)

cnt = 0

for i in range(n):
    s[i+1] = s[i] + a[i]
    if a[i] == 0:
        cnt += 1
        
import itertools
for l,r in itertools.combinations(range(1,n+1),2):
    if l >= r:
        continue
    if s[r] - s[l-1] == 0:
        cnt += 1

print(cnt)

### FIXED CODE ###

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

b = [0] + a
s = list(itertools.accumulate(b))


c = collections.Counter(s)
cm = c.most_common()
cnt = 0
for v in cm:
    if v[1] > 1:
        cnt += (v[1]*(v[1]-1) // 2)
print(cnt)
### BUGGY CODE ###

import math
a,b=map(int,input().split())
gcd=math.gcd(a,b)

def prime_factorization(n):
  i=2
  prime=[]
  while i*i<=n or n>1:
    if n%i:
      i+=1
    else:
      prime.append(i)
      while n%i==0:
        n//=i
  if n>1:
    prime.append(n)
  return prime

print(len(prime_factorization(gcd))+1)

### FIXED CODE ###

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

def prime_factorization(n):
  if n==1:
    return [1]
  else:
    i=2
    ans=[]
    k=int(n**0.5)+1
    for j in range(2,k+1):
      if n==1: break
      if n%j==0:
        n//=j
        ans.append(j)
        while n%j==0:
          n//=j
    if len(ans):
      ans.append(1)
      if n!=1:
        ans.append(n)
      return ans
    else:
      return [1,n]

A=prime_factorization(a)
B=prime_factorization(b)
#print(A)
#print(B)

print(len(set(A)&set(B)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    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
b = 0
for i in range(n):
    if a[i] == 0:
        b = 1
        print(0)
if b == 0:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); quit()
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
    if now == zan:
        print(-1)
        quit()

            


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions,time
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

st = time.time()
n = inp()
a = []
for i in range(n):
    b = inpl()
    a.append(deque(b))
zan = n*(n-1)//2
res = 0
while True:
    res += 1
    now = zan
    s = set()
    for i in range(n):
        if i in s or a[i] == deque([]): continue
        end = True
        chk = a[i][0] - 1
        if not chk in s and a[chk][0] == i+1:
            zan -= 1
            if not zan: 
                print(res); quit()
            a[i].popleft(); a[chk].popleft()
            s.add(i); s.add(chk)
        # print(res,i,chk,a)
        nnn = time.time()
    if now == zan:
        print(-1)
        quit()
    if nnn - st > 1.7:
        print(n*(n-1)//2)
        quit()
### BUGGY CODE ###

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

if n == 1:
    print(1)
    exit()

if n % 2 != 0:
    if a_list.count(0) != 1:
        print(0)
        exit()
    else:
        for i in range(2, n, 2):
            if a_list.count(i) != 2:
                print(0)
                exit()
            else:
                continue
    print(int(pow(2, (n - 1) / 2) % (pow(10, 9) + 7)))
else:
    for i in range(1, n, 2):
        if a_list.count(i) != 2:
            print(0)
            exit()
        else:
            continue
    print(int(pow(2, n / 2) % (pow(10, 9) + 7)))

### FIXED CODE ###

n = int(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

 
if n % 2 == 0:
    possible_list = {i: True for i in range(1, n, 2)}
    for k, v in a_dict.items():
        if v != 2 or k not in possible_list:
            print(0)
            exit()
else:
    possible_list = {i: True for i in range(0, n, 2)}
    if a_dict[0] != 1:
        print(0)
        exit()
    else:
        a_dict[0] = 2
        for k, v in a_dict.items():
            if v != 2 or k not in possible_list:
                print(0)
                exit()
 
print(2 ** (n // 2) % (10 ** 9 + 7))