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

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]

e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)

e.sort(reverse=True)

for i in range(k):
  print(e[i])

### FIXED CODE ###

x, y, z, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []

for e1 in a:
  for e2 in b:
    d.append(e1+e2)

d.sort(reverse=True)
d = d[:k]
e = []

for e1 in d:
  for e2 in c:
    e.append(e1+e2)
    
e.sort(reverse=True)

for i in range(k):
  print(e[i])
### BUGGY CODE ###

def gcm(a,b):
    g = max(a,b)
    s = min(a,b)
    while g % s != 0:
        g = max(a,b)
        s = min(a,b)
        g = g % s
    return s

def main():
    n, x = map(int, input().split())
    X = list(map(int, input().split()))

    for i in range(n):
        X[i] -= x
        if X[i] < 0:
            X[i] *= -1

    m = X[0]
    for c in X[1:]:
        m = gcm(c,m)

    print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def gcd(g, s):
    while g % s != 0:
        s, g = sorted([g,s])
        g = g % s
    return s

def main():
    n, x = map(int, input().split())
    X = list(map(int, input().split()))

    for i in range(n):
        X[i] -= x
        if X[i] < 0:
            X[i] *= -1

    m = X[0]
    for c in X[1:]:
        m = gcd(c,m)

    print(m)

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

#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
#visited_node=0
distance=0
for i in range(h):
    s=input()
    a=[]
    a.append(True)
    for j in range(w):
        if s[j]=="#":
            a.append(True)
            d.append((i+1,j+1))
        else:
            a.append(False)
    a.append(True)
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)
    

### FIXED CODE ###

#darker　and darker
from collections import deque
d=deque()
e=deque()
h,w=map(int,input().split())
field=[0 for i in range(h+2)]
field[0]=[True for i in range(w+2)]
distance=0
for i in range(h):
    s=input()
    a=[False for i in range(w+2)]
    a[0]=True
    for j in range(w):
        if s[j]=="#":
            a[j+1]=True
            d.append((i+1,j+1))
    a[w+1]=True
    field[i+1]=a
field[h+1]=[True for i in range(w+2)]
while d:
    while d:
        some=d.popleft()
        index1,index2=some[0],some[1]
        if field[index1-1][index2]==False:
                field[index1-1][index2]=True
                e.append((index1-1,index2))
        if field[index1+1][index2]==False:
                field[index1+1][index2]=True
                e.append((index1+1,index2))
        if field[index1][index2+1]==False:
                field[index1][index2+1]=True
                e.append((index1,index2+1))
        if  field[index1][index2-1]==False:
                field[index1][index2-1]=True
                e.append((index1,index2-1))
    distance+=1
    d=e
    e=deque()
print(distance-1)
### BUGGY CODE ###

n,m =map(int, input().split())
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
#a, b = [list(i) for i in zip(*ab)]
test = []
for i in range(1,n+1):
    check = [j[1] for j in ab if j[0] == i] + [j[0] for j in ab if j[1] == i]
    check = list(set(check))
    test.append(check)
result = 0
for j in range(len(test)):
    flag = 1
    for k in test[j]:
        if h[k-1] >= h[j]:
            flag = 0
            break
    if flag == 1:
        result += 1
print(result)

### FIXED CODE ###

#c
n,m =map(int, input().split())
h = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
a, b = [list(i) for i in zip(*ab)]
result = []
for i in ab:
    if h[i[0]-1] > h[i[1]-1]:
        result.append(i[1])
    elif h[i[1]-1] > h[i[0]-1]:
        result.append(i[0])
    else:
        result.append(i[0])
        result.append(i[1])
result = list(set(result))
print(n - len(result))
### BUGGY CODE ###

import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = ["0" for i in range(N+1)]


tmp = set()

for i in range(1, N+1):
    tmp2 = set()
    for n, k in num:
        if i - k in tmp:
            tmp2.add(dp[i-k]+str(n))
        else:
            if i == k:
                tmp2.add(str(n))

    for x in tmp2:
        x = list(x)
        x.sort(reverse=True)
        x = int("".join(x))

        dp[i] = str(max(int(dp[i]), x))
        tmp.add(i)


# print(dp)
ans = list(dp[N])
ans.sort(reverse=True)
print("".join(ans))


### FIXED CODE ###

