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

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
C=Counter([])
for i in range(n):
    x=lists[i]
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=lists[i]
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j]))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)
        
        
    
    
        
    
    


### FIXED CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)
### BUGGY CODE ###




N,M,Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0

def check(lst):
    global ans
    tmp = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] == lst[a-1] + c:
            tmp += d
    ans = max(ans, tmp)

def solve(idx, lst):

    if idx >= N:
        check(lst)
        return
    
    if idx <= 0:
        lo = 1
    else:
        lo = lst[idx-1]

    for i in range(lo, M+1):
        
        lst[idx] = i
        solve(idx+1, lst)


lst = [0] * N
for i in range(1, M+1):
    solve(0, lst)
    

print(ans)

### FIXED CODE ###




N,M,Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]

ans = 0

def check(lst):
    global ans
    tmp = 0
    for i in range(Q):
        a,b,c,d = abcd[i]
        if lst[b-1] == lst[a-1] + c:
            tmp += d
    ans = max(ans, tmp)

def solve(idx, lst):

    if idx >= N:
        check(lst)
        return
    
    if idx <= 0:
        lo = 1
    else:
        lo = lst[idx-1]

    for i in range(lo, M+1):
        
        lst[idx] = i
        solve(idx+1, lst)


lst = [0] * N
for i in range(1, M+1):
    solve(0, lst)
    

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

from operator import itemgetter
n,m = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = []
for i in range(m):
	b,c = map(int,input().split()) 
	b_list.append([b,c]) #b_list[i][枚数、value]

a_list.sort()
b_list.sort(reverse = True,key = itemgetter(1)) #cについてソート

now_position = 0
for i in range(m):
	if (now_position + b_list[i][0] < len(a_list)) and a_list[now_position + b_list[i][0]] < b_list[i][1]:
		del a_list[now_position:now_position + b_list[i][0]]
		a_list.insert(now_position,b_list[i][1]*b_list[i][0])
		now_position += 1
	else:
		for j in range(b_list[i][0]):
			if (now_position + j < len(a_list)) and a_list[now_position + j] < b_list[i][1]:
				a_list[now_position + j] = b_list[i][1]

			else:
				break
		break

print(sum(a_list))

### FIXED CODE ###

from operator import itemgetter
n,m = map(int,input().split())
a_list = list(map(int,input().split()))
b_list = []
for i in range(m):
	b,c = map(int,input().split()) 
	b_list.append([b,c]) #b_list[i][枚数、value]

a_list.sort()
b_list.sort(reverse = True,key = itemgetter(1)) #cについてソート
sum_list = []
now_position = 0
j = 0
for i in range(m):
	if (now_position + b_list[i][0] <= len(a_list)) and a_list[now_position + b_list[i][0]-1] < b_list[i][1]:
		sum_list.append(b_list[i][1]*b_list[i][0])
		now_position += b_list[i][0] 
	else:
		for j in range(b_list[i][0]):
			if (now_position + j < len(a_list)) and a_list[now_position + j] < b_list[i][1]:
				sum_list.append(b_list[i][1])

			else:
				break
		break
if (now_position + j <= len(a_list)-1):
	print(sum(sum_list)+sum(a_list[now_position+j:]))
else:
	print(sum(sum_list))
### BUGGY CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()
S = s()

nums = []

num = 1
prev = S[0]
first_zero = prev == '0'
for i in range(1, N):
    if prev != S[i]:
        nums.append(num)
        num = 1
        prev = S[i]
    else:
        num += 1
nums.append(num)

first = 0
if first_zero:
   first = -1

res = 0
for i in range(first, len(nums), 2):
    total = sum(nums[max(i, 0):min(i+2*K+1, len(nums))])
    if total > res:
        res = total

print(res)





### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, K = nl()
S = s()

nums = [0]

num = 1
prev = S[0]
first_zero = prev == '0'
for i in range(1, N):
    if prev != S[i]:
        nums.append(num)
        num = 1
        prev = S[i]
    else:
        num += 1
nums.append(num)

total = 0
for i in range(len(nums)):
    total += nums[i]
    nums[i] = total

first = 0
if first_zero:
   first = -1

res = 0
for i in range(first, len(nums), 2):
    total = nums[min(i+2*K+1, len(nums)-1)] - nums[max(i, 0)]
    if total > res:
        res = total

print(res)
### BUGGY CODE ###

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

def kei(b):
    ANS=0
    for i in range(N):
        ANS+=abs(A[i]-(b+i+1))
    return ANS

x=kei(A[0])
for i,j in enumerate(A):
    x=min(x,kei(j-i-1))
    
print(x)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[None]*N

for i in range(N):
    B[i]=A[i]-i-1

B.sort()

Left=0
Right=sum(B)-B[0]*N
ANS=Left+Right
#print(B)
#print(Left,Right)

