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

S = input()
p = 10**9 + 7

N = len(S)
# dp = [[0 for _ in range(13)] for _ in range(N + 1)]
# dp[N][0] = 1 # i = N - 1のケースでうまくいくための処置

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] = (dp[r][(j + w * k) % 13] + dp[1 - r][j]) % p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])

### FIXED CODE ###

p = 10**9 + 7
S = input()
N = len(S)

dp = [[0 for _ in range(13)] for _ in range(2)]
dp[0][0] = 1 # i = N - 1のケースでうまくいくための処置
r = 0

for i in range(N - 1,  -1,  -1):  # 小さい桁から順に
    w = 1 if i == N - 1 else (w * 10) % 13 # 各桁の重み
    r = 1 - r  # dpの0行目と1行目を交互に使う
    if S[i] == '?':
        for j in range(13):
            for k in range(10): # ?の値が0, 1, ..., 9のとき
                dp[r][(j + w * k) % 13] += dp[1 - r][j]
                if dp[r][(j + w * k) % 13] >= p:
                    dp[r][(j + w * k) % 13] -= p
    else:
        k = int(S[i])
        for j in range(13):
            dp[r][(j + w * k) % 13] = dp[1 - r][j]

    dp[1 - r] = [0] * 13

print(dp[r][5])
### BUGGY CODE ###

#from operator import itemgetter
#from collections import Counter
#import heapq
N = int(input())
S = input()
#N, M = map(int, input().split())
#A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]
#C = [list(map(int, input().split())) for i in range()]
R  =[]
G  =[]
B  =[]
for i, s in enumerate(S):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)
answer = len(R)*len(G)*len(B)
hiku = 0
for r in R:
    for g in G:
        for b in B:
            if b > max(r,g)+abs(r-g):
                break
            if abs(r-g) == abs(g-b) or abs(r-b) == abs(b-g) or abs(b-r) == abs(r-g):
                hiku += 1
answer -= hiku
print(answer)



### FIXED CODE ###

N = int(input())
S = input()
#N, M = map(int, input().split())
#A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]
#C = [list(map(int, input().split())) for i in range()]
R  =[]
G  =[]
B  =[]
for i, s in enumerate(S):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)
answer = len(R)*len(G)*len(B)
hiku = 0

for i in range((N-1)//2):
    for j in range(N-i-i-2):
        if S[j] != S[j+i+1] and S[j+i+1] != S[j+i+i+2] and S[j] != S[j+i+i+2]:
            hiku += 1


answer -= hiku
print(answer)
### BUGGY CODE ###

import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

import re
def solver(N,A,Q,BC):

    for b,c in BC:
        #print(A,':',b,'->',c)
        bef = '[\s]*'+str(b)
        aft = ' '+str(c)
        #print("bef,aft=",bef,aft)
        A = re.sub(bef, aft, A)
        #A = A.replace(' '+str(b), ' '+str(c))
        #print(A)
        print(sum(map(int,A.split())))


def main():
    N = I()
    #A = LI()
    A = L()
    Q = I()
    BC = []*Q
    BC = [LI() for _ in range(Q)]

    #print("N,Q=",N,Q)
    #print("A=",A)
    #print("BC=",BC)

    solver(N,A,Q,BC)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def L(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI():return list(map(int,sys.stdin.readline().rstrip().split()))
def LS():return list(sys.stdin.readline().rstrip().split())

import collections

def solver(N,A,Q,BC):
    T = sum(map(int,A))
    #print(T)

    Nums = collections.Counter(A)
    #print(Nums)
    for b,c in BC:
        diff = c - b

        T += Nums[b] * diff
        print(T)

        Nums[c] += Nums[b]
        Nums[b] = 0


def main():
    N = I()
    A = LI()
    Q = I()
    BC = []*Q
    BC = [LI() for _ in range(Q)]

    solver(N,A,Q,BC)

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

def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    # print(N, M, Q, L, R, p, q)
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    # for s in S:
    #     print(s)
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    # for s in S2:
    #     print(s)
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = 0
        for j in range(pi, qi + 1):
            ans += (S2[j][qi] - S2[j][pi-1])
        print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    # print(N, M, Q, L, R, p, q)
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    # for s in S:
    #     print(s)
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    # for s in S2:
    #     print(s)
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = 0
        for j in range(pi, qi + 1):
            ans += (S2[j][qi] - S2[j][pi-1])
        print(ans)

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

arr = []
for _ in range(int(input())):
  arr.append(int(input()))
arr2 = arr.copy()
for k in range(len(arr)):
  arr.pop(k)
  print(max(arr))
  arr = arr2.copy()

### FIXED CODE ###

arr = []
for _ in range(int(input())):
  arr.append(int(input()))
arr2 = arr.copy()
arr2.sort()
z = arr2[-1]
zz = arr2[-2]
for k in arr:
  if k != z:
    print(z)
  else:
    print(zz)
### BUGGY CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
#print(d)
for i in range(q):
  ans=0
  for k,v in d.items():
    if k==b[i]:
      removed=d.pop(b[i])
      d[c[i]]+=removed
      break
  #print(d)
  for k,v in d.items():
    #print(ans,k,v)
    ans+=k*v
  print(ans)
  

### FIXED CODE ###

import numpy as np
from collections import Counter as C

n=int(input())
a = list(input().split())
a = [int(i) for i in a]
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
bc=np.array(bc).T
b=bc[0]
c=bc[1]

d=C(a)
d2={}
for k,v in d.items():
  d2[k]=k*v

#print(d)
ans=sum(a)
for i in range(q):
  d[c[i]]+=d[b[i]]
  ans+=(c[i]-b[i])*d[b[i]]
  d[b[i]]=0
  print(ans)
### BUGGY CODE ###

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


for i in range(Q):
    query = input().split()
    if query[0] == '1':
        S = S[::-1]
    elif query[1] == '1':
        S = query[2] + S
    else:
        S = S + query[2]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

flag = 0
for i in range(Q):
    query = input().split()
    if query[0] == '1':
        flag = flag ^ 1
    elif query[0] == '2':
        if flag == 0:
            if query[1] == '1':
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if query[1] == '1':
                S.append(query[2])
            else:
                S.appendleft(query[2])
if flag == 0:
    print(''.join(S))
else:
    # deque型はスライスで取り出せない print(''.join(S[::-1]))
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])
ans = 0
while m > 0:
    a[-1] = a[-1]//2
    m-=1
    a.sort()