import bisect
N, M = map(int, input().split())
A = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
num = [(i, num[i]) for i in range(10) if i in A]
num.sort(key=lambda x: x[0], reverse=True)
num.sort(key=lambda x: x[1])
dp = [0 for i in range(N+1)]
ans = 0
tmp = set()
tmp.add(0)
for i in range(1, N+1):
    for n, k in num:
        if i - k in tmp:
            dp[i] = 1 + dp[i-k]
            tmp.add(i)
            break


num.sort(reverse=True)
tmp = N
ans = []
for i in reversed(range(1, dp[N])):
    for n, k in num:
        if dp[tmp - k] == i:
            ans.append(n)
            tmp -= k
            break
for n, k in num:
    if k == tmp:
        ans.append(n)
        break

ans.sort(reverse=True)
ans = "".join(map(str, ans))
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
r = 0
for i in range(n):
    p = 0
    for j in range(i, n):
        if p & A[j] == 0:
            r += 1
            p ^= A[j]
        else:
            break
print(r)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
j = 0
for i in range(n):
    while j < n and not (s & A[j]):
        s ^= A[j]
        j += 1
    ans += j-i
    s ^= A[i]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = list(map(int, list(input())))
#print(S)
mod = 2019
mod_list = [0]
#last = 0
ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    #print(yo)
    mod_list.append(yo)
    #last = yo
    ten *= 10

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1) // 2

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = list(map(int, list(input())))
#print(S)
mod = 2019
mod_list = [0]
#last = 0
ten = 1

for num in S[::-1]:
    yo = (num * ten + mod_list[-1]) % mod
    #print(yo)
    mod_list.append(yo)
    #last = yo
    ten = (ten * 10) % mod

cnt = [0]*2019

for yo in mod_list:
    cnt[yo] += 1

ans = 0
for i in range(2019):
    ans += cnt[i] * (cnt[i]-1) // 2

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

import sys
import math
input = sys.stdin.readline

N = int(input())
S = input().strip()

s = 0
for i in range(N):
	for j in range(i+1, N):
		if S[j] == S[i]: continue
		dif = j - i
		for k in range(j+1, N):
			if S[j] == S[k] or S[k] == S[i]: continue
			if k-j == j-i: continue
			s += 1

print(s)

### FIXED CODE ###

import sys
import math
import collections
input = sys.stdin.readline

N = int(input())
S = input().strip()

cnt = collections.Counter(S)
ans = cnt['R'] * cnt['G'] * cnt['B']

for i in range(N):
	for d in range(1,N):
		j, k = i+d, i+2*d
		if k > N-1: break
		if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
			ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
idx = 0
ans = 0
while 1:
  if idx >= len(A):
    break
  elif A[idx] == idx+1:
    idx += 1
  else:
    A.pop(idx)
    ans += 1

if len(A) == 0:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

k = 1
ans = 0

if 1 not in A:
  print(-1)
  exit()

for a in A:
  if a == k:
    k += 1
  else:
    ans += 1

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

N = int(input())
A = list(map(int, input().split()))
anslist = []
for i in range(N):
    lefts = sum(A[:i])
    rights = sum(A[i:])
    anslist.append(abs(lefts - rights))
print(min(anslist))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
anslist = []
lefts = 0
rights = sum(A)
for i in range(N):
    lefts += A[i]
    rights -= A[i]
    anslist.append(abs(lefts - rights))
print(min(anslist))
### BUGGY CODE ###

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

ans=0
inf=10**9+7
flag=True
for i in range(N-1):
    if A[i]!=0:
        for j in range(i+1,N):
            temp=(A[i]*A[j])%inf
            ans+=temp
            ans%=inf
 
          
print(ans)

### FIXED CODE ###

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

ans=0
inf=10**9+7
flag=True
total=0
for i in range(N):
    total+=A[i]
    total%=inf

for i in range(N): 
    total-=A[i]
    ans+=A[i]*total
    ans%=inf    
          
print(ans)
### BUGGY CODE ###

# 解説を参考に作成

