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

N = int(input())
A = list(map(int,input().split()))
d = N // 2
ans = []
def linking_up():
    for i in range(N):
        if i % 2 == 1:
            if A.count(i) == 2:
                ans.append('a')
            else:
                ans.append('b')
        elif i % 2 == 0 and i != 0:
            if A.count(i) == 2 and A.count(0) == 1:
                ans.append('c')
            else:
                ans.append('b')
linking_up()
if ans.count('a') == d or ans.count('c')== d:
    print(2 ** d)
else:
    print(0)
        




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
if n%2==0:
  for i in range(n):
    if a[i]!=(i//2)*2+1:
      print(0)
      exit()
  print(pow(2,n//2,mod))
else:
  for i in range(n):
    if a[i]!=((i+1)//2)*2:
      print(0)
      exit()
  print(pow(2,n//2,mod))
### BUGGY CODE ###

import sys
import numpy as np

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


def main():
    d, g = MI()
    data = np.array([LI() for _ in range(d)], np.int64)
    p = data[:, 0]
    c = data[:, 1]

    problems = np.zeros(2 ** d, np.int64)
    points = np.zeros(2 ** d, np.int64)
    for i in range(d):
        problems[1 << i : 1 << (i + 1)] = problems[: 1 << i] + p[i]
        points[1 << i : 1 << (i + 1)] = points[: 1 << i] + c[i] + 100 * (i + 1) * p[i]

    for i in range(2 ** d):
        point = points[i]
        problem = problems[i]
        while point < g:
            for j in reversed(range(d)):
                if (i >> j) & 1:
                    continue
                for _ in range(p[j]):
                    if point >= g:
                        break
                    point += 100 * (j + 1)
                    problem += 1
        problems[i] = problem

    print(problems.min())


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import math

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")


def main():
    d, g = MI()
    pc = [LI() for _ in range(d)]

    ans = inf
    for bit in range(2 << d):
        c = 0
        score = 0
        for i in range(d):
            if bit & (1 << i):
                c += pc[i][0]
                score += pc[i][0] * 100 * (i + 1) + pc[i][1]

        if score >= g:
            ans = min(ans, c)
        else:
            for i in reversed(range(d)):
                if bit & (1 << i):
                    continue
                res = math.ceil((g - score) / (100 * (i + 1)))
                if res < pc[i][0]:
                    ans = min(ans, c + res)
                break

    print(ans)


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

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))


def solve(i, m): 
    if m == 0:
        return True
    elif i >= n:
        return False
    else:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
M = list(map(int, input().split()))

table = [[-1 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != -1:
        return table[i][m]
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res
    else:
        res = solve(i + 1, m)
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for x in range(1, k + 1):
  for y in range(1, k + 1):
    for z in range(1, k + 1):
      ans += math.gcd(math.gcd(x, y), z)
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for x in range(1, k + 1):
  for y in range(1, k + 1):
    for z in range(1, k + 1):
      ans += gcd(gcd(x, y), z)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_set = set(a_list)
count_list = []

if k >= len(a_set):
    print(0)
else:
    for i in a_set:
        count = a_list.count(i)
        count_list.append(count)
    count_list.sort()
    ans = sum(count_list[:len(a_set)-k])
    print(ans)

### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline

n, k = map(int, input().split())
a_tuple = tuple(map(int, input().split()))
count_dict = defaultdict(int)

for i in a_tuple:
    count_dict[i] += 1

n = len(count_dict.keys())

if n <= k:
    print(0)
else:
    ans = sum(tuple(sorted(count_dict.values()))[:n-k])
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = []
ans = 1000000001
for i in range(n):
    h.append(int(input()))
h.sort()
for j in range(n-(k-1)):
    x = []
    if ans == 0:
        break
    for l in range(j,j+k):
        x.append(h[l])
        if ans == 0:
            break
        elif len(x) == k:
            y = x[-1]-x[0]
            if ans == 0:
                break
            elif ans > y:
                ans = y
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = []
ans = 1000000001
for i in range(n):
    h.append(int(input()))
h.sort()
for j in range(n-(k-1)):
    if ans == 0:
        break
    elif ans > h[j+k-1]-h[j]:
        ans = h[j+k-1]-h[j]
print(ans)
### BUGGY CODE ###

n,W = map(int,input().split())
w,v = [0] * n ,[0] * n
for i in range(n):
    w[i] ,v[i] = map(int,input().split())
dp=[[-1 for i in range(W + 1)] for j in range(n + 1)]


def rec(i,j):
    if dp[i][j] !=-1:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1 ,j),rec(i + 1,j -w[i]) + v[i])
    dp[i][j] =res
    return res

print(rec(0,W))

### FIXED CODE ###

n,W = map(int,input().split())
w,v = [0] * n ,[0] * n
for i in range(n):
    w[i] ,v[i] = map(int,input().split())

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)
for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from copy import deepcopy
from collections import deque
def main():
    h, n = map(int, input().split())
    a = deque()
    b = deque()
    aa = a.append
    ba = b.append
    for _ in range(n):
        numa, numb = map(int, input().split())
        aa(numa)
        ba(numb)
    dp = [10**9] * (h + 1)
    dp[0] = 0
    while a:
        dp_c = deepcopy(dp)
        at = a.popleft()
        bt = b.popleft()
        for i1 in range(h + 1):
            if i1 <= at:
                dp[i1] = min(bt, dp_c[i1])
            else:
                dp[i1] = min(dp[i1], dp[i1 - at] + bt)
    print(dp[h])

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    h, n = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(n)]

    large_num = 10**9
    dp = [large_num] * (h + 10**4 + 1)
    dp[0] = 0
    for abe in ab:
        a = abe[0]
        b = abe[1]
        for i1 in range(h + 1):
            if dp[i1 + a] > dp[i1] + b:
                dp[i1 + a] = dp[i1] + b
    r = min(dp[h:])

    print(r)

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

N=int(input())
count=[0]*(N+1)
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      n=x*x+y*y+z*z+x*y+y*z+z*x
      if(n<=N):
        count[n]+=1
for i in range(1,N+1):
  print(count[i])

### FIXED CODE ###

N=int(input())
count=[0]*(N+1)
for x in range(1,100):
  for y in range(1,100):
    for z in range(1,100):
      n=x*x+y*y+z*z+x*y+y*z+z*x
      if(n<=N):
        count[n]+=1
for i in range(1,N+1):
  print(count[i])
### BUGGY CODE ###

# coding: utf-8
#!/usr/bin/env python3

import queue

h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = queue.Queue()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.put( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while not q.empty():
    # queue の先頭を取り出す
    x, y, dist = q.get()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.put( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)



### FIXED CODE ###

# coding: utf-8
#!/usr/bin/env python3

from collections import deque

# input
h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False for _ in range(w)] for __ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

while q:
    # queue の先頭を取り出す
    x, y, cnt = q.popleft()
    # 4方向にループ
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny or is_visited[ny][nx]:
            continue

        q.append( (nx, ny, cnt+1) )
        is_visited[ny][nx] = True

print(cnt)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0

import itertools
C = list(itertools.combinations(L,3))
l = len(C)

for i in range(l):
    s = sorted(C[i])
    if s[0] + s[1] <= s[2]:
        pass
    else:
        count = count + 1

print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
C = sorted(L)
count = 0

import bisect
for i in range(N - 2):
    for  j in range(N - i - 2):
        s = C[i] + C[j + i + 1]
        t = bisect.bisect_left(C,s)
        u = t - (j + i + 1) - 1
        if u <= 0:
            pass
        else:
            count = count + u

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

from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(sum(a[l-1:r+1]))

### FIXED CODE ###

from math import sqrt
M = 10**6
p = [1 for i in range(M+1)]
p[0] = 0
p[1] = 0
for x in range(2, int(sqrt(M))+1):
    if p[x]:
        for y in range(x*x, M+1, x):
            p[y] = 0

a = [0 for i in range(M+1)]
for i in range(M):
    if i%2 != 0 and p[i] and p[(i+1)//2]:
        a[i] = 1

ans = [0 for i in range(M)]
for i in range(1, M):
    ans[i] = ans[i-1] + a[i]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(ans[r] - ans[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
P_X = []
for _ in range(M):
  p, x = map(int, input().split())
  P_X.append((p, x))
  dic[p].append(x)
for key in dic:
  dic[key] = sorted(dic[key])
for i in range(M):
  print(str(P_X[i][0]).zfill(6) + str((dic[P_X[i][0]].index(P_X[i][1]) + 1)).zfill(6))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect as bs
from collections import defaultdict
N, M = map(int, input().split())
dic = defaultdict(list)
P_X = [None] * M
for _ in range(M):
  p, x = input().split()
  p, x = int(p), int(x)
  P_X[_] = (p, x)
  dic[p].append(x)
for key in dic:
  dic[key].sort()
for i in range(M):
  print(str(P_X[i][0]).zfill(6) + str(bs.bisect_left(dic[P_X[i][0]], P_X[i][1]) + 1).zfill(6))
### BUGGY CODE ###

N, K = map(int, input().split())
P = dict()
C = dict()

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * ((K//k)-1)
                NumberOfCycle = (K%k) + k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
P = dict()
C = dict()

for i, p in enumerate(map(int, input().split())):
    P[i+1] = p
for i, c in enumerate(map(int, input().split())):
    C[i+1] = c

ans = -float("inf")
for pos in range(1, N+1):
    i = pos
    score = 0
    for k in range(1, K+1):
        i = P[i]
        score += C[i]
        ans = max(ans, score)
        if i == pos:
            if score > 0:
                lastAns = score * ((K//k)-1)
                NumberOfCycle = (K%k) + k
                lastScore = lastAns
                j = i
                for _ in range(NumberOfCycle):
                    j = P[j]
                    lastScore += C[j]
                    lastAns = max(lastAns, lastScore)
                ans = max(ans, lastAns)
            break
print(ans)
### BUGGY CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod

for i in range(1, N):
    x[i] = ((10 ** i) * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)

### FIXED CODE ###

import collections
S = input()[::-1]
N = len(S)
mod = 2019

ans = 0
x = [0] * N
x[0] = int(S[0]) % mod
ruijo = 10

for i in range(1, N):
    x[i] = (ruijo * int(S[i]) + x[i - 1]) % mod
    if x[i] % mod == 0:
        ans += 1
    ruijo *= 10
    ruijo %= mod
    
d = collections.Counter(x)

for i in d.values():
    ans += i * (i - 1) // 2
    
print(ans)
### BUGGY CODE ###

N = int(input())
i = 1
count = 0
if N <= 777777777:
    while i <= N:
        I = str(i)
        I = list(I)
        if I.count("3")>0 and I.count("5")>0 and I.count("7")>0:
            if I.count("0")+I.count("1")+I.count("2")+I.count("4")+I.count("6")+I.count("8")+I.count("9")==0:
                count+=1
                i+=2
            else:
                i+=2
        else:
            i+=2
    print(count)
else:
    print(26484)

### FIXED CODE ###

N = int(input())
def shichi(n):
    if int(n) > N:
        return 0
    ret=1 if all(n.count(c)>0 for c in "753") else 0
    for c in "753":
        ret += shichi(n+c)
    return ret
print(shichi("0"))
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


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

    l = A[0]
    for i in range(1, N):
        l = l * A[i] // gcd(l, A[i])

    print(sum([l // a for a in A]) % MOD)


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

import sys
readline = sys.stdin.readline

X,Y,Z,K = map(int,readline().split())

A = sorted(list(map(int,readline().split())),reverse = True)
B = sorted(list(map(int,readline().split())),reverse = True)
C = sorted(list(map(int,readline().split())),reverse = True)

# Aからa個、Bからb個、Cからc個選ぶ
# a * b * c >= Kとなること
# 全探索する上で、条件から外れるものを除外する

ans = []
for a in range(min(K,len(A))):
  for b in range(len(B)):
    for c in range(len(C)):
      ans.append(A[a] + B[b] + C[c])
      if a * b * c > K:
        break

ans = sorted(ans,reverse = True)
for i in range(K):
  print(ans[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=sorted(list(map(int,input().split())))[::-1]
B=sorted(list(map(int,input().split())))[::-1]
C=sorted(list(map(int,input().split())))[::-1]
ans=[]
for a in range(len(A)):
  for b in range(len(B)):
    for c in range(len(C)):
      if (a+1)*(b+1)*(c+1)>K:
        break
      ans.append(A[a]+B[b]+C[c])

ans=sorted(ans)[::-1]
for i in range(min(K,len(ans))):
  print(ans[i])
### BUGGY CODE ###

n = int(input())
h = list(map(int,input().split()))
ans = cnt = 0
for i in range(1,n):
    flag = cnt = 0
    for j in range(i,n):
        if h[j-1]>=h[j] and flag==0:
            cnt+=1
        else:
            flag = 1
    ans = max(ans,cnt)
print(ans)


### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
dif = [0]*(n-1)
ans = cnt = 0
for i in range(n-1):
    dif[i] =  h[i]-h[i+1]
for i in dif:
    if i>=0:
        cnt+=1
    else:
        ans = max(ans,cnt)
        cnt=0
print(max(ans,cnt))
### BUGGY CODE ###

from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
N = len(A)

S = [1]
for i in range(0, N):
 S.append(S[i] * A[i])

count = 0
prev = -1
for i in range(K, len(S)):
  current = S[i]//S[count]
  if prev != -1:
    if current > prev:
      print("Yes")
    else:
      print("No")
  prev = S[i]//S[count]
  count += 1 



### FIXED CODE ###

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

for i in range(N-K):
    print('Yes' if A[i] < A[i+K] else 'No')
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = []
C = []
S = []
for i in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
for j in range(Q):
    X = []
    for x in range(len(A)):
        if A[x] == B[j]:
            X.append(x)
            A[x] = ''
    for k in range(len(X)):
        A[X[k]] = C[j]
    s = sum(A)
    S.append(s)
for y in range(len(S)):
    print(S[y])

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
S = sum(A)
NUM = [0] * 100005
for a in A:
    NUM[a] += 1
for k in range(Q):
    S += (C[k]-B[k]) * (NUM[B[k]])
    NUM[C[k]] += NUM[B[k]]
    NUM[B[k]] = 0
    print(S)
### BUGGY CODE ###


# chmin can't use
# List in Python create copy by using slice

def main():
    INF = 10 ** 9
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    # memo of cost of i th avalable going range
    dp = [INF] * (N + 10)

    # condition of init
    dp[0] = 0

    for i in range(N):
        for k in range(1, K+1):
            if i + k >= len(h):continue
            if dp[i]+ abs(h[i] - h[i + k]) < dp[i + k]:
                dp[i + k] = dp[i]+abs(h[i] - h[i + k])

    print(dp[N-1])



if __name__ == "__main__":
    main()

### FIXED CODE ###


# chmin can't use
# List in Python create copy by using slice

def main():
    INF = 10 ** 9
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    # memo of cost of i th avalable going range
    dp = [INF] * (N + 10)

    # condition of init
    dp[0] = 0

    #
    for i in range(N):
        for k in range(1, K+1):
            if i + k >= len(h):break
            tmp_cost = dp[i]+ abs(h[i] - h[i + k])
            if tmp_cost < dp[i + k]:
                dp[i + k] = tmp_cost
    print(dp[N-1])

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

s=input()
l=len(s)

dp = [[0 for i in range(13)] for j in range(l+1)]
dp[0][0] = 1
#dp[i][j]=i桁目までを13で割った時、
#そのあまりがjになる場合の数

for i in range(1,l+1):
	num = s[-i]
	if num == '?':
		for j in range(10):
			tmp = int(j) * pow(10,i-1)
			tmp %= 13
			for k in range(13):
				index = (tmp + k) % 13
				dp[i][index] += dp[i-1][k]
	else:
		tmp = int(num) * pow(10,i-1)
		tmp %= 13
		for k in range(13):
			index = (tmp + k) % 13
			dp[i][index] += dp[i-1][k]
print(dp[l][5] % (pow(10,9)+7))


### 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 ###

from numpy import*
N,K,*A=map(int,open(0).read().split())
X=matrix(A,"O").reshape(N,N)
M=10**9+7
S=1
while K:S*=~K%2or X;K//=2;X*=X%M
print(sum(S)%M)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
M = 10**9+7
xs = []
for _ in range(N):
    xs.append(list(map(int, input().split())))
X = np.array(xs, dtype="object")
S = np.ones(N, dtype="object")
#Xs = [X]
for _ in range(60):
#    Xs.append(np.dot(Xs[-1],Xs[-1])%M)
    if K%2:
        S = np.dot(X, S)%M
    K = K//2
    X = np.dot(X, X)%M
S = np.array(S, dtype="int64")
r = 0
for s in S:
    r = (r + s)%M
print(r)
### BUGGY CODE ###

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


N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret+=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret+=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]
### BUGGY CODE ###

s = input()[::-1]

dp = [[0 for _ in range(13)] for _ in range(len(s))]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

L1 = range(1, len(s))
L2 = range(13)

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13for i in range(10))
        for j in mod_list:
            for k in L2:
                l = (k+j)%13
                dp[i][l] += dp[i-1][k]
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        for k in L2:
            l = (k+mod)%13
            dp[i][l] += dp[i-1][k]

print(dp[-1][5]%(10**9+7))

### FIXED CODE ###

s=input()
l=len(s)

mod=10**9+7

dp=[[0 for j in range(13)] for i in range(l)]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

for i in range(1, l):
 if s[i]=='?':
   for j in range(10):
     for k in range(13):
       dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
 else:
   for k in range(13):
     dp[i][(k*10+int(s[i]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int,input().split()))
g = 1
MOD = 10**9+7
for i in range(N):
    g = g*a[i]//fractions.gcd(g,a[i])
res = 0
for i in range(N):
    res += (g//a[i])%MOD
print(res%MOD)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)