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


import collections

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze = [list(input()) for i in range(h)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

field = [[False for i in range(w)] for j in range(h)]
field[sy][sx] = True
dx = [1,0,-1,0]
dy = [0,1,0,-1]

q = collections.deque()
q2 = collections.deque()
q.append((sy,sx))
q2.append((sy,sx))
ans = 10**9
count = 0
maze[sy][sx] = 0

def f(count):
    while q:
        s = q.popleft()
        y,x = s[0],s[1]
        count = maze[y][x]
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<=newy<h and 0<=newx<w:
                if maze[newy][newx] == ".":
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                elif maze[newy][newx] != "#" and field[newy][newx] == False:
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                field[newy][newx] = True
        for ddy in range(-2,3):
            for ddx in range(-2,3):
                newy = y+ddy
                newx = x+ddx
                if  0<=newy<h and 0<=newx<w:
                    if maze[newy][newx] == "." and field[newy][newx] == False:
                        maze[newy][newx] = count+1
                        q.append((newy,newx))

f(count)
if maze[gy][gx] != ".":
    print(maze[gy][gx])
else:
    print(-1)

  

### FIXED CODE ###

import collections

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze = [list(input()) for i in range(h)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

field = [[False for i in range(w)] for j in range(h)]
field[sy][sx] = True
dx = [1,0,-1,0]
dy = [0,1,0,-1]

q = collections.deque()
q2 = collections.deque()
q.append((sy,sx))
count = 0
maze[sy][sx] = 0

def f(count):
    while q:
        s = q.popleft()
        y,x = s[0],s[1]
        count = maze[y][x]
        for i in range(4):
            newy = y + dy[i]
            newx = x + dx[i]
            if 0<=newy<h and 0<=newx<w:
                if newy == gy and newx == gx:
                    print(count)
                    exit()
                if maze[newy][newx] == ".":
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                elif maze[newy][newx] != "#" and field[newy][newx] == False:
                    maze[newy][newx] = count
                    q.appendleft((newy,newx))
                field[newy][newx] = True
        for ddy in range(-2,3):
            for ddx in range(-2,3):
                newy = y+ddy
                newx = x+ddx
                if  0<=newy<h and 0<=newx<w:
                    if maze[newy][newx] == "." and field[newy][newx] == False:
                        maze[newy][newx] = count+1
                        q.append((newy,newx))

f(count)
if maze[gy][gx] != ".":
    print(maze[gy][gx])
else:
    print(-1)
### BUGGY CODE ###

from sys import stdin

n = (int(i) for i in input().split())

l = [int(x) for x in stdin.readline().rstrip().split()]

l.sort()

while 1 < len(l):
    for i in range(1, len(l)):
        if l[i]%l[0] == 0:
            l[i] = l[i] - l[0]
        else:
            l[i] = l[i]%l[0]
    l = [e for e in l if e != 0]
    l.sort()

print(l[0])


### FIXED CODE ###

from sys import stdin

def fun():
    n = (int(i) for i in input().split())

    l = [int(x) for x in stdin.readline().rstrip().split()]

    l = list(set(l))
    l.sort()

    while 1 < len(l):
        k = len(l)
        for i in range(1, k):
            if l[k-i]%l[0] == 0:
                l.pop(k-i)
            elif l[k-i] - l[k-i-1] == 1:
                print(1)
                return
            else:
                l[k-i] = l[k-i]%l[0]
        #l = [e for e in l if e != 0]
        l = list(set(l))
        l.sort()

        if l[0]==1:
            print(1)
            return

    print(l[0])
    return

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

N, A, B = map(int, input().split())
s = str(input())

passed = []

for i in range(N):
  if s[i] == "a" and len(passed) < A + B:
    passed.append(s[i])
    print("Yes")
  elif s[i] == "b" and len(passed) < A + B and passed.count("b") < B:
    passed.append(s[i])
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N, A, B = map(int, input().split())
s = str(input())

passed = []
count = 0
for i in range(N):
  if s[i] == "a" and len(passed) < A + B:
    passed.append(s[i])
    print("Yes")
  elif s[i] == "b" and len(passed) < A + B and count < B:
    passed.append(s[i])
    count += 1
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a_list = list(map(int, input().split()))

    vals = []
    for i in set(a_list):
        for X in [i-1, i, i+1]:
            vals.append(len([a for a in a_list if abs(X - a) <= 1]))
    print(max(vals))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    num_freq = collections.Counter(a_list)

    vals = []
    for X in set(a_list):
        v = 0
        if X in num_freq:
            v += num_freq[X]
        if X - 1 in num_freq:
            v += num_freq[X-1]
        if X + 1 in num_freq:
            v += num_freq[X+1]
        vals.append(v)
    print(max(vals))

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

from fractions import gcd
import sys
input = sys.stdin.readline

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

cnt = 1
for i in range(n):
    cnt = a[i] * cnt // gcd(a[i], cnt)

b = [cnt // a[i] for i in range(n)]
print(sum(b) % (10**9+7))


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

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

cnt = 1
for i in range(n):
    cnt = a[i] * cnt // gcd(a[i],cnt)


b = [cnt // a[i] for i in range(n)]
print(sum(b)%(10**9+7))
### BUGGY CODE ###

from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = (3*abc + ab)%mod
        ab = (3*ab + a)%mod
        a = (3*a + k)%mod
        k *= 3
print(abc%mod)



### FIXED CODE ###

from collections import Counter
mod = 10**9+7
s = input()
k = 1
a = 0
ab = 0
abc = 0
for c in s:
    if c == "A":
        a += k
    elif c == "B":
        ab += a
    elif c == "C":
        abc += ab
    else:
        abc = 3*abc + ab
        ab = 3*ab + a
        a = 3*a + k
        k *= 3
    a %= mod
    ab %= mod
    abc %= mod
    k %= mod
print(abc%mod)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
for _ in range(Q):
    l,r=map(int,input().split())
    print(S[l-1:r].count('AC'))


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
AC=[0]*N

cnt=0
for i in range(N-1):
    if S[i]+S[i+1]=='AC':
        AC[i]=cnt
        cnt+=1
        AC[i+1]=cnt
    else:
        AC[i],AC[i+1]=cnt,cnt

for _ in range(Q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
INF = 10**18
mul = 1
flg = True
for i in range(n):
  mul *= a[i]
if mul > INF:
  print(-1)
else:
  print(mul)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
INF = 10**18
cnt = 0
for i in range(n):
  if a[i] == 0:
    cnt += 1
if cnt > 0:
  print(0)
else:
  mul = 1
  flg = True
  for i in range(n):
    mul *= a[i]
    if mul > INF:
      flg = False
      break
  if flg:
    print(mul)
  else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in a:
  ans *= i

if ans > 1000000000000000000:
  ans = -1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
if 0 in a:
  ans = 0
else:
  for i in a:
    ans *= i
    if ans > 1000000000000000000:
      ans = -1
      break
print(ans)
### BUGGY CODE ###

from collections import deque

INF = 10**12

H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
wx = [2, -2, 0, 0, -1, -1, 1, 1, 1, 2, 2, -1, -2, -2, 1, 2, 2, -1, -2, -2]
wy = [0, 0, 2, -2, -1, 1, -1, 1, 2, 2, 1, -2, -2, -1, -2, -2, -1, 2, 2, 1]
maze = []

for _ in range(H):
    maze.append(list(input()))

q = deque()
d = [[INF] * W for i in range(H)]
d[sx][sy] = 0
q.append((sx, sy, 0))

while q:
    x, y, s = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s:
            d[nx][ny] = s
            q.appendleft((nx, ny, s))
    for i in range(20):
        nx = x + wx[i]
        ny = y + wy[i]
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != '#' and d[nx][ny] > s+1:
            d[nx][ny] = s + 1
            q.appendleft((nx, ny, s+1))

if d[gx][gy] == INF:
    print(-1)
else:
    print(d[gx][gy])


### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
num = []
for Q in range(q):
	l,r = map(int,input().split())
	num.append(s[l - 1:r].count('AC'))
for NUM in range(q):
	print(num[NUM])

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
r = [0 for n in range(N)]
l = [0 for n in range(N)]
cnt = 0
for s in range(N - 1):
	if S[s] == 'A':
		if S[s + 1] == 'C':
			cnt += 1
	l[s + 1] = cnt
cnt = 0
for s in range(1,N):
	if S[-s] == 'C':
		if S[-s - 1] == 'A':
			cnt += 1
	r[-s - 1] = cnt
for q in range(Q):
	L,R = map(int,input().split())
	print(cnt - l[L - 1] - r[R - 1])
### BUGGY CODE ###

k=int(input())
c=1
m='7'
if k%2==0:
    print(-1)
else:
    while True:
        if c > 1:
            m=m+'7'
        if int(m)%k==0:
            print(c)
            break
        c+=1

### FIXED CODE ###

import sys
k=int(input())
l=[]
x=7%k
if x == 0:
  print(1)
  sys.exit()
for i in range(2,k+1):
  num=(x*10+7)%k
  x=num
  l.append(num)
  if num==0:
    print(i)
    break
if 0 not in l:
  print(-1)
### BUGGY CODE ###


def main():
  n = int(input())

  dp = [1] * (n + 1)

  ans = 1
  for num in range(2, n + 1):
    dp[num] += 1
    for i in range(num, n // num + 1):
      dp[num * i] += 1 if i == num else 2

    ans += num * dp[num]

  print(ans)


main()


### FIXED CODE ###


def main():
  n = int(input())

  ans = 0
  for i in range(1, n + 1):
    y = n // i
    ans += y * (y + 1) * i // 2

  print(ans)


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
import numpy as np
N, K = map(int, raw_input().split())
R = []
for i in xrange(N):
    ia, ib = map(int, raw_input().split())
    R.extend(np.ones(ib) * ia)

print int(sorted(R)[K-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N, K = map(int, raw_input().split())
R = [0] * (10**5+10) 

for i in xrange(N):
     ia, ib = map(int, raw_input().split())
     R[ia] += ib

k = 0
c = 0
while k < K:
    c += 1
    k += R[c]
print c
### BUGGY CODE ###

def popcount(x):
    ans = 0   
    while x > 0:
        if x & 1:
            ans += 1
        x >>= 1
    return ans
              
def f(x, pc, memo):
    if (x, pc) in memo:
        return memo[(x, pc)]
    r = x % pc
    memo[(x, pc)] = r
    return r  
              
N = int(input())
X = input()   
              
x = int(X, 2) 
              
memo = {}     
pc_x = popcount(x)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
    else:     
        pc = pc_x + 1
    if pc == 0:
        print('0')
        continue
    f_x = f(x, pc, memo)
    f_res = f(1<<(N-i-1), pc, memo)
    if X[i] == '1':
        f_i = f_x - f_res
    else:     
        f_i = f_x + f_res
    f_i = (f_i + 2 * pc) % pc
    ans = 1   
    while f_i > 0:
        ans += 1
        pc = popcount(f_i)
        f_i = f(f_i, pc, memo)
    print(ans)

### FIXED CODE ###

N = int(input())
X = input()   
              
x_val = int(X, 2)
pc_x = X.count('1')
              
x_mod_pc_x_plus_1 = x_val % (pc_x + 1)
x_mod_pc_x_minus_1 = x_val % max(pc_x - 1, 1)
              
for i in range(N):
    if X[i] == '1':
        pc = pc_x - 1
        if pc == 0:
            print(0)
            continue
        val = (x_mod_pc_x_minus_1 - pow(2, N-i-1, pc)) % pc
    else:     
        pc = pc_x + 1
        val = (x_mod_pc_x_plus_1 + pow(2, N-i-1, pc)) % pc
    ans = 1   
    while val > 0:
        val %= bin(val).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
count=0
for X in range(K+1):
    for Y in range(K+1):
        for Z in range(K+1):
            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):
        Z=S-X-Y
        if 0<=Z<=K:
            count+=1
 
print (count)
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))


### FIXED CODE ###

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

answer=[0]*n
for i in range(n-1):
    answer[a[i]-1]+=1

for i in range(n):
    print(answer[i])
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(_) for _ in input().split()]

inf = 10**10
dp = [inf]*n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(n, i+k+1)):
        dp[j] = min(dp[j], dp[i]+abs(h[i]-h[j]))

print(dp[n-1])


### FIXED CODE ###

n, k = map(int, input().split())
h = [int(_) for _ in input().split()]

inf = 10**10
dp = [inf]*n

dp[0] = 0

for i in range(n):
    for j in range(i+1, min(n, i+k+1)):
        dp[j] = min(dp[j], dp[i]+abs(h[i]-h[j]))

print(dp[n-1])
### BUGGY CODE ###

s = list(input())
n = int(input())

import collections
s = collections.deque(s)
L = []
for i in range(n):
    L = (list(map(str,input())))
    #print(L)
    if len(L) >1:
        if int(L[2]) == 1:
            #print(s)
            s.appendleft(L[4])
        elif int(L[2]) == 2:
            s.append(L[4])
    
    elif len(L) ==1:
        s.reverse()
print("".join(s))

### FIXED CODE ###

from collections import deque
s = input()
s = deque(s)
n = int(input())
cnt = False
for i in range(n):
  L = input()
  if len(L) == 1:
    cnt  ^=1 
  else:
    a,b,c = L.split()
    if cnt:
      if b == "1":
        s.append(c)
      else:
        s.appendleft(c)
    else:
      if b == "1":
        s.appendleft(c)
      else:
        s.append(c)
if cnt:
    s = reversed(s)
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###

def topological_sort(V, to):
    cnt = [0]*V
    s = []
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = []
    for i in range(V):
        if cnt[i] == 0:
            Q.append(i)
    while len(Q) > 0:
        i = Q[0]
        del Q[0]
        s.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return s

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = s[j][1]
            I = j
    print(I+1)

### FIXED CODE ###

from collections import deque

def topological_sort(V, to):
    cnt = [0]*V
    for i in range(V):
        for j in to[i]:
            cnt[j] += 1
    Q = deque(i for i in range(V) if cnt[i]==0)
    res = []
    while Q:
        i = Q.popleft()
        res.append(i)
        for k in to[i]:
            cnt[k] -= 1
            if cnt[k] == 0:
                Q.append(k)
    return res

N,M = map(int,input().split())
to = [[] for i in range(N)]
From = [[] for i in range(N)]
for i in range(N-1+M):
    x, y = list(map(int,input().split()))
    to[x-1].append(y-1)
    From[y-1].append(x-1)
s = topological_sort(N, to)
s = [(s[i],i) for i in range(N)]
s.sort()
for i in range(N):
    k = -1
    I = -1
    for j in From[i]:
        if k < s[j][1]:
            k = s[j][1]
            I = j
    print(I+1)
### BUGGY CODE ###

import sys,math
N,M = map(int,input().split())
a = []
cnt = 0
ans = 1
fi = []
fi.append(1)
fi.append(1)
fi.append(1)
for i in range(3,10**5+2):
    tmp = fi[i-1]+fi[i-2]
    fi.append(tmp)
for i in range(M):
    a.append(int(input()))
for i in range(N+1):
    if i in a:
        if cnt == 0:
            print(0)
            sys.exit()
        else:
            ans *= fi[cnt]
            cnt = 0
    else:
        cnt += 1
ans *= fi[cnt]

print(ans % 1000000007)

### FIXED CODE ###

import sys,math
N,M = map(int,input().split())
a = [int(input()) for i in range(M)]
b = set(a)
dp = [0] * (N+1)
mod = 10**9+7
for i in range(N,-1,-1):
    if i in b:
        continue
    elif i == N or i == N-1:
        dp[i] = 1
    else:
        dp[i] = (dp[i+1] + dp[i+2])%mod
print(dp[0])
### BUGGY CODE ###

import numpy as np

def solve(_list,_k):
  start = 0
  _sum = -1
  for i in range(len(_list)-_k+1):
    s = np.sum(_list[i:i+_k])
    if _sum < s:
      _sum = s
      start = i

  ans = 0.
  for item in _list[start:start+_k]:
    upper = np.sum(np.arange(1, item+1))
    ans += upper / item

  return ans


if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]
  _l = np.array(_l)

  result = solve(_l, _k)
  print(result)


### FIXED CODE ###

def solve(_list,_k):
  accumulate_list = [0.]
  for i in _list:
    accumulate_list.append((i+1)/2 + accumulate_list[-1])

  ans = -1.0
  for i in range(len(accumulate_list)-_k):
    ans = max(ans, accumulate_list[i+_k]-accumulate_list[i])
  return ans

if __name__ == "__main__":
  _n, _k = map(int, input().split())
  _l = [int(i) for i in input().split()]

  result = solve(_l, _k)
  print(result)
### BUGGY CODE ###

import numpy as np

# 約数列挙(nを含む)
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)

    return divisors


N = int(input())
A = np.array(input().split(), dtype=np.int64)
A.sort()
A = A[::-1]


p0 = make_divisors(A[0])
p1 = make_divisors(A[-1])
P = p0 | p1

for p in sorted(list(P))[::-1]:
    c = 0
    for a in A:
        if a % p == 0:
            c += 1

    if c == N - 1:
        break

q = np.gcd.reduce(A)
if p > q:
    print(p)
else:
    print(q)


### FIXED CODE ###

import numpy as np

# 約数列挙(nを含む)
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n // i)

    return divisors


N = int(input())
A = np.array(input().split(), dtype=np.int64)
A.sort()
A = A[::-1]


p0 = make_divisors(A[0])
p1 = make_divisors(A[-1])
P = p0 | p1

for p in sorted(P)[::-1]:
    c = np.count_nonzero(A % p == 0)
    if c == N - 1:
        break

q = np.gcd.reduce(A)
if p > q:
    print(p)
else:
    print(q)
### BUGGY CODE ###

def wf(d):
    N = len(d)
    for k in range(N):
        for j in range(N):
            for i in range(N):
                d[j][i] = min(d[j][i], d[j][k] + d[k][i])
    return d


N, x, y = map(int, input().split())
x -= 1
y -= 1
d = [[float('inf') for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    d[i][i + 1] = 1
    d[i + 1][i] = 1

d[x][y] = 1
d[y][x] = 1

for n in range(N):
    d[n][n] = 0

d = wf(d)

cnt = {n: 0 for n in range(N)}
for i in range(N):
    for j in range(i, N):
        cnt[d[i][j]] += 1

for i in range(1, N):
    print(cnt[i])


### FIXED CODE ###

N, x, y = map(int, input().split())

cnt = {n: 0 for n in range(1, N)}
for i in range(1, N + 1):
    for j in range(i+1, N + 1):
        d1 = abs(i - j)
        d2 = 1 + min(abs(x - i) + abs(y - j), abs(x - j) + abs(y - i))
        cnt[min(d1, d2)] += 1

for k in range(1, N):
    print(cnt[k])
### BUGGY CODE ###

#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK,N,score):
    dbg(V,rK,N,score)
    # if rK == 0:
    #     db[]
    #     return score + sum(N)


    max_v = score + sum(sorted(N)[rK:])
    #LV = V[:ceil(len(V)/2)]
    RV = V[floor(len(V)/2):][::-1]



    n = []
    for i in range(min(rK,ceil(len(V)/2))):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[i+1:]
        next_rK = rK - 1 - i
        next_tmp_v = tansaku(next_V, next_rK, N+n, score+V[i])
        max_v = max(next_tmp_v , max_v)


        break

    n = []
    for i in range(    len(V)-1    ,   max(floor(len(V)/2),len(V)-1-rK),-1 ):
        
        if V[i] <= 0:
            n.append(V[i])
            continue

        next_V = V[:i]
        next_rK = rK - 1 - (len(V)-1-i)
        next_tmp_v = tansaku(next_V,next_rK,N+n,score+V[i])
        max_v = max(next_tmp_v , max_v)
        break


    return max_v

print(tansaku(V,K,[],0))






### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



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

N = int(input())
A = [int(i) for i in input().split()]

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

p = N//2
print(2**p)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = [int(i) for i in input().split()]
zz = Counter(A)

if N%2 == 0:
    for i in range(1,N,2):
        if zz[i] != 2:
            print(0)
            exit()
else:
    if zz[0] != 1:
        print(0)
        exit()
    for i in range(2,N,2):
        if zz[i] != 2:
            print(0)
            exit()

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