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

n,mw=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(mw+1)] for _ in range(n+1)]
for i in range(n):
    weight,value=l[i]
    for j in range(mw+1):
        dp[i+1][j]=max(dp[i+1][j],dp[i][j])
        if j+weight<=mw:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])

### FIXED CODE ###

n,w=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
dp=[[0 for _ in range(w+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        weight,value=a[i]
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        if j+weight<=w:
            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)
print(dp[-1][-1])
### BUGGY CODE ###


n,k=map(int,input().split())
l=[input().split() for _ in range(n)]
b=[[0]*k for _ in range(k)]
w=[[0]*k for _ in range(k)]
anb=[[0]*k for _ in range(k)]
anw=[[0]*k for _ in range(k)]
ans=0
i=0
while i<n:
    m=(((int(l[i][0]))//k)+((int(l[i][1]))//k))%2
    if (m==0 and str(l[i][2])=="W"):
        w[int(l[i][0])%k][int(l[i][1])%k]+=1 
    elif (m==1 and str(l[i][2])=="B"):
        b[int(l[i][0])%k][int(l[i][1])%k]+=1
    elif (m==1 and str(l[i][2])=="W"):
        anw[int(l[i][0])%k][int(l[i][1])%k]+=1
    else:
        anb[int(l[i][0])%k][int(l[i][1])%k] +=1

from numpy import matrix

w=matrix(w)
b=matrix(b)
anw=matrix(anw)
anb=matrix(anb)

for a in range(0,k):
     for b in range(0,k):
         total=w[a:k][b:k].sum()+anw[0:a][0:b].sum()+b[a:k][b:k].sum()+anb[0:a][0:b].sum()
         ans=max(ans,total,n-total)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
imos = [[0 for i in range(k)] for j in range(k)]
white = 0
for i in range(n):
    x, y, c = input().split()
    x = int(x)
    y = int(y)
    if c == "W":
        c = 1
    else:
        c = 0
    x %= 2*k
    y %= 2*k

    if x > k-1:
        x -= k
        c += 1
    if y > k-1:
        y -=k
        c += 1
    c %= 2

    if c == 1:
        white += 1
        imos[x][y] -= 1
    else:
        imos[x][y] += 1

for i in range(k):
    for j in range(k-1):
        imos[i][j+1] += imos[i][j]

for j in range(k):
    for i in range(k-1):
        imos[i+1][j] += imos[i][j]

ans = 0
for i in range(k):
    for j in range(k):
        exp = imos[k-1][k-1] - imos[k-1][j] - imos[i][k-1] + 2 * imos[i][j] + white
        ans = max(ans, max(exp, n - exp))

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

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

ans=[0]*N

for i in range (N):
    a=0
    if Hi[i]<Hi[i-1]:
        continue

    for j in range(N-i-1):
        if Hi[i+j]>=Hi[i+j+1]:
            a+=1
        else:
            break
    ans[i]=a

print(max(ans))

### FIXED CODE ###

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

# ans=[0]*N

# for i in range (N):
#     a=0
#     # if Hi[i]<Hi[i-1]:
#     #     continue
#     for j in range(N-i-1):
#         if Hi[i+j]>=Hi[i+j+1]:
#             a+=1
#         else:
#             break
#     ans[i]=a

# print(max(ans))

ans=0
temp=0

for i in range(1,N):
    if Hi[i]<=Hi[i-1]:
        temp+=1
    else:
        if temp>ans:
            ans=temp
        else:
            pass
        temp=0
else:
    if temp>ans:
        ans=temp

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

def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    min_n = min([a, b])

    kouyaku = []

    for n in range(1, min_n + 1):
        if a % n == 0 and b % n == 0:
            kouyaku.append(n)

    so = [1]
    for i in kouyaku:
        if i == 1: continue

        f = True
        for j in kouyaku:
            if j == 1 or i < j: continue
            if i != j and i % j == 0:
                f = False
                break
        if f is True:
            so.append(i)

    print(len(so))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math


def main():
    inputs = input().split()
    inputs = [int(i) for i in inputs]

    a = inputs[0]
    b = inputs[1]

    g = n = gcd(a, b)
    d = {}

    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i:
            continue
        d[i] = i
        while n % i == 0:
            n /= i

    if n != 1:
        d[n] = n

    print(len(d) + 1)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


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

n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
a=[int(input()) for i in range(m)]
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%mod
    if i in a:
        dp[i]=0
print(int(dp[n]))

### FIXED CODE ###

n,m=map(int,input().split())
dp=[0]*(n+1)
dp[0]=1
mod=10**9+7
broken=[False for _ in range(n+1)]
for _ in range(m):
    broken[int(input())]=True
    
for i in range(1,n+1):
    if broken[i]:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%mod

print(dp[n])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1, n+1):
  print(a.count(i))

### FIXED CODE ###

a = int(input())
b = list(map(int, input().split()))
c = [0 for f in range(a)]
for i in b:
  c[i - 1] += 1
for g in c:
  print(g)
### BUGGY CODE ###

def main():
    s = input()
    n = len(s)
    inf = pow(10, 9)+7
    
    dp = [[0]*13 for i in range(n)]
    if s[0] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s[0])] = 1
    
    for i in range(1, n):
        if s[i] != "?":
            k = int(s[i])
            for j in range(13):
                dp[i][(10*j+k)%13] += dp[i-1][j]
        else:
            for k in range(10):
                for j in range(13):
                    dp[i][(10*j+k)%13] += dp[i-1][j]
        for j in range(13):
            dp[i][j] %= inf
        
    print(dp[n-1][5])
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    n = len(s)
    inf = pow(10, 9)+7
    
    dp = [[0]*13 for i in range(n)]
    if s[0] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(s[0])] = 1
    
    for i in range(1, n):
        if s[i] != "?":
            k = int(s[i])
            for j in range(13):
                dp[i][(10*j+k)%13] += dp[i-1][j]
        else:
            for k in range(10):
                for j in range(13):
                    dp[i][(10*j+k)%13] += dp[i-1][j]
        for j in range(13):
            dp[i][j] %= inf
        
    print(dp[n-1][5])
    

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

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