print(sum(a))

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
a = sorted([int(i) for i in input().split()])
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

while m > 0:
    t = heapq.heappop(a)*(-1)//2
    heapq.heappush(a,-t)
    m-=1
print(-sum(a))
### BUGGY CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n = n%bin(n).count('1')
        c += 1
    return c

tmp = pow(2, n)
for i in range(n-1, -1, -1):
    # ibit目を反転させる # つまり2**iを引く
    tmp //= 2
    if (nx>>i)&1:
        if nx-tmp == 0:
            print(0)
            continue
        r = (nx-tmp)%(pc-1)
    else:
        r = (nx+tmp)%(pc+1)

    if r > 0:
        print(f(r) + 1)
    else:
        print(1)
    


### FIXED CODE ###

n = int(input())
X = input()
pc = X.count('1')
nx = int(X, 2)

def f(n):
    c = 0
    while n > 0:
        n %= bin(n).count('1')
        c += 1
    return c

nxp = nx%(pc+1)
nxm = nx%(pc-1) if pc > 1 else 0
for i in range(n-1, -1, -1):
    if (nx>>i)&1:
        # 2**iを引く
        if pc-1 == 0:
            print(0)
            continue
        p = pow(2, i, pc-1)
        r = (nxm-p)%(pc-1)
    else:
        # 2**iを足す
        r = (nxp+pow(2, i, pc+1))%(pc+1)

    print(f(r) + 1)
### BUGGY CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0] * n

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

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

### FIXED CODE ###

n, k = map(int,input().split())
h = list(map(int, input().split()))

dp = [0] + [float("inf")]*(n-1)

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

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

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n - 2):
    a = L[i]
    for j in range(i + 1, n - 1):
        b = L[j]
        c_min = b - a
        c_max = a + b
        if c_max > c_min + 1:
            l = L[j+1:]
            i_min = bisect.bisect_right(l, c_min)
            i_max = bisect.bisect_left(l, c_max)
            ans += i_max-i_min
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        k = bisect.bisect_left(L, L[i]+L[j])
        ans += k-1 - j
print(ans)
### BUGGY CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d: continue
        dst[nh][nw] = d
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if -1 < dst[nh][nw] <= d + 1: continue
        dst[nh][nw] = d + 1
        dq.appendleft((nh, nw, d + 1))

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

from heapq import heappop, heappush
INF = float('inf')