for i in range(1,N):
    Left=Left+(B[i]-B[i-1])*i
    Right=Right-(B[i]-B[i-1])*(N-i)
    #print(Left,Right)

    if ANS>Left+Right:
        ANS=Left+Right

print(ANS)
### BUGGY CODE ###

L,R = (int(i) for i in input().split())

minimum = 2019
checked = set()
for i in range(L, R+1):
    a = i%2019
    if a not in checked:
        checked.add(a)
        for j in range(i+1, R+1):
            v = (i * j) % 2019
            minimum = min([v, minimum])

print(minimum)

### FIXED CODE ###

L,R = (int(i) for i in input().split())

minimum = 2019
checked = set()

start = L
end   = R+1

end2 = min(end, start+1+2019)
for i in range(start, end2):
    a = i % 2019
    if a not in checked:
        checked.add(a)
        endd = min(end, i+1+2019)
        for j in range(i+1, endd):
            v = (i * j) % 2019
            minimum = min([v, minimum])

print(minimum)
### BUGGY CODE ###

from collections import deque
import itertools
import copy

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)

### FIXED CODE ###

from collections import deque
import itertools
import copy

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]=='.' and steps[ny][nx] < 0:
            # if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)
### BUGGY CODE ###

N = int(input())
x = list(map(int, input().split()))
y = [0] * N

def shift(l, n):
    return l[n:] + l[:n]
shifted_x = shift(x, -1)
for i in range(N):
  shifted_x = shift(shifted_x, 1)
  odd = sum([n for i, n in enumerate(shifted_x) if i % 2 == 1])
  even = sum([n for i, n in enumerate(shifted_x) if i % 2 == 0])
  y[i] = even - odd


str_y = map(str, y)
output = " ".join(str_y)
print(output)

### FIXED CODE ###

N = int(input())
x = list(map(int, input().split()))
y = [0] * N

odd = sum([n for i, n in enumerate(x) if i % 2 == 1])
even = sum([n for i, n in enumerate(x) if i % 2 == 0])
y[0] = even - odd

for i in range(N-1):
  y[i+1] = 2 * x[i] - y[i]


str_y = map(str, y)
output = " ".join(str_y)
print(output)
### BUGGY CODE ###

n = int(input())

ans = 0

for i in range(1, n):
    for j in range(1, n):
        if i*j >= n:
            break
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())

ans = 0

for i in range(1, n):
    for j in range(i, n):
        if i*j >= n:
            break
        if i == j:
            ans += 1
        else:
            ans += 2

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

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        ans[i] = -1
    
que = deque()
for v in path[root]:
    que.append([root, v])
while que:
    u, V = que.popleft()
    ans[V] = u
    for v in path[V]:
        que.append([V, v])

for i in range(N):
    print(ans[i]+1)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = [-1]
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    if len(parent[v]) > 1:
        parent[v].remove(root) 
    else: que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        if len(parent[v]) > 1:
            parent[v].remove(V)
        else:
            que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)
### BUGGY CODE ###

N = int(input())
L = []
for _ in range(N):
  x, l = map(int, input().split())
  L.append([x-l, x+l])
L.sort(key=lambda x: x[1])
s, ans = -10**8, 0
while True:
  for l in L:
    if s<=l[0]:
      ans += 1
      s = l[1]
      break
  else:
    break
print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
L = []
for _ in range(N):
  x, l = map(int, input().split())
  L.append([x-l, x+l])
L.sort(key=lambda x: x[1])
L = deque(L)
s, ans = -10**8, 0
while L:
  l = deque.popleft(L)
  if s<=l[0]:
    ans += 1
    s = l[1]
print(ans)
### BUGGY CODE ###

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

for i in range(N-2):
  for j in range(i+1,N-1):
    x = L[i]+L[j]
    B = N-1
    A = j
    max_c_index = j
    while True:
      M = A + (B-A)//2
      if B-A<=1:
        if L[B] < x:
          max_c_index = B
        value += max_c_index - j
        break
      if L[M] < x:
        max_c_index = M
        A = M       
      else:
        B = M
print(value)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)

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

# import heapq
import itertools

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

data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

# scores = []
max_score = 0
for info in list(itertools.combinations(data, M)):
    beuty_score = 0
    taste_score = 0
    popular_score = 0
    for i in info:
        beuty_score += i[0]
        taste_score += i[1]
        popular_score += i[2]
    beuty_score = abs(beuty_score)
    taste_score = abs(taste_score)
    popular_score = abs(popular_score)
    if (beuty_score + taste_score + popular_score) > max_score:
        max_score = (beuty_score + taste_score + popular_score)
    # heapq.heappush(scores, -(beuty_score + taste_score + popular_score))