a = 0
while True:
    s = AB.pop(0)
    if M > s[1]:
        M -= s[1]
        a += s[0] * s[1]
    else:
        a += s[0] * M
        break

print(a)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

a = 0
while True:
    s = AB.pop(0)
    if M > s[1]:
        M -= s[1]
        a += s[0] * s[1]
    else:
        a += s[0] * M
        break

print(a)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1,n):
  ans += i
print(ans)


### FIXED CODE ###

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

import collections

n = int(input())
count = 0

for i in range(1, n + 1, 2):
	c = collections.Counter(list(str(i)))
	if len(c.keys()) == 3:
		if (c['3'] != 0) and (c['5'] != 0) and (c['7'] != 0):
			count += 1
print(count)

### FIXED CODE ###

n = int(input())
count = 0

def dfs(s):
	if int(s) > n:
		return 0
	if all(s.count(c) > 0 for c in '357'):
		count = 1
	else:
		count = 0
	count += dfs(s + '3')
	count += dfs(s + '5')
	count += dfs(s + '7')
	return count

print(dfs('0'))
### BUGGY CODE ###


def solve():
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x+y+z == S:
                    cnt += 1
    print(cnt)


if __name__=="__main__":
    K, S = list(map(int, input().split()))
    solve()


### FIXED CODE ###


def solve():
    cnt = 0
    for x in range(K+1):
        for y in range(K+1):
            z = S - (x+y)
            if 0 <= z and z <= K:
                cnt += 1

    print(cnt)


if __name__=="__main__":
    K, S = list(map(int, input().split()))
    solve()
### BUGGY CODE ###

n = int(input())
s = list(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

R,G,B = [],[],[]


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)

ans = 0
for r in R:
    for g in G:
        for b in B:
            tmp = [r,g,b]
            tmp = list(sorted(tmp))

            if 2*tmp[1] != tmp[0] + tmp[2]:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
#a,b = map(int,input().split())
#a_L = list(map(int,input().split()))

R,G,B = [],[],[]


for i in range(n):
    if s[i] == "R":
        R.append(i)
    elif s[i] == "G":
        G.append(i)
    else:
        B.append(i)


base = len(R) * len(G) * len(B)

B = set(B)

ans = 0
for r in R:
    for g in G:
        y = max(r,g)
        x = min(r,g)
        
        # x < 0 < y

        tmp = int((x+y)/2)
        if (x+y)%2==0 and (tmp in B):
            ans += 1
        # x<y<0
        tmp = 2*y-x
        if tmp in B:
            ans += 1
        #0 < x < y
        tmp = 2*x-y
        if tmp in B:
            ans += 1