n, m, s, t = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n + 1)]
for u, v, a, b in edges:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(s, pay):
    """
    s: start
    pay: 0 = yen, 1 = snuuk
    """
    d = [INF] * (n + 1)
    visited = [False] * (n + 1)
    pq = []

    heappush(pq, (0, s))
    d[s] = 0
    visited[s] = True

    while pq:
        cost, x = heappop(pq)
        visited[x] = True

        for v, *c in graph[x]:
            if visited[v]:
                continue

            if d[v] > d[x] + c[pay]:
                d[v] = d[x] + c[pay]
                heappush(pq, (d[v], v))

    return d

d1 = dijkstra(s, 0)
d2 = dijkstra(t, 1)

cost = [v + w for v, w in zip(d1[1:], d2[1:])]
for i in range(n):
    print(10 ** 15 - min(cost[i:]))








### FIXED CODE ###

from heapq import heappop, heappush
INF = float('inf')

n, m, s, t = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

graph = [[] for _ in range(n + 1)]
for u, v, a, b in edges:
    graph[u].append((v, a, b))
    graph[v].append((u, a, b))

def dijkstra(s, pay):
    """
    s: start
    pay: 0 = yen, 1 = snuuk
    """
    d = [INF] * (n + 1)
    visited = [False] * (n + 1)
    pq = []

    heappush(pq, (0, s))
    d[s] = 0
    visited[s] = True

    while pq:
        cost, x = heappop(pq)
        visited[x] = True

        for v, *c in graph[x]:
            if visited[v]:
                continue

            if d[v] > d[x] + c[pay]:
                d[v] = d[x] + c[pay]
                heappush(pq, (d[v], v))

    return d

d1 = dijkstra(s, 0)
d2 = dijkstra(t, 1)

ans = []
tmp = float('inf')
for i in reversed(range(1, n + 1)):
    tmp = min(tmp, d1[i] + d2[i])
    ans.append(10 ** 15 - tmp)
    
print(*ans[::-1], sep='\n')
### BUGGY CODE ###

from math import factorial


m = 1000000007


r1, c1, r2, c2 = map(int, input().split())


def F(r, c):
    r += 1
    c += 1
    path = (factorial(r + c) % m) * pow(factorial(r) * factorial(c), m - 2, m) % m
    return path - 1


r1 -= 1
c1 -= 1

ans = F(r2, c2)
ans -= F(r1, c2)
ans -= F(r2, c1)
ans += F(r1, c1)

print(ans)



### FIXED CODE ###

m = 1000000007


r1, c1, r2, c2 = map(int, input().split())

nf = 10 ** 6 * 2 + 100
fact = [0] * (nf + 1)
fact[0] = 1
for i in range(nf):
    fact[i + 1] = fact[i] * (i + 1) % m


def F(r, c):
    path = (fact[r + c + 2] % m) * pow(fact[r + 1] * fact[c + 1], m - 2, m) % m
    return path - 1


r1 -= 1
c1 -= 1

ans = F(r2, c2)
ans -= F(r1, c2)
ans -= F(r2, c1)
ans += F(r1, c1)
ans = ans % m

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

N=int(input())
A=[int(x) for x in input().rstrip().split()]
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N=int(input())
A=[int(x) for x in input().rstrip().split()]
ans=[0 for i in range(N)]

for i in A:
  ans[i-1]+=1

for i in ans:
  print(i)
### BUGGY CODE ###

N=int(input())
ans=[]
for i in range(N):
  s=int(input())
  if s not in ans:
    ans+=[s]
  else:
    ans.remove(s)
print(len(ans))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
i=0
ans=0
while i<N:
  p=A[i]
  count=0
  for j in range(i,N):
    if A[j]==A[i]:
      count+=1
    else:
      break
  if count%2==1: ans+=1
  i+=count
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*N
for i in range(1,N):
  dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

from collections import defaultdict

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

plus_dic = defaultdict(int)
AB_lst = [list(map(int, input().split())) for _ in range(N - 1)]
AB_lst = sorted(AB_lst, key=lambda x: x[1])
PX_lst = [list(map(int, input().split())) for _ in range(Q)]

for p, x in PX_lst:
    plus_dic[p] += x

out_lst = [0] * (N + 1)
out_lst[1] = plus_dic[1]

for a, b in AB_lst:
    out_lst[b] = plus_dic[b] + out_lst[a]

print(*out_lst[1:])

### FIXED CODE ###

from collections import deque

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

connect_lst = [[] for _ in range(N + 1)]

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

query_weight = [0] * (N + 1)
for _ in range(Q):
    q, x = map(int, input().split())
    query_weight[q] += x