def solve():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S))]
    mod = 10 ** 9 + 7

    if S[-1] == '?':
        dp[0] = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[0][int(S[-1])] = 1

    for i, s in enumerate(S[::-1][1:], 1):
        digit = pow(10, i, 13)
        if s == '?':
            for j in range(10):
                x = (j * digit) % 13
                for k in range(13):
                    # print(s, i, j, k, x)
                    dp[i][(x + k) % 13] += dp[i - 1][k] % mod
                    # dp[i][(x + k) % 13] += pow(dp[i - 1][k], 1, mod)
        else:
            x = (int(s) * digit) % 13
            for k in range(13):
                # print(s, i, 'X', k, x)
                dp[i][(x + k) % 13] += dp[i - 1][k] % mod
                # dp[i][(x + k) % 13] += pow(dp[i - 1][k], 1, mod)
    print(dp[-1][5] % mod)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# #11254823を参考


def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    modmap = []
    for i in range(10):
        modmap.append([0] * 13)
        for j in range(13):
            k = (j * 10 + i) % 13
            modmap[i][k] = j

    # なぜ最初を1にするのか？
    # → Sの先頭に 0 を固定でつけても結果は変化しない. また付けた場合の最初の計算では余り0となる.
    # → どんなパターンでも共通の初期状態として使用できる.
    dp = [1] + [0] * 12
    for s in S:
        if s == '?':
            dp = [sum(dp[l] for l in modlist) % mod for modlist in zip(*modmap)]
        else:
            modlist = modmap[int(s)]
            dp = [dp[modlist[l]] % mod for l in range(13)]

    print(dp[5])


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

a, b = map(int, input().split())
def cf(x1,x2):
    cf=[]
    cf.append(1)
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

cf = cf(a,b)

ans = [1] * len(cf)
for i in reversed(range(1,len(cf))):
    for j in range(1,i):
        if cf[i] % cf[j] == 0:
            ans[i] = 0
            break

print(sum(ans))

### FIXED CODE ###


# -*- coding: utf-8 -*-
def cf(x1,x2):
    cf=[]
    cf.append(1)
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

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

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

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

result = factorization(gcd(a,b))
ans = len(result)
if not result[-1][0] == 1:
    ans += 1
print(ans)
### BUGGY CODE ###

A, B, N = map(int,input().split())
L = []