print(base-ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return 

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k or k == i:
                    continue
                if dp[i][k] == inf or dp[i][j] == inf or dp[j][k] == inf:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    # i->jは要らない
                    dp[i][j] = inf
    cnt = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] < inf:
                cnt += dp[i][j]
    print(cnt // 2)
main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print(-1)
        return
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()
### BUGGY CODE ###

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

def mod2(num):
    return num%2==0

def div2(num):
    return num//2

count = 0
while True:
    if len(set(map(mod2,a_list))) != 1 :
        break
    else:
        a_list = list(map(div2, a_list))
        count += 1
print(count)

### FIXED CODE ###

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

count_list = []
for a in a_list:
    count = 0
    q,mod = divmod(a,2)
    while True:
        if mod != 0:
            break
        else:
            q,mod = divmod(q,2)
            count += 1
    count_list.append(count)
print(min(count_list))
### BUGGY CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<100
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

### FIXED CODE ###

H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    # ループしているところを見つける
    path = [1]
    current = 0
    looping = False
    loop_st = -1
    loop_ed = -1
    for i in range(n):
        _next = a[current]

        if _next in path:
            loop_st = path.index(_next)
            loop_ed = len(path)
            looping = True
            break
        path.append(_next)
        current = _next-1

    if looping:
        if loop_ed - 1 >= k:
            print(path[k])
        else:
            len_loop = loop_ed - loop_st
            z = (k - loop_st) % len_loop
            print(path[loop_st + z])
    else:
        print(path[k])


main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    # ループしているところを見つける
    path = [1]
    dic = [0] * n
    dic[0] = 1
    current = 0
    looping = False
    loop_st = -1
    loop_ed = -1
    for i in range(n):
        _next = a[current]
        if dic[_next-1] == 1:
            loop_st = path.index(_next)
            loop_ed = len(path)
            looping = True
            break
        dic[_next-1] = 1
        # if _next in path:
        #     loop_st = path.index(_next)
        #     loop_ed = len(path)
        #     looping = True
        #     break
        path.append(_next)
        current = _next-1

    if looping:
        if loop_ed - 1 >= k:
            print(path[k])
        else:
            len_loop = loop_ed - loop_st
            z = (k - loop_st) % len_loop
            print(path[loop_st + z])
    else:
        print(path[k])


main()
### BUGGY CODE ###

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

nmax = 0

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans = 0

for i in range(N + 1):
    if a[i] > K:
        break

    for j in range(M+1):
        if b[j] + a[i] > K:
            break
        ans = max(ans, i+j)

print(ans)
exit()


### FIXED CODE ###

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

nmax = 0

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans = 0
j = M
for i in range(N + 1):
    if a[i] > K:
        break

    while b[j] + a[i] > K:
        j -= 1
    ans = max(ans, i+j)

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

N = int(input())
L = [int(i) for i in input().split()]
count = 0

for a in range(N):
    for b in range(a+1, N):
        for c in range(b+1, N):
            if L[a]>=L[b]+L[c] or L[b]>=L[c]+L[a] or L[c]>=L[a]+L[b]:
                pass
            else:
                count += 1

print(count)

### FIXED CODE ###

import bisect
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
count = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        count += bisect.bisect_left(L, L[a]+L[b])-b-1
print(count)
### BUGGY CODE ###

n,k=map(int,input().split())
l=[int(x) for x in input().split()]
dp=[0 for i in range(k+1)]
dp[0]=1
for i in range(len(l)):
	p=[0]*(k+1)
	for j in range(k-1,-1,-1):
		li= j+1
		ri=j+min(l[i],k-j)+1
		if li<=ri:
			p[j+1]+=dp[j]
		if ri<=k:
			p[j+min(l[i],k-j)+1]-=dp[j]
		'''for o in range(j+1,j+min(l[i],k-j)+1):
			dp[o]+=dp[j]'''
	su=0
	for i in range(k+1):
		su+=p[i]
		dp[i]+=su
print(dp[k]%(10**9+7))
#print(dp[0][n-1])

### FIXED CODE ###

n,k=map(int,input().split())
l=[int(x) for x in input().split()]
dp=[0 for i in range(k+1)]
dp[0]=1
M=10**9+7
for i in range(len(l)):
	p=[0]*(k+1)
	for j in range(k-1,-1,-1):
		li= j+1
		ri=j+min(l[i],k-j)+1
		if li<=ri:
			p[j+1]+=dp[j]
		if ri<=k:
			p[j+min(l[i],k-j)+1]-=dp[j]
		'''for o in range(j+1,j+min(l[i],k-j)+1):
			dp[o]+=dp[j]'''
	su=0
	for i in range(k+1):
		su=(su+p[i])%M
		dp[i]=(dp[i]+su)%M
print(dp[k]%(10**9+7))
#print(dp[0][n-1])
### BUGGY CODE ###

from sys import stdin

n, q = map(int, stdin.readline().split())
s = stdin.readline().strip()
count = 0
for i in range(q):
    l, r = map(int, stdin.readline().split())
    for j in range(l - 1, r - 1):
        if s[j] + s[j + 1] == 'AC':
            count += 1

    print(count)
    count = 0


### FIXED CODE ###

from sys import stdin

n, q = map(int, stdin.readline().split())
s = stdin.readline().strip()
counts = [0 for i in range(n)]
count = 0
for i in range(1, n):
    if s[i-1:i+1] == 'AC':
        count += 1
    counts[i] = count

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

import itertools
from collections import deque,Counter
n,x,y = map(int,input().split())
route=[[10**10]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  q=deque([i])
  j=i
  route[i][j]=0
  while q:
    j=q.pop()
    if j == y:
      if route[i][j]+1 < route[i][x]:
        route[i][x]=route[i][j]+1
        q.append(x)
    if j == x:
      if route[i][j]+1 < route[i][y]:
        route[i][y]=route[i][j]+1
        q.append(y)
    if 1 < j:#-1
      if route[i][j]+1 < route[i][j-1]:
        route[i][j-1]=route[i][j]+1
        q.append(j-1)
    if j < n:#+1
      if route[i][j]+1 < route[i][j+1]:
        route[i][j+1]=route[i][j]+1
        q.append(j+1)

ans=Counter(list(itertools.chain.from_iterable(route)))
for i in range(1,n):
  print(ans[i]//2)


### FIXED CODE ###

import itertools
from collections import deque,Counter
n,x,y = map(int,input().split())
route=[[10**10]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  q=deque([i])
  j=i
  route[i][j]=0
  while q:
    j=q.pop()
    if j == y:
      if route[i][j]+1 < route[i][x]:
        route[i][x]=route[i][j]+1
        q.append(x)
    if j == x:
      if route[i][j]+1 < route[i][y]:
        route[i][y]=route[i][j]+1
        q.append(y)
    if 1 < j:#-1
      if route[i][j]+1 < route[i][j-1]:
        route[i][j-1]=route[i][j]+1
        q.append(j-1)
    if j < n:#+1
      if route[i][j]+1 < route[i][j+1]:
        route[i][j+1]=route[i][j]+1
        q.append(j+1)

ans=Counter(list(itertools.chain.from_iterable(route)))
for i in range(1,n):
  print(ans[i]//2)
### BUGGY CODE ###

S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,13),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      for j in range(13):
        dp[i][convert(j,d)]+=dp[i-1][j]
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    for j in range(13):
      dp[i][convert(j,d)]+=dp[i-1][j]
  dp[i]=dp[i]%DIV

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

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

#5
#24 11 8 3 16

N = int(input())
num = list(map(int, input().split()))
divz = [0]*N

num.sort()

count = 0
for i, n in enumerate(num):
    if divz[i] == 0:
        for k in range(i+1, N):
            if divz[k] == 0:
                if num[k] == num[i]:
                    divz[i] = 1
                if num[k] % num[i] == 0:
                    divz[k] = 1
        if divz[i] == 0: count += 1

print(count)


### FIXED CODE ###

import numpy as np

N = int(input())
MAXX = 10**6 + 5
num = np.array(input().split(), np.int32)[:]
mark = np.zeros(MAXX, np.int32)

num = np.sort(num)
for n in num:
    if mark[n] < 2:
        mark[n::n] += 1

count = 0
for n in num:
    if mark[n] == 1:
        count += 1

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

N=int(input())
M=0
for i in range(N-1):
  M+=(i+1)
print(M)

### FIXED CODE ###

N=int(input())
if (N-1)%2==0 :
  print(N*((N-1)//2))
else :
  print(N*((N-1)//2)+N//2)
### BUGGY CODE ###

def copy(l):
    l1=[]
    for i in l:
        l1.append(i)
    return l1
s = input()
n = len(s)
l = [1]*n
k = 0
c = 1
for i in range(len(s)-1):
    if k<c:
        k = c
    if(s[i+1]==s[i]):
        c+=1
    else:
        c = 0
    
if k%2 ==1:
    k+=1
for _ in range(k):
    l1 = copy(l)
    for i in range(n):
        if(l[i]):
            if s[i] == 'R':
                l[i+1]+=l1[i]
                l[i] =l[i]- l1[i];
            else:
                l[i-1]+=l1[i]
                l[i] =l[i] -l1[i]

for i in l:
    print(i,end = " ")

### FIXED CODE ###

s = input()+'R'
n = len(s)
flag = 0
cr=1
cl=0
l=[]
for i in range(1,n):
    if(s[i]=='L'):
        flag=1
        cl+=1
    elif s[i]=='R' and flag == 0:
        cr+=1
    elif i==n-1 or s[i]=='R' and flag!=0:
        temp = [0]*(cl+cr)
        if(cr>cl):
            diff = cr-cl
            temp[cr-1] = cl+diff-diff//2
            temp[cr] = cl + diff//2
            if (cl+diff-1)%2==1:
                temp[cr-1],temp[cr] = temp[cr],temp[cr-1]
        elif(cr<cl):
            diff = cl-cr
            temp[cr-1] = cr+diff-diff//2
            temp[cr] = cr + diff//2
            if (cr+diff-1)%2==0:
                temp[cr-1],temp[cr] = temp[cr],temp[cr-1]
        else:                #cr==cl
            temp[cr-1] = cr
            temp[cr] = cl  #cr==cl
        l+=temp
        flag = 0
        cr = 1
        cl=0
        #continue
    
print(" ".join(map(str,l)))