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

from collections import defaultdict
import math

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()

f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')

### FIXED CODE ###

from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')
### BUGGY CODE ###

from collections import defaultdict

tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

edge = defaultdict(list)
fixed = [False] * (n + 1)
fixed[1] = True
point = [0] * (n + 1)

for i in range(1, n):
  tmp = list(map(int, (input().split())))
  edge[tmp[0]].append(tmp[1])
  edge[tmp[1]].append(tmp[0])

for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]

que = []
for i in edge[1]:
  que.append(i)
  
while len(que) != 0:
  cur = que.pop()
  for i in edge[cur]:
    if fixed[i] == 1:
      point[cur] += point[i]
    else:
      que.append(i)
  fixed[cur] = True

for i in range(1, n+1):
  print (point[i], end=" ")

### FIXED CODE ###

tmp = list(map(int, (input().split())))
n = tmp[0]
q = tmp[1]

#edge = defaultdict(list)
edge = [[] for i in range(n+1)]
fixed = [False] * (n + 1)
fixed[1] = True
point = [0] * (n + 1)

for i in range(1, n):
  tmp = list(map(int, (input().split())))
  edge[tmp[0]].append(tmp[1])
  edge[tmp[1]].append(tmp[0])

for i in range(1, q+1):
  tmp = list(map(int, (input().split())))
  point[tmp[0]] += tmp[1]

que = []
que += edge[1]
frm = 1

while len(que) != 0:
  cur = que.pop()
  for i in edge[cur]:
    if fixed[i]:
      point[cur] += point[i]
    else:
      que.append(i)
  fixed[cur] = True

for i in range(1, n+1):
  print (point[i], end=" ")
### BUGGY CODE ###

s = input()
q = int(input())
hanten = 0
check = 0
for i in range(q):
    l = list(map(str, input().split()))
    if l[0] == "1":
        hanten += 1
        check += 1
    else:
        if l[1] == "1":
            if check%2 == 0:
                s = l[2] + s
            else:
                s = s + l[2]
        else:
            if check%2 == 0:
                s = s + l[2]
            else:
                s = l[2] + s

if hanten%2 == 1:
    s = s[::-1]

print(s)

### FIXED CODE ###

s = input()
q = int(input())
hanten = True
atm = ""
kts = ""
for i in range(q):
    l = input().split()
    if l[0] == "1":
        hanten = not hanten
    else:
        if l[1] == "1":
            if hanten:
                atm = l[2] + atm
            else:
                kts = kts + l[2]
        else:
            if hanten:
                kts = kts + l[2]
            else:
                atm = l[2] + atm

ans = atm + s + kts
if hanten == False:
    print(ans[::-1])
else:
    print(ans)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
ans=0
for i in range(n):
  c=math.floor(a*(i+1)/b)-a*math.floor((i+1)/b)
  ans=max(c,ans)
print(ans)

### FIXED CODE ###

a,b,n=map(int,input().split())
print(a*min(n,b-1)//b-a*(min(b-1,n)//b))
### BUGGY CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)
### BUGGY CODE ###

X = int(input())
A=0
B=0
while(True):
  while(True):
    if (A**5) - (B**5) == X:
      print("{} {}".format(A,B))
      exit()
    elif ((-1*A)**5) - (B**5) == X:
      print("{} {}".format(-1*A,B))
      exit()
    elif (A**5) - ((-1*B)**5) == X:
      print("{} {}".format(A,-1*B))
      exit()   
    elif ((-1*A)**5) - ((-1*B)**5) == X:
      print("{} {}".format(-1*A,-1*B))
      exit()
    else:
      B += 1
  A += 1

### FIXED CODE ###

X = int(input())
for A in range(130):
  for B in range(130):
    if (A**5) - (B**5) == X:
      print("{} {}".format(A,B))
      exit()
    elif ((-1*A)**5) - (B**5) == X:
      print("{} {}".format(-1*A,B))
      exit()
    elif (A**5) - ((-1*B)**5) == X:
      print("{} {}".format(A,-1*B))
      exit()   
    elif ((-1*A)**5) - ((-1*B)**5) == X:
      print("{} {}".format(-1*A,-1*B))
      exit()
### BUGGY CODE ###

import sys
from fractions import gcd
import bisect

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]



n, m = na()
a = na()
a.sort()

bc = s(m)
bc.sort(key=lambda x:x[1],reverse=True)


for i in range(m):
    for j in range(bc[i][0]):
        c_i = bc[i][1]
        if a[0] < c_i:
            a.pop(0)
            inid = bisect.bisect_left(a, c_i)
            a.insert(inid, c_i)
        else:
            break