used = set()
dq = deque([1])
used.add(1)
ans = [0] * (N + 1)

while dq:
    node = dq.popleft()
    can = connect_lst[node]

    used.add(node)
    ans[node] += query_weight[node]

    for c in can:
        if c not in used:
            ans[c] += ans[node]
            dq.append(c)


ans = [str(w) for w in ans[1:]]
print(' '.join(ans))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
for i in range(N):
    ver.append([0,False])
 
for c in co:
    ver[c[0]-1][0] += c[1]

ver[0][1] = True

while len(kid) != 0:
    k = kid.popleft()
    if ver[k[0]-1][1] == True:
        ver[k[1]-1][0] += ver[k[0]-1][0]
        ver[k[1]-1][1] = True
    elif ver[k[1]-1][1] == True:
        ver[k[0]-1][0] += ver[k[1]-1][0]
        ver[k[0]-1][1] = True
    else:
        kid.append(k)

ans = [ver[i][0] for i in range(N)]

print(' '.join(map(str,ans)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque

N,Q = map(int,readline().split())
ki = []
for i in range(N-1):
    ki.append(list(map(int,readline().split())))
co = []
for i in range(Q):
    co.append(list(map(int,readline().split())))
 
ki.sort(key=lambda x: x[1])

kid = deque(ki)
ver = []
check = []
for i in range(N):
    ver.append(0)
    check.append(False)
 
for c in co:
    ver[c[0]-1] += c[1]

check[0] = True

kid2 = deque()

while len(kid) != 0:
    k = kid.popleft()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.append(k)

while len(kid2) != 0:
    k = kid2.pop()
    if check[k[0]-1] == True:
        ver[k[1]-1] += ver[k[0]-1]
        check[k[1]-1] = True
    elif check[k[1]-1] == True:
        ver[k[0]-1] += ver[k[1]-1]
        check[k[0]-1] = True
    else:
        kid2.appendleft(k)


print(' '.join(map(str,ver)))
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
sum = 1
flag = 1
upper = pow(10, 18)
for num in nums:
  sum = sum * num
  if flag != 0:
    if sum > upper:
      flag = 2
  if num == 0:
    flag = 0
if flag == 2:
  print(-1)
else:
  print(sum * flag)


### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
sum = 1
flag = 1
upper = pow(10, 18)
for num in nums:
  if flag == 1:
    sum = sum * num
    if sum > upper:
      flag = 2
  if num == 0:
    flag = 0
    break
if flag == 2:
  print(-1)
else:
  print(sum * flag)
### BUGGY CODE ###

def main():
    from collections import deque
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = deque()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.append([i,j])
                cnt += 1
    ans = 0
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt<h*w:
        q_ = deque()
        ans += 1
        while len(q)>0:
            b = q.pop()
            for nx in nxt:
                mv = [b[0]+nx[0],b[1]+nx[1]]
                if -1<mv[0]<h and -1<mv[1]<w:
                    if S[mv[0]][mv[1]]=='#':
                        continue
                    cnt += 1
                    S[mv[0]][mv[1]]='#'
                    q_.append(mv)
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

n=int(input())
def out(i):
  print(i,flush=True)
  s=input()
  if s=="Male":return 0
  elif s=="Female":return 1
  else:exit()
f=out(0)
ng=0
ok=n
while ng+1!=ok:
  mid=(ng+ok)//2
  if mid%2==out(mid)%2+f:ng=mid
  else:ok=mid

### FIXED CODE ###

n=int(input())
def out(i):
  print(i,flush=True)
  s=input()
  if s=="Male":return 0
  elif s=="Female":return 1
  else:exit()
f=out(0)
ng=0
ok=n
while ng+1!=ok:
  mid=(ng+ok)//2
  if (mid+f)%2==out(mid)%2:ng=mid
  else:ok=mid
### BUGGY CODE ###

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

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

if flg:
    ans = 1
    for i in range(N//2):
        ans *= 2
        ans %= 10**9 + 7
else:
    ans = 0

print(ans)


### FIXED CODE ###

from collections import Counter

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

flg = 0
if N % 2:
    if c[0] != 1:
        flg = 1
    else:
        for i in range(2, N, 2):
            if c[i] != 2:
                flg = 1
                break
else:
    for i in range(1, N, 2):
        if c[i] != 2:
            flg = 1
            break

if flg:
    ans = 0
else:
    ans = 2 ** (N//2) % (10**9+7)

print(ans)