def floor(x):
  return (A * x // B) - A * (x // B)

L.append(floor(N))
for i in range(N):
  while B * (i + 1) - 1 < N:
    L.append(floor(B * (i + 1) - 1))

print(max(L))

### FIXED CODE ###

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

def floor(x):
  return (A * x // B) - A * (x // B)

print(floor(min(B - 1, N)))
### BUGGY CODE ###

N = list(map(int,input().split()))[0]
lis = [[] for i in range(N)]

for a_i,b_i in [ map(int,input().split()) for _ in range(N-1) ]:
	lis[a_i-1].append(b_i-1)
	lis[b_i-1].append(a_i-1)

flag = False
while True:
	flag = False

	sumsum = 0
	for x in lis:
		sumsum += sum(x)
	if sumsum == 0:
		print("Second")
		quit()

	for i in range(len(lis)):

		if flag:
			break

		if len(lis[i]) == 1:
			b = lis[i][0]
			lis[i].remove(b)
			lis[b].remove(i)
			for c in lis[b]:
				lis[c].remove(b)
				if len(lis[c]) == 0:
					print("First")
					quit()
			lis[b] = []
			flag = True

### FIXED CODE ###

N = list(map(int,input().split()))[0]
lis = [[] for i in range(N)]

for a_i,b_i in [ map(int,input().split()) for _ in range(N-1) ]:
	lis[a_i-1].append(b_i-1)
	lis[b_i-1].append(a_i-1)

while True:

	sumsum = 0
	for x in lis:
		sumsum += sum(x)
	if sumsum == 0:
		print("Second")
		quit()

	for i in range(len(lis)):

		if len(lis[i]) == 1:
			b = lis[i][0]
			lis[i].remove(b)
			lis[b].remove(i)
			for c in lis[b]:
				lis[c].remove(b)
				if len(lis[c]) == 0:
					print("First")
					quit()
			lis[b] = []
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
# points = [0 for _ in range(n)]
points = [0]*N
for i in range(Q):
  p, x = map(int, input().split())
  points[p-1] += x
  
def dfs(v, pv):
  for nv in G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

### FIXED CODE ###

#138_D
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 6)

n, q = map(int, input().split())

edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
    
def dfs(frm, cur):
    for to in edges[cur]:
        if to != frm:
            cnt[to] += cnt[cur]
            dfs(cur, to)
dfs(-1, 0)          
print(*cnt)
### BUGGY CODE ###

inf = 2019
L, R = map(int, input().split())
ans = 2018

for i in range(L, L + 2019):
    if i >= R:
        break
    for j in range(i + 1, R + 1):
        tmp = int((i * j) % inf)
        ans = min(ans, tmp)
    if ans == 0:
        break

print(ans)

### FIXED CODE ###

inf = 2019
L, R = map(int, input().split())
ans = 0
df = R - L
if df < 2019:
    L = L % inf
    R = L + df
    ans = 2019
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            tmp = int((i * j) % inf)
            ans = min(ans, tmp)

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

n,m=map(int,input().split())
s={k for k in range(1,100001)}
for i in range(m):
  l,r=map(int,input().split())
  b=set()
  for j in range(l,r+1):
    b.add(j)
  s=s&b
print(len(s))

### FIXED CODE ###

n,m = map(int,input().split())
count = 0
lmax = 0
rmin = 100000
for i in range(m):
  l,r = map(int,input().split())
  lmax = max(l,lmax)
  rmin = min(r,rmin)
print(max(rmin-lmax+1,0))
### BUGGY CODE ###

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

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

mod = 10**9+7
fact = [1]
for n in range(1, N+1):
    fact.append( fact[-1] * n % mod)
from copy import deepcopy as dcpy

def solve(S, X):
    n = len(S)

    if all( X < s for s in S):
        return fact[n] * X % mod
    if n == 1:
        return X % S[0] % mod

    ans = 0

    s_holder = [ dcpy(S) for _ in range(n)]
    for i,s in enumerate(S):
        new_x = X % s
        s_holder[i].pop(i)
        ans = (ans + solve(s_holder[i], new_x)) % mod
    return ans % mod

print( solve(S, X) % mod )
        




### FIXED CODE ###

N,X = map(int, input().split())
S = list(map(int,input().split()))

S.sort(reverse=True)
mod = 10**9+7
dp = [ [0] * (10**5+1) for _ in range(N+1)]
dp[0][X] = 1
for i in range(N):
    for j in range(0,10**5+1):
        dp[i+1][j] += dp[i][j] * (N-1-i) % mod
        dp[i+1][j% S[i]] += dp[i][j] 

        dp[i+1][j] %= mod
        dp[i+1][j%S[i]] %= mod
ans = 0
for j in range(0,10**5+1):
    ans = (ans + dp[N][j] * j % mod ) % mod

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

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
ST = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for s, t in ST:
    graph[s].append(t)


# 解説AC
# 閉路ないから後ろから見てけばOK

# ゴールまでのステップ数の期待値
def solve(block_v=None):
    step = np.zeros(N + 1)
    step[N] = 0.0
    for v in reversed(range(1, N)):
        s = 0.0
        for u in graph[v]:
            s += step[u]
        if v == block_v:
            s -= step[graph[v]].max()
            step[v] = s / (len(graph[v]) - 1) + 1
        else:
            step[v] = s / (len(graph[v])) + 1
    return step[1]


ans = solve()
for v in range(1, N):
    if len(graph[v]) > 1:
        ans = min(ans, solve(v))
print(ans)


### FIXED CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = list(map(int, sys.stdin.readline().split()))
ST = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N + 1)]
for s, t in ST:
    graph[s].append(t)

# 解説AC
# 閉路ないから後ろから見てけばOK


# dp[v][u]: u からの出口を塞いだときの、v から N までのステップ数の期待値の最小値
dp = np.full((N + 1, N + 1), IINF, dtype=float)
dp[N] = 0.0
for v in reversed(range(1, N)):
    # 塞がない
    dp[v, :] = dp[graph[v], :].sum(axis=0) / len(graph[v]) + 1
    if len(graph[v]) >= 2:
        # 塞ぐ
        s = dp[graph[v], v].sum() - dp[graph[v], v].max()
        dp[v, v] = s / (len(graph[v]) - 1) + 1