print(max_score)
# print(-heapq.heappop(scores))



### FIXED CODE ###

import heapq

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

data = []
for _ in range(N):
    data.append(list(map(int, input().split())))

score = [] 
scores = []
for i in range(-1, 2, 2):
    for j in range(-1, 2, 2):
        for k in range(-1, 2, 2):
            for info in data:
                heapq.heappush(score, -(i*info[0] + j*info[1] + k*info[2]))
            scores.append(-sum([heapq.heappop(score) for _ in range(M)]))
            score.clear()

print(max(scores))
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[]
for _ in range(A):
    s.append(int(input()))
t=[]
for _ in range(B):
    t.append(int(input()))
from bisect import bisect
infty=1e50
for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    if 0<i<A:
        sL=s[i-1]
        sR=s[i]
    elif i==0:
        sL=-infty
        sR=s[i]
    else:
        sL=s[-1]
        sR=infty
    
    if 0<j<B:
        tL=t[j-1]
        tR=t[j]
    elif j==0:
        tL=-infty
        tR=t[j]
    else:
        tL=t[-1]
        tR=infty
    sL=abs(sL-x)
    sR=abs(sR-x)
    tL=abs(tL-x)
    tR=abs(tR-x)

    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))




### FIXED CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[-inf]
for _ in range(A):
    s.append(int(input()))
s.append(inf)

t=[-inf]
for _ in range(B):
    t.append(int(input()))
t.append(inf)
from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))
### BUGGY CODE ###

import numpy as np
import itertools as it

N=int(input())
a_l=np.array([int(i) for i in input().split()])

def xor(i,j):
    l=max(len(str(format(i,'b'))),len(str(format(j,'b'))))
    i2=str(format(i,'b').zfill(l))
    j2=str(format(j,'b').zfill(l))
    ans=0
    for k in range(l):
        if i2[k]!=j2[k]:
            ans+=2**(l-k-1)
    return ans

sum1=0
for (i,j) in it.combinations(a_l, 2):
        sum1+=xor(i,j)
print(sum1%(7+10**9))

### FIXED CODE ###

n=int(input())
lis=list(map(lambda x:format(int(x),'b'),input().split()))
l=0
for i in range(n):
    l=max(l,len(lis[i]))

d0=[0]*60
d1=[0]*60

for i in range(n):
    lis[i]=lis[i].zfill(l)
    for j in range(l):
        if lis[i][-j-1]=='0':
            d0[j]+=1
        else:
            d1[j]+=1

ans=0
for i in range(60):
    ans+=(d0[i]*d1[i]*2**i)%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

N,M=map(int,input().split())
alist=list(map(int,input().split()))

alist.sort()
cblist = []
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
  
cblist.sort(reverse=True)
#print(alist)
#print(cblist)

for (C,B) in cblist:
  for i in range(B):
    if alist[i] < C:
      alist[i] = C
    else:
      break
  
  alist.sort()
  
#print(alist)
print(sum(alist))

### FIXED CODE ###

N,M=map(int,input().split())
alist=list(map(int,input().split()))

alist.sort()
cblist = []
for i in range(M):
  B,C=map(int,input().split())
  cblist.append((C,B))
  
cblist.sort(reverse=True)
#print(alist)
#print(cblist)

index = 0
for (C,B) in cblist:
  for i in range(index,index+B):
    if i == len(alist):
      break
    
    if alist[i] < C:
      alist[i] = C
    else:
      break
      
  index += B
  if index >= len(alist):
    break
  
#print(alist)
print(sum(alist))
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
i_list = [0] * N

A_sum = A[0]
for i in range(K-1):
    A_sum = A_sum * A[i+1]
i_list[K-1] = A_sum
cnt = 0

for k in range(K, N):
    i_list[k] = i_list[k-1] // A[cnt] * A[k]
    cnt = cnt + 1

