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

MOD = 10**9+7
# dp[i][j] := Sの後ろからi桁を13で割った余りがjとなるようなものの個数
S = input()
l = len(S)
dp = [[0]*13 for _ in range(l+5)]
dp[0][0] = 1
mul = 1  
for i in range(l):
    x = S[-(i+1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= MOD
    else:
        k = int(x) # これしか選ぶ余地なし
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= MOD
    mul = mul * 10 % 13
print(dp[l][5]%MOD)


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().rstrip().split())
to = [[] for _ in range(N)]
ans = [0] * N
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for _ in range(N-1):
    a, b = map(int, input().rstrip().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().rstrip().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

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

stack = [0]
visited = [0] * N
while stack:
    v = stack.pop()
    visited[v] = 1
    for next_v in to[v]:
        if visited[next_v] == 1:
            continue
        count[next_v] += count[v]
        stack.append(next_v)
print(*count)
### BUGGY CODE ###

from sys import stdin
def main():
  n = int(input())
  a = list(map(int, input().split()))
  sum = 0
  mod = 10**9+7
  for i in range(n):
    for j in range(i+1, n):
      sum += a[i]*a[j]
  print(sum%mod)
main()



### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
S = sum(a)
S2 = sum(map(lambda x:x*x, a))
print((S*S-S2)//2%mod)
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[]
for _ in range(q):
    a.append(int(input()))
for i in range(1,n+1):
    if k-(q-a.count(i))>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
cnt=[0]*n
for _ in range(q):
    cnt[int(input())-1]+=1
for i in range(n):
    if k-(q-cnt[i])>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = input()
n = len(s)
cnt = 0
for i in range(n-2):
    for j in range(3, n+1-i):
        if int(s[i:i+j]) % 2019 == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

s = input()[::-1]
 
sum_of_digits = 0
 
cnts = [0] * 2019
 
cnts[0] = 1
 
d = 1
 
for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10
    d %= 2019
    cnts[sum_of_digits] += 1
 
ans = 0

for cnt in cnts:
    ans += cnt * (cnt - 1) // 2
 
print(ans)
### BUGGY CODE ###

#                         author:  kagemeka 
#                         created: 2019-11-09 16:39:51(JST)
### modules
## from standard library
import sys
# import collections
# import math
# import string
import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator
## from external libraries
# import scipy.special   
# import scipy.misc      
# import numpy as np 

def main():
    n, k, *x = (int(i) for i in sys.stdin.read().split())

    minimums = []
    for i in range(n - k + 1):
        cur_range = x[i: i+k]
        if cur_range[-1] <= 0:
            mi = abs(cur_range[0])
        elif cur_range[0] >= 0:
            mi = abs(cur_range[-1])
        else:
            mi = min(abs(cur_range[0]) * 2 + cur_range[-1], abs(cur_range[0]) + cur_range[-1] * 2)
        minimums.append(mi)
    
    ans = min(minimums)
    print(ans)


if __name__ == "__main__":
    # execute only if run as a script
    main()


### FIXED CODE ###

#                         author:  kagemeka 
#                         created: 2019-11-09 16:39:51(JST)
### modules
## from standard library
import sys
# import collections
# import math
# import string
import bisect
# import re
# import itertools
# import statistics
# import functools
# import operator
## from external libraries
# import scipy.special   
# import scipy.misc      
# import numpy as np 

def main():
    n, k, *x = (int(i) for i in sys.stdin.read().split())

    minimums = []
    for i in range(n - k + 1):

        left = x[i]
        right = x[i + k - 1]
        mi = min(abs(left) + abs(right - left), abs(right) + abs(left - right))
        minimums.append(mi)
    
    ans = min(minimums)
    print(ans)


if __name__ == "__main__":
    # execute only if run as a script
    main()
### BUGGY CODE ###

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
q = []
q.append((0, 0))
distance[0] = 0
while q:
    here, c = heapq.heappop(q)
    if distance[here] < c:
        continue
    for t, cost in enumerate(graph[here]):
        if distance[here] + cost < distance[t]:
            distance[t] = distance[here] + cost
            heapq.heappush(q, (t, distance[t]))
            
print(distance[n+1])

### FIXED CODE ###

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost
        graph = tuple(graph)

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
used = [False]*(n+2)
distance[0] = 0

while True:
    v = -1
    for u in range(n+2):
        if not used[u] and (v == -1 or distance[u] < distance[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    for u in range(n+2):
        distance[u] = min(distance[u], distance[v] + graph[v][u])
            
print(distance[n+1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q = map(int, input().split())
a_b = [list(map(int, input().split())) for _ in range(n-1)]
p_x = [list(map(int, input().split())) for _ in range(q)]
 
v = [[] for i in range(n)]
for e in a_b:
    v[e[0]-1].append(e[1]-1)
    v[e[1]-1].append(e[0]-1)
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
 
def dfs(p):
    for c in v[p]:
        if not c in visited:
            visited.append(c)
            score[c]+=score[p]
            if len(visited)==n:
                print(*score)
            else:
                dfs(c)
visited = [0]                
dfs(0)

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(1000000)

n,q = map(int, input().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n-1)]
p_x = [list(map(int, sys.stdin.readline().split())) for _ in range(q)]

v = [deque([]) for i in range(n)]
for e in a_b:
    v[e[0]-1]+=[e[1]-1]
    v[e[1]-1]+=[e[0]-1]
score = [0 for i in range(n)]
for e in p_x:
    score[e[0]-1]+=e[1]
def dfs(p, bp=-1):
    while v[p]:
        c =v[p].popleft()
        if c ==bp:
            continue
        #print(p, c, bp)
        score[c]+=score[p]
        dfs(c, bp=p)
visited = [0]                
dfs(0)
print(*score)
### BUGGY CODE ###

#!/usr/bin/env pypy
 
import sys
import string
def get_int(): return int(sys.stdin.readline().strip())
def get_ints(): return map(int, sys.stdin.readline().strip().split()) 
def get_list(): return list(map(int, sys.stdin.readline().strip().split())) 
def get_string(): return sys.stdin.readline().strip()
def out(data): return sys.stdout.write(str(data))
def out_list(arr): return sys.stdout.write(' '.join(str(e) for e in arr))

MAX = 10**9
MOD = 10**9 + 7

n = get_int()
arr = get_list()
q = get_int()
sum_ = sum(arr)

for _ in range(q):
	a, b = get_ints()
	if a in arr:
		sum_ += arr.count(a) * (b - a)
		arr = [b if x == a else x for x in arr]
	out(sum_)
	out('\n')




### FIXED CODE ###

#!/usr/bin/env pypy
 
import sys
import string
from collections import Counter

def get_int(): return int(sys.stdin.readline().strip())
def get_ints(): return map(int, sys.stdin.readline().strip().split()) 
def get_list(): return list(map(int, sys.stdin.readline().strip().split())) 
def get_string(): return sys.stdin.readline().strip()
def out(data): return sys.stdout.write(str(data))
def out_list(arr): return sys.stdout.write(' '.join(str(e) for e in arr))

MAX = 10**9
MOD = 10**9 + 7

n = get_int()
arr = get_list()
d = Counter(arr)
q = get_int()
sum_ = sum(arr)

for _ in range(q):
	a, b = get_ints()
	if a in d.keys() :
		sum_ += d[a] * (b - a)
		count = d[a]
		d.pop(a)
		if not d[b]:
			d[b] = count
		else:
			d[b] += count
	out(sum_)
	out('\n')
### BUGGY CODE ###

k = int(input())
c = 0
x = 0
sx = 0
while c < k:
  x+=1
  sx = str(x)
  c+=1
  for i in range(len(sx)-1):
    if abs(int(sx[i]) - int(sx[i+1])) > 1:
     c-=1
     break
print(x)

### FIXED CODE ###

kk = int(input())
if kk < 10:
    print(kk)
    exit()
 
 
dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    #dp[i+1][0] += sum(dp[i])
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]
 
a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])
 
ii = i
 
 
for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]
 
ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j
 
            break
        a += dp[i][j + k]
 
 
print(ans)
### BUGGY CODE ###

import numpy as np

#1. input
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

ans = [np.sum(np.abs(np.r_[A[:i], A[i+1:], 0] \
                                    - np.r_[0, A[:i], A[i+1:]])) for i in range(N)]
[print(ans[i]) for i in range(N)]

### FIXED CODE ###

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

#2. make distance list
a.append(0)
a.insert(0,0)
costs = []

for i in range(n+1):
    costs.append(abs(a[i+1]-a[i]))

#3. calculate each cost
total = sum(costs)
for i in range(n):
    print(total - costs[i] - costs[i+1] + abs(a[i+2]-a[i]))
### BUGGY CODE ###

a, b= map(int, input().split())
pair = []
max_len = len(str(bin(b).split("b")[1]))
if a % 2 ==0:
    start = a
    remain_before = 0
else:
    start = a+1
    remain_before = a

remain_after = 0
for i in range(start, b+1,2):
    if i+1 <= b:
        pair.append((i, i+1))
    else:
        remain_after = i

if len(pair) % 2 ==0:
    print(remain_before ^ 0 ^ remain_after)
else:
    print(remain_before ^ 1 ^ remain_after)

### FIXED CODE ###

import numpy as np
a, b= map(int, input().split())
if a % 2 ==0:
    start = a
    remain_before = 0
else:
    start = a+1
    remain_before = a

if b % 2 ==0:
    end = b-1
    remain_after = b
else:
    end = b
    remain_after = 0

if ((end+1-start) /2) %2 == 0:
    num = 0
else:
    num = 1

print(remain_before ^ num ^ remain_after)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
n,k=map(int, input().split())
h=list(map(int, input().split()))
b =sorted(h, reverse=True)
#必殺技の消費
for i in range(0,k):
    if len(b) != 0:
        b.pop(0)
    else:
        print(0)
        sys.exit()

#攻撃回数
print(sum(b))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())
h=list(map(int, input().split()))
b =sorted(h)
if k != 0:
    b = b[:-k]
#攻撃回数
print(sum(b))
### BUGGY CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
cnt = 0
last = []
head = []
for i in range(Qlen):
    if int(Query[i][0]) == 1:
        cnt +=1
    else:
        if int(Query[i][1]) == 1: #頭につける
            if cnt % 2 != 0:   #逆さ
                last = last + [Query[i][2]]
            else:
                head = [Query[i][2]] + head
        else: #けつにつける
            if cnt % 2 != 0:
                head = [Query[i][2]] + head
            else:
                last = last + [Query[i][2]]
if cnt % 2 == 0:
    print("".join(head + Slist + last))
else:
    Slist = Slist[::-1]
    head = head[::-1]
    last = last[::-1]
    print("".join(last + Slist + head))
    
# head Slist last

### FIXED CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
reverse = False
back = []
head = []

for idx, value in enumerate(Query):
    if value[0] == "1":
        reverse ^= True
        head, back = back, head
    else:
        if value[1] == "1":
            head += [value[2]]
        else:
            back += [value[2]]

if reverse == False:
    head.reverse()
    print("".join(head + Slist + back))
else:
    head.reverse()
    print("".join(head + Slist[::-1] + back))
### BUGGY CODE ###

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

ans = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        ans +=1
      elif x+y+z >S:
        break

print(ans)

### FIXED CODE ###

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

ans = 0
if K*3<S:
  print(0)
  exit()

for x in range(K, -1, -1):
  if x >S:
    continue
  for y in range(min(S-x, K), -1, -1):
    if x+y >S:
      continue
    for z in range(min(S-x-y, K), -1, -1):
      if x+y+z==S:
        ans+=1
      elif x+y+z<S:
        break

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

def main():
    import sys
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    I = []
    for i in range(len(S)-1):
        if S[i] == "A" and S[i+1] == "C":
            I.append(i)
    for j in range(Q):
        cnt = 0
        l,r = L[j]
        R = []
        for i in I:
            if l-1 <= i < r-1:
                cnt += 1
        print(cnt)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    import re
    input = sys.stdin.readline
    N,Q = list(map(int, input().split()))
    S = list(input())
    L = []
    for _ in range(Q):
        temp = list(map(int, input().split()))
        L.append(temp)
    dp = [0] * N
    for i in range(1,N):
        if S[i] == "C" and S[i-1] == "A":
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = dp[i-1]
    for j in range(Q):
        l,r = L[j]
        print(dp[r-1] - dp[l-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
p2 = [ i + 1 for i in range(n-1)]
p2.append(0)
print(sum(p2))

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0

    for a in A:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            left = bisect_left(A, d)
            right = bisect_right(A, d)
            if left != right and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(A):
    n = A[-1]
    is_nodiv = [True for _ in range(n+1)]

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a
        
    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

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

import sys
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
for i in range(M):
  tmp = A[-1]
  del A[-1]
  insort_right(A,tmp//2)
print(sum(A))

### FIXED CODE ###

import sys
import heapq
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)
  
for i in range(M):
  tmp = heapq.heappop(A)
  heapq.heappush(A,int(tmp/2))
print(sum([-a for a in A]))
### BUGGY CODE ###

N, M = map(int,input().split())
A_list = []
for i in range(M):
    A_list.append(int(input()))
if A_list:
    if A_list[0] == 1:
        Dp_list = [1,0]
    else:
        Dp_list = [1,1]
else:
    Dp_list = [1,1]
if N != 1:
    for i in range(2, N + 1):
        if i not in A_list:
            Dp_list.append(Dp_list[i-2] + Dp_list[i-1])
        elif i in A_list and i-1 in A_list:
            Dp_list = [0] * (N + 1)
            break
        else:
            Dp_list.append(0)
        if Dp_list[i] > 1000000007:
            Dp_list[i] -= 1000000007
    print(Dp_list[N]%1000000007)
else:
    print(1)

### FIXED CODE ###

N, M = map(int,input().split())
A_list = set([int(input()) for _ in range(M)])
Dp_list = [0] * (N+1)
Dp_list[0] = 1

if 1 in A_list:
    Dp_list[1] = 0
else:
    Dp_list[1] = 1

if N != 1:
    for i in range(2, N + 1):
        if i in A_list:
            continue

        Dp_list[i] = Dp_list[i-2] + Dp_list[i-1]
        Dp_list[i] %= 1000000007
    print(Dp_list[N])
else:
    print(1)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def binary_search(a, key, low, high):
    ok = low
    ng = high
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if a[mid] < key:
            ok = mid
        else:
            ng = mid
    return ok


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

    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            x = binary_search(L, L[a] + L[b], low=b, high=N)
            ans += (x - b)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


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

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


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

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

mem = [-1 for i in range(n+1)]
def countd(y):
  if mem[y] == -1:
    mem[y] = d.count(y)
  return mem[y]

if d[0] != 0:
  print(0)
  exit()

count = 1
for i in range(n-1):
  x = d[i+1]
  if x == 0:
    print(0)
    exit()
  if x == 1:
    continue
  count = count * countd(x-1)
  count = count % 998244353

print(count)


### FIXED CODE ###

from collections import Counter

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

mem = Counter(d)

if d[0] != 0 or mem[0] != 1:
  print(0)
  exit()

count = 1
for i in range(max(d)):
  count = count * mem[i] ** mem[i+1]
  count = count % 998244353

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n, m, l = map(int, input().split())
    d = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    dl = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        d[i][i] = 0

    for i in range(n):
        for j in range(i+1, n):
            if i != j and d[i][j] <= l:
                dl[i][j] = 1
                dl[j][i] = 1
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dl[i][j] > dl[i][k] + dl[k][j]:
                    dl[i][j] = dl[i][k] + dl[k][j]
    
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if dl[s-1][t-1] == float("inf"):
            print(-1)
        else:
            print(dl[s-1][t-1] - 1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n, m, l = map(int, input().split())
    d = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for _ in range(m):
        a, b, c = map(int, input().split())
        d[a-1][b-1] = c
        d[b-1][a-1] = c
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
    
    dl = [[float("inf") for _ in range(n)] for _ in range(n)]
    for i in range(n):
        d[i][i] = 0

    for i in range(n):
        for j in range(i+1, n):
            if i != j and d[i][j] <= l:
                dl[i][j] = 1
                dl[j][i] = 1
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dl[i][j] > dl[i][k] + dl[k][j]:
                    dl[i][j] = dl[i][k] + dl[k][j]
    
    q = int(input())
    for _ in range(q):
        s, t = map(int, input().split())
        if dl[s-1][t-1] == float("inf"):
            print(-1)
        else:
            print(dl[s-1][t-1] - 1)


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

n = int(input())
a = list(map(int,input().split()))
flag = True
if n%2==0:
  if a.count(0)>0:
    flag=False
  else:
    for i in range(n):
      if a.count(a[i])!=2:
        flag=False
else:
  if a.count(0)!=1:
    flag=False
  else:
    a.pop(a.index(0))
    for i in range(n-1):
      if a.count(a[i])!=2:
        flag=False

if flag==True:
    print((2**(n//2))%(10**9+7))
else:
  print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
A = list(set(a))
flag = True
if n%2==0:
  if a.count(0)>0 or len(A)!=len(a)//2:
    flag=False
else:
  if a.count(0)!=1 or len(A)!=len(a)//2+1:
    flag=False
if flag==True:
    print((2**(n//2))%(10**9+7))
else:
  print(0)