print(sum(a))

### FIXED CODE ###

import sys
import math
import numpy as np
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
a = na()
bc = []

for _ in range(m):
    bci = na()
    bc.append(bci)

bc.sort(key=lambda x:x[1], reverse=True)
#print(bc)

bi, ci = bc[0][0], bc[0][1]
i = 0
for _ in range(n):
    if bi != 0:
        bi -= 1
        a.append(ci)
    else:
        i += 1
        if i > (m - 1):
            break
        else:
            bi, ci = bc[i][0], bc[i][1]
            bi -= 1
            a.append(ci)

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

S = input()
texts = ["dream", "dreamer", "erase", "eraser"]
T = [""]
max_count = len(S) // 5 + 1

match = False
count = 0
while count < max_count:
    if S in T:
        match = True
        break
    for i in range(len(T)):
        t = T.pop(0)
        for j in texts:
            T.append(t+j)
    count += 1

if match:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()
S_rvs = S[::-1]
texts = ["maerd", "remaerd", "esare", "resare"]

match = True
while len(S_rvs) > 0:
    if (S_rvs[0:5] == "maerd") or (S_rvs[0:5] == "esare"):
        S_rvs = S_rvs[5:]
    elif S_rvs[0:6] == "resare":
        S_rvs = S_rvs[6:]
    elif S_rvs[0:7] == "remaerd":
        S_rvs = S_rvs[7:]
    else:
        match = False
        break

if match:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import math
k=int(input())

sum_num=0
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      s=math.gcd(i,math.gcd(j,l))
      sum_num+=s
      
print(sum_num)

### FIXED CODE ###

import math
k=int(input())

sum_num=0
for i in range(1,k+1):
  for j in range(1,k+1):
    tmp=math.gcd(j,i)
    for l in range(1,k+1):
      s=math.gcd(l,tmp)
      sum_num+=s
      
print(sum_num)
### BUGGY CODE ###

def main():
    import heapq
    hpop=heapq.heappop
    hpush=heapq.heappush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    h2 = []
    h2a=h2.append
    heapq.heapify(h)
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i=-i
        temp = i-a[j]
        sho=temp//(b[j-1]+b[(j+1)%n])
        if  sho==0:
            h2a((i, j))
            continue
        cnt += sho
        b[j] -= (b[j-1]+b[(j+1)%n])*sho
        hpush(h, (-b[j], j))
    h2.sort(key=lambda x: x[1])
    for i in range(n):
        if a[i] != h2[i][0]:
            print(-1)
            return 0
    print(cnt)


main()

### FIXED CODE ###

def main():
    from heapq import heappop as hpop
    from heapq import heappush as hpush
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    h = []
    for i in range(n):
        hpush(h, (-b[i], i))
    cnt = 0
    while h:
        i, j = hpop(h)
        i = -i
        jj = (j+1) % n
        temp = i-a[j]
        temp2 = b[j-1]+b[jj]
        sho = temp//temp2
        if sho == 0:
            if temp:
                print(-1)
                return 0
            continue
        cnt += sho
        b[j] -= temp2*sho
        hpush(h, (-b[j], j))
    print(cnt)
main()
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans=sum(A)
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  #Bの数だけ（C-B)足す、BはCに置き換わるのでLB＝０になおす。
  L[C]+=L[B]
  ans+=L[B]*(C-B)
  L[B]=0
  print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans+=a
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)
### BUGGY CODE ###

h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            p.append([x+j-1,y+k-1])
p.sort()
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
        if p[i]==p[i+1]:
            f+=1
        else:
            ans[f]+=1
            f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,n=map(int,input().split())
z=(h-2)*(w-2)
p=[]
for i in range(n):
    x,y=map(int,input().split())
    for j in range(3):
        for k in range(3):
            p.append([x+j-1,y+k-1])
p.sort(key=lambda x:(10**10)*x[0]+x[1])
n=len(p)
p.append([10**20,10**20])
ans=[0]*10
f=1
for i in range(n):
    if 2<=p[i][0]<=h-1 and 2<=p[i][1]<=w-1:
        if p[i]==p[i+1]:
            f+=1
        else:
            ans[f]+=1
            f=1
ans[0]=z-sum(ans)
for i in ans:
    print(i)
### BUGGY CODE ###

L,R = map(int,input().split())
if (L-R >= 2019):
  print(0)
else:
  res = 2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      res = min(res,(i*j)%2019)
print(res)

### FIXED CODE ###

L,R = map(int,input().split())
if (R-L >= 2019):
  print(0)