for k in range(K-1, N-1):
    if i_list[k] < i_list[k+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K = map(int, input().split())
A = [int(i) for i in input().split()]
i_list = [0] * N

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

N,K = [int(i) for i in input().rstrip().split()]
H = [int(i) for i in input().rstrip().split()]
H = [H[0]]*K + H
C = [0]*K
for i,h in enumerate(H):
    if i < K: continue
    c = [C[-1-j]+abs(H[i-j-1]-h) for j in range(K)]
    C += [min(c)]
print(C[-1])

### FIXED CODE ###

N,K = [int(i) for i in input().rstrip().split()]
H = [int(i) for i in input().rstrip().split()]
H = [H[0]]*K + H
C = [0]*K
for i,h in enumerate(H):
    if i < K: continue
    c = [C[-1-j]+abs(H[i-j-1]-h) for j in range(K)]
    C += [min(c)]
print(C[-1])
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
ans = 0
q = []
l = len(jobs)
for i in range(m+1):
    tmp = jobs[:]
    for j in range(1, l+1):
        job = tmp[-j]
        if job[0] <= i:
            heapq.heappush(q, -jobs.pop()[1])
            l -= 1
        else:
            break
    if len(q) > 0:
        ans += -heapq.heappop(q)
print(ans)


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
jobs = [[int(x) for x in input().split()] for _ in range(n)]
jobs = sorted(jobs, key=lambda x:x[0], reverse=True)
r_jobs = list(reversed(jobs[:]))
ans = 0
q = []
cnt = 0
l = len(jobs)
for i in range(m+1):
    while cnt < l:
        if r_jobs[cnt][0] == i:
            heapq.heappush(q, -jobs.pop()[1])
            cnt += 1
        else:
            break

    if q:
        ans += -heapq.heappop(q)

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

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
  if A[i] == min(A[:i+1]):
    ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
min = 10**6
for i in range(N):
  if A[i] < min:
    ans += 1
    min = A[i]
print(ans)
### BUGGY CODE ###

import sys
i = 1
while True:
    x = sys.stdin.readline().strip()
    if x == 0:
        break
    print('Case %d: %s' % (i, x))
    i += 1

### FIXED CODE ###

import sys
i = 1
while True:
    x = sys.stdin.readline().strip()
    if x == '0':
        break
    print('Case %d: %s' % (i, x))
    i += 1
### BUGGY CODE ###

S = str(input())
mod = 10 ** 9 + 7

dp = [[0] * 13 for i in range(len(S))]
for i in range(len(S)):
  if i == 0:
    if S[i] == "?":
      for j in range(10):#"?"
        dp[i][j] = 1
    else:
      x = int(S[i])
      dp[i][x] = 1
  else:
    if S[i] == "?":
      for j in range(10):#"?"
        for k in range(13):
          now = (10 * k + j) % 13
          dp[i][now] += dp[i - 1][k]   
          dp[i][now] %= mod
    else:
      x = int(S[i])
      for k in range(13):
        now = (10 * k + x) % 13
        dp[i][now] += dp[i - 1][k]
        dp[i][now] %= mod
        
#print(dp)        
print(dp[-1][5] % mod)        
      
      


### FIXED CODE ###

S = str(input())
mod = 10 ** 9 + 7

dp = [[0] * 13 for i in range(len(S))]
for i in range(len(S)):
  if i == 0:
    if S[i] == "?":
      for j in range(10):#"?"
        dp[i][j] = 1
    else:
      x = int(S[i])
      dp[i][x] = 1
  else:
    if S[i] == "?":
      for j in range(10):#"?"
        for k in range(13):
          now = (10 * k + j) % 13
          dp[i][now] += dp[i - 1][k]   
          dp[i][now] %= mod
    else:
      x = int(S[i])
      for k in range(13):
        now = (10 * k + x) % 13
        dp[i][now] += dp[i - 1][k]
        dp[i][now] %= mod
        
#print(dp)        
print(dp[-1][5] % mod)
### BUGGY CODE ###

n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  d_p=[0]*2*n
  d_m=[0]*2*n
  m_p=[0]*2*n
  m_m=[0]*2*n
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n=int(input())
s=[ord(i)for i in input()]
t=[-1]*n
for i in range(n):
  if s[i]==68:
    t[i]=0
  elif s[i]==77:t[i]=1
  elif s[i]==67:t[i]=2

def solve(k):
  dd=mm=dm=dmc=0
  for i in range(n):
    if t[i]==0:dd+=1
    if i>=k and t[i-k]==0:dm-=mm;dd-=1
    if t[i]==1:dm+=dd;mm+=1
    if i>=k and t[i-k]==1:mm-=1
    if t[i]==2:dmc+=dm
  return dmc

q=int(input())
k=list(map(int,input().split()))
for i in k:print(solve(i))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s=input().replace('\n','')
q=int(input())
for i in range(q):
    query=input()
    if int(query[0])==1:
        s=s[::-1]
    else:
        query=query.replace('\n','')
        _,f,c=map(str,query.split())
        if int(f)==1:
            s=c+s
        else:
            s=s+c
print(s)


### FIXED CODE ###

import sys
input = sys.stdin.readline
s=input().replace('\n','')
q=int(input())
num1=0
sento=''
matsubi=''

for i in range(q):
    query=input()
    if query[0]=='1':
        num1+=1
    else:
        query=query.replace('\n','')
        _,f,c=map(str,query.split())
        if f=='1':
            if num1%2==0:
                sento=c+sento
            else:
                matsubi+=c
        else:
            if num1%2==0:
                matsubi+=c
            else:
                sento=c+sento
ans=sento+s+matsubi
if num1%2==0:
    print(ans)
else:
    print(ans[::-1])