print(dp[1].min())
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  n=I()
  l=LI()

  l.sort()

  if n%2==0:
    for i in range(n):
      if (i//2)*2+1!=l[i]:
        return 0
    return pow(2,n//2)%mod

  else:
    if l[0]!=0:
      return 0
    for i in range(n-1):
      if (i//2)*2+2!=l[1:][i]:
        return 0
    return pow(2,n//2)%mod

print(main())


### FIXED CODE ###

a=1000000007
n=int(input())
l=list(map(int,input().split()))
l.sort()
if n%2==1:
  if l[0]!=0:
    print(0)
    exit()
  else:
    l.remove(0)
    sh=2
    f=0
    for i in l:
      if f==0:
        if i!=sh:
          print(0)
          exit()
        else:
          f=1
      else:
        if i!=sh:
          print(0)
          exit()
        else:
          sh+=2
          f=0
  sh=(n-1)//2
  b=1
  for i in range(sh):
    b*=2
    b%=a
  print(b)
else:
  sh=1
  f=0
  for i in l:
    if f==0:
      if i!=sh:
        print(0)
        exit()
      else:
        f=1
    else:
      if i!=sh:
        print(0)
        exit()
      else:
        sh+=2
        f=0
  sh=n//2
  b=1
  for i in range(sh):
    b*=2
    b%=a
  print(b)
### BUGGY CODE ###

n=int(input())
s=input()
preb=[0 for i in range(n)]
preg=[0 for i in range(n)]
prer=[0 for i in range(n)]
b=0; g=0; r=0
for i in range(n-1,-1,-1):
	if(s[i]=='R'):
		r+=1
	elif(s[i]=='G'):
		g+=1
	else:
		b+=1
	preb[i]=b; prer[i]=r; preg[i]=g
# print(preb)
# print(preg)
# print(prer)
l=[prer,preg,preb]
s=s.replace('R','0')
s=s.replace('G','1')
s=s.replace('B','2')
ans=0
# print(s)
for i in range(n):
	for j in range(i+1,n):
		if(s[i]!=s[j]):
			if(j+1>=n):
				continue
			ct = l[(3-int(s[i])-int(s[j]))][j+1]
			diff = j-i
			if((j+diff)<n and s[j+diff]==str(3-int(s[i])-int(s[j]))):
				ct-=1
			ans+=ct
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline
yo = input()
if(yo[-1]=='\n'):
	yo=yo[:-1]
n=int(yo)
s=input()
if(s[-1]=='\n'):
	s=s[:-1]
preb=[0 for i in range(n)]
preg=[0 for i in range(n)]
prer=[0 for i in range(n)]
b=0; g=0; r=0
for i in range(n-1,-1,-1):
	if(s[i]=='R'):
		r+=1
	elif(s[i]=='G'):
		g+=1
	else:
		b+=1
	preb[i]=b; prer[i]=r; preg[i]=g
# print(preb)
# print(preg)
# print(prer)
l=[prer,preg,preb]
s=s.replace('R','0')
s=s.replace('G','1')
s=s.replace('B','2')
ans=0
# print(s)
for i in range(n):
	for j in range(i+1,n):
		if(s[i]!=s[j]):
			if(j+1>=n):
				continue
			ct = l[(3-int(s[i])-int(s[j]))][j+1]
			diff = j-i
			if((j+diff)<n and s[j+diff]==str(3-int(s[i])-int(s[j]))):
				ct-=1
			ans+=ct
print(ans)
### BUGGY CODE ###

import sys
input =sys.stdin.readline

N=int(input().rstrip('\n'))
s = []
for _ in range(N):
  A,B = (int(x) for x in input().rstrip('\n').split())
  s.append([A,B])
m = sorted(list(set(x[1] for x in s)))
check = 0
for i in m:
  if sum([x[0] for x in s if x[1]<=i]) > i:
    check += 1
    print('No')
    break
if check == 0:
  print('Yes')

### FIXED CODE ###

import sys
input =sys.stdin.readline

N=int(input().rstrip('\n'))
s = {}
for _ in range(N):
  A,B = (int(x) for x in input().rstrip('\n').split())
  if B in s:
    s[B] += A
  else:
    s[B] = A
m = sorted(list(set(s)))
check = 0
used = 0
for i in m:
  used += s[i]
  if used > i:
    check += 1
    print('No')
    break
if check == 0:
  print('Yes')
### BUGGY CODE ###

N,P = map(int,input().split())
Z = 2
k = 1
if N==1:
    print(P)
    exit()
while(1):
    if P < (Z**N):
        break
    if P%(Z**N)==0:
        k*=Z
        P/=(Z**N)
        Z=1
    Z+=1
print(k)

### FIXED CODE ###

N,P = map(int,input().split())
r = round(P**(1/N))
for i in range(r,0,-1):
    if P%(i**N)==0:
        print(i)
        exit()