else:
  res = 2019
  for i in range(L,R):
    for j in range(i+1,R+1):
      res = min(res,(i*j)%2019)
  print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


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

    ans = 0
    for i in range(N-1):
        for j in range(i+1, N):
            ans += A[i]*A[j]
            ans %= MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

MOD = 10**9+7


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

    ans = 0
    t = 0
    for i in reversed(range(N-1)):
        t += A[i+1]
        t %= MOD
        ans += t * A[i]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
### BUGGY CODE ###

def isPrime(N, arr):
	if N == 1:
		return True
	for i, x in enumerate(arr):
		if x > 1 and N % x == 0:
			return False
	return True

def q_D(A, B):
	target = A
	another = B
	if A > B:
		target = B
		another = A
	yaku = []
	if target == 1:
		yaku.append(1)
	for i in range(int(target/2)):
		x = i + 1
		if target % x == 0 and another % x == 0:
			if isPrime(x, yaku):
				yaku.append(x)
	print(len(yaku))

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


### FIXED CODE ###

# D - Disjoint Set of Common Divisors
A, B = map(int, input().split())

from fractions import gcd

# nの素数判定
def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# nの約数列挙
def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass #sortされていない

ans = 0
gcd1 = gcd(A, B)
for i in divisor(gcd1):
    if is_prime(i):
        ans += 1

print(ans+1)
### BUGGY CODE ###

import math
N = int(input())
z = 0
for a in range(N):
    d = math.floor(N/(a+1))
    e = min(a,d)
    for b in range(e):
        c = N - (a+1)*(b+1)
        if c > 0:
            z = z+2
        else:
            pass
    f = N - (a+1)*(a+1)
    if f > 0:
        z = z+1
    else:
        pass
print(z)

### FIXED CODE ###

import math
N = int(input())
z = 0
for a in range(N):
    for b in range(min(a,math.floor(N/(a+1)))):
        if N - (a+1)*(b+1) > 0:
            z = z+2
        else:
            pass
    if N - (a+1)*(a+1) > 0:
        z = z+1
    else:
        pass
print(z)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
for i in range(10**18):
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l[-1]

loop = len(l[l.index(last):-1])
first = l.index(last)
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]

for i in range(n):
  l.append(a[l[i]-1])
p = l.index(l[n])
#print(p,l[n])
if k<=n:
  print(l[k])
else:
  x = (k-n+1)%(n-p)
  if x ==0:
    x += (n-p)
    print(l[x-1])
  else:
    print(l[x+p-1])
### BUGGY CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)
### BUGGY CODE ###

N=int(input())

l=0
r=N

print(l,flush=True)
bstate=input()

if state!="Vacant":
    while True:
        
        c=int((l+r)/2)+1
        #print(c,l,r)
        print(c,flush=True)
        state=input()
        if state=="Vacant":
            break
        
        if state==bstate:
            l=c
        else:
            r=c



### FIXED CODE ###



N=int(input())

l=0
r=N

print(l,flush=True)
bstate=input()

if bstate!="Vacant":
    while True:
        #c=int((l+r)/2)
        L=int((r-l)/2)
        if (L%2)==0:
            L-=1
        c=l+L
        c=max(l+1,c)
        c=min(r-1,c)
        #print(c,l,r)
        print(c,flush=True)
        state=input()
        if state=="Vacant":
            break

        if state!=bstate:
            l=c
        else:
            r=c

        bstate=state
### BUGGY CODE ###

s = input()
w_count = s.count('W')

result = 0
for i in range(len(s)):
  if s[i] == 'W':
    result += s[0:i].count('B')

print(result)

### FIXED CODE ###

s = input()
b_count = s.count('B')
shoki = 0
for i in range(len(s)):
  if s[i] == 'B':
    shoki += i
saigo = sum(range(len(s) - b_count,len(s)))
print(saigo-shoki)
### BUGGY CODE ###

A, B = list(map(int, input().split()))
K = 0
for i in range(1, max(A, B)):
  if abs(A-i) == abs(B-i):
    K = i

if K:
  print(K)
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

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

if A%2 != B%2:
  print('IMPOSSIBLE')
else:
  print(int((A+B)/2))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    mp = [0] * (H + 1)
    for i in range(1, len(mp)):
        ml = []
        for j in range(N):
            if i - A[j] < 0:
                ml.append(mp[0] + B[j])
            else:
                ml.append(mp[i - A[j]] + B[j])
        mp[i] = min(ml)
    print(mp[-1])   


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    mp = [0] * (H + 1)
    for i in range(1, len(mp)):
        ml = [0 for j in range(N)]
        for j in range(N):
            if i - A[j] < 0:
                ml[j] = mp[0] + B[j]
            else:
                ml[j] = mp[i - A[j]] + B[j]
        mp[i] = min(ml)
    print(mp[-1])   


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

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

import sys,heapq,math,resource
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  #resource.setrlimit(RLIMIT_STACK, (128*1024*1024,hard))

rem = [1,10,9,12,3,4]
s = input().strip()
sr = s[::-1]
n = len(s)
dp = [ [0]*13 for i in range(n) ]
if sr[0]=='?':
    for j in range(10):
        dp[0][j] = 1
else:
    j = int(sr[0])
    dp[0][j] = 1

for i in range(1,n):
    r = rem[i%6]
    if sr[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R
    else:
        j = int(sr[i])
        for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R

print(dp[n-1][5])


### FIXED CODE ###

#printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)


rem = [1,10,9,12,3,4]
s = input().strip()
sr = s[::-1]
n = len(s)
dp = [ [0]*13 for i in range(n) ]
if sr[0]=='?':
    for j in range(10):
        dp[0][j] = 1
else:
    j = int(sr[0])
    dp[0][j] = 1

for i in range(1,n):
    r = rem[i%6]
    if sr[i]=='?':
        for j in range(10):
            for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R
    else:
        j = int(sr[i])
        for k in range(13):
                dp[i][(k+j*r)%13] = (dp[i][(k+j*r)%13] + dp[i-1][k])%R

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

N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]

s=[]
g=[]
for i, j in ab:
    if i==1:
        s.append(j)
    elif j==1:
        s.append(i)
    elif i==N:
        g.append(j)
    elif j==N:
        g.append(i)
flag=0
for i in range(len(s)):
    for j in range(len(g)):
        if s[i]==g[j]:
            flag=1

print("POSSIBLE"  if flag else "IMPOSSIBLE")


### FIXED CODE ###

N, M=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(M)]
b=set()
for i,j in ab:
    if i==1 or j==N:
        b.add((i,j))
print("IM"*(not(any(((1,i) in b and (i,N) in b) for i in range(N))))+"POSSIBLE")
### BUGGY CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return (a*b)/gcd(a,b)

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=lcm(A[0],A[1])
#LCM%=mod
for i in range(2,N):
  LCM=lcm(LCM, A[i])
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))



### FIXED CODE ###


#かけて最小公倍数になる　そのために必要な数がB
from fractions import gcd
N=int(input())
if N==1:
  print(1)
  exit()

mod=10**9+7
A=list(map(int, input().split()))
def lcm(a,b):
  return a//gcd(a,b)*b

if N==2:
  LCM=lcm(A[0],A[1])
  ans=((LCM//A[0])+(LCM//A[1]))%mod
  print(ans)
  exit()

LCM=1
#LCM%=mod
for a in A:
  LCM=lcm(LCM, a)
  #LCM%=mod
  
#print(LCM)
ans=0
for a in A:
  ans+=LCM//a
  #ans%=mod

print(int(ans%mod))
### BUGGY CODE ###

import itertools
import collections
import math
import sys
sys.setrecursionlimit(2000000)
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
data = [i for i in range(n)]

for i, j in itertools.combinations(data, 2):
    ans += (a[i] % mod)*(a[j] % mod) % mod

ans %= mod
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
total = sum(a)
for i in range(n):
    total -= a[i]
    ans += a[i]*total
    ans %= mod
print(ans)
### BUGGY CODE ###

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

ans = []
for _ in range(2, N-1):
    p = A[:_]
    q = A[_:]
    P = sum(p)
    Q = sum(q)
    p_sa = 10**15
    q_sa = 10**15
    for i in range(1,len(p)):
        s = sum(p[:i])
        sa = abs(P-s*2)
        if sa < p_sa:
            n = [s,P-s]
            p_sa = sa
    for i in range(1,len(q)):
        s = sum(q[:i])
        sa = abs(Q - s*2)
        if sa < q_sa:
            m = [s,Q-s]
            q_sa = sa
    ans.append(max(n+m)-min(n+m))
print(min(ans))

### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
 
ans = []
t = []
c = 0
for i in range(N):
    c += A[i]
    t.append(c)
    
l = 0
r = 0

for _ in range(1, N-1):
    while t[_] > t[l]+t[l+1]:
        l += 1
    while t[-1]+t[_] > t[r]+t[r+1]:
        r += 1
    n = [t[l], t[_]-t[l], t[r]-t[_], t[-1]-t[r]]
    ans.append(max(n)-min(n))
print(min(ans))