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

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

### FIXED CODE ###

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

N = int(input())
S = []
for i in range(N):
    S.append(input())
S.sort()
B = [S[0]]
C = [1]
for i in range(N-1):
    if S[i] == S[i+1]:
        C[B.index(S[i+1])] += 1
    else:
        B.append(S[i+1])
        C.append(1)

for i in range(len(C)):
    if C[i] == max(C):
        print(B[i])

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
    S.append(input())
S.sort()
S.append("A")
B = []
M = 1
T = 1
for i in range(N):
    if S[i] == S[i+1]:
        T += 1
    elif T < M:
        T = 1
    elif T == M:
        T = 1
        B.append(S[i])
    else:
        M = T
        T = 1
        B = [S[i]]

for i in range(len(B)):
    print(B[i])
### BUGGY 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()
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 ###

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

for i in range(1, n + 1):
    cnt = 0
    for j in range(n - 1):
        if i == a[j]:
            cnt += 1
    l.append(cnt)
            
for k in range(n):
    print(l[k])


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [0] * n

for i in a:
    l[i - 1] += 1
    
for k in range(n):
    print(l[k])
### BUGGY CODE ###

class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n,k=map(int,input().split())
arr=[int(input()) for _ in range(n)]
lim=max(arr)
st=SegmentTreeMax(lim,0)
for val in arr:
  l=max(0,val-k)
  r=min(lim,val+k)
  tmp=st.query(l,r)
  st.update(val,tmp+1)
print(st.query(0,lim))

### FIXED CODE ###

class SegmentTreeMax():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=val
    while pos>1:
      pos=pos//2
      self.tree[pos]=max(self.tree[2*pos],self.tree[2*pos+1])
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=max(ret,self.tree[r])
      r=(r-1)//2
      ret=max(ret,self.tree[l])
      l=(l+1)//2
    return ret

n,k=map(int,input().split())
arr=[int(input()) for _ in range(n)]
lim=max(arr)
st=SegmentTreeMax(lim,0)
for val in arr:
  l=max(0,val-k)
  r=min(lim,val+k)
  tmp=st.query(l,r)
  st.update(val,tmp+1)
print(st.query(0,lim))
### BUGGY CODE ###

n = int(input())
s = list(input())

ss = [0] * n
ans = 0
for i in range(n):
    if s[i] == 'R':
        ss[i] = 1
    elif s[i] == 'G':
        ss[i] = 2
    else:
        ss[i] = 3

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if (j - i) == (k - j):
                continue
            if ss[i] == ss[j] == ss[k] == 2:
                continue
            else:
                if ss[i] + ss[j] + ss[k] == 6:
                    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = list(input())
s_reverse = s[::-1]
ans = 0
r_cnt = 0
b_cnt = 0
g_cnt = 0
r = [0] * n
b = [0] * n
g = [0] * n
for i in range(n):
    if s_reverse[i] == 'R':
        r_cnt += 1
    elif s_reverse[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1
    r[n-i-1] = r_cnt
    g[n-i-1] = g_cnt
    b[n-i-1] = b_cnt
    
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] == 'R' and s[j] == 'G':
            if (2*j - i) < n:
                if s[j+(j-i)] == 'B':
                    ans -= 1
            ans += b[j+1]
        elif s[i] == 'R' and s[j] == 'B':
            if (2 * j - i) < n:
                if s[j+(j-i)] == 'G':
                    ans -= 1
            ans += g[j+1]
        elif s[i] == 'G' and s[j] == 'R':
            if (2 * j - i) < n:
                if s[j+(j-i)] == 'B':
                    ans -= 1
            ans += b[j+1]
        elif s[i] == 'G' and s[j] == 'B':
            if (2 * j - i) < n:
                if s[j+(j-i)] == 'R':
                    ans -= 1
            ans += r[j+1]
        elif s[i] == 'B' and s[j] == 'R':
            if (2 * j - i) < n:
                if s[j+(j-i)] == 'G':
                    ans -= 1
            ans += g[j+1]
        elif s[i] == 'B' and s[j] == 'G':
            if (2 * j - i) < n:
                if s[j+(j-i)] == 'R':
                    ans -= 1
            ans += r[j+1]

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

L, R = map(int, input().split())
ans = 2019
for i in range(L, R):
    for j in range(i+1, R+1):
        ans = min(ans, i*j%2019)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())

if abs(L-R)>2019:
    print(0)
else:
    ans = 2019
    for i in range(L, R):
        for j in range(i+1, R+1):
            ans = min(ans, i*j%2019)
    print(ans)
### BUGGY CODE ###

k = int(input())

cnt = 9
if k < 10:
    print(k)
else:
    for i in range(10,10**16+2):
        s = str(i)
        flag = True
        for j in range(len(s)-1):
            if abs(int(s[j])-int(s[j+1])) > 1:
                flag = False
                break
        if flag == True:
            cnt += 1
        if cnt == k:
            print(i)
            break

### FIXED CODE ###

k = int(input())

l = [i for i in range(1,10)]
for i in range(k):
    if l[i]%10 != 0:
        l.append(10*l[i]+l[i]%10-1)
    l.append(10*l[i]+l[i]%10)
    if l[i]%10 != 9:
        l.append(10*l[i]+l[i]%10+1)
print(l[k-1])
### BUGGY CODE ###

from scipy.special import comb

n = int(input())
a = sorted(list(map(int, input().split())))
num0, num1, val = 0, 0, 0

if n == 2:
    print(a[1], a[0])
else:
    for i in range(n-1, n//2, -1):
        for j in range(i-1, 0, -1):
            val0 = comb(a[i], a[j])
            if val0 > val:
                num0 = a[i]
                num1 = a[j]
                val = val0
    print(num0, num1)


### FIXED CODE ###

_ = int(input())
a = sorted(list(map(int, input().split())))
num0, num1, val = a[-1], 0, float('inf')

for i in a[:-1]:
    val0 = abs(i-num0/2)
    if val0 < val:
        num1 = i
        val = val0
print(num0, num1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    if n%2==1:
        print(0)
    else:

        def divide_count(n, p):
            """nをpで何回割り切れるか"""
        
            temp = n  # nを破壊しないため
            cnt = 0
            val = p
            m = n
            while n % p == 0:
                n //= p
                cnt += 1
            n = temp
            return cnt
        
        cnt=0
        while n>=2:
            cnt+=divide_count(n,5)
            n-=2
        print(cnt)

    
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    n=int(input())
    
    if n%2==1:
        print(0)
    else:
        N=n//2
        cnt=0
        while N>=5:
            cnt+=N//5
            N//=5
        print(int(cnt))
        



    
resolve()
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
dp = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    path[x-1].add(y-1)
    dp[y-1] = -1

que = deque()
for i in range(n):
    if dp[i] == 0:
        que.append(i)
ans = 0
while que:
    p = que.popleft()
    for i in path[p]:
        que.append(i)
        dp[i] = max(dp[i], dp[p] + 1)
        ans = max(ans, dp[i])
print(ans)


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
path = [set() for _ in range(n)]
to = [0]*n
dp = [0]*n
for _ in range(m):
    x,y = map(int,input().split())
    path[x-1].add(y-1)
    to[y-1] += 1

que = deque()
for i in range(n):
    if to[i] == 0:
        que.append(i)
ans = 0
while que:
    p = que.popleft()
    for i in path[p]:
        to[i] -= 1
        if to[i] == 0:
            que.append(i)
        dp[i] = max(dp[i], dp[p] + 1)
        ans = max(ans, dp[i])
print(ans)
### BUGGY CODE ###

import sys
from fractions import Fraction

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
g1, s1, b1 = nm()
g2, s2, b2 = nm()


def solve():
    gr, sr, br = (g2, g1), (s2, s1), (b2, b1)
    rp = sorted([(Fraction(n, d), n, d) for (n, d) in [gr, sr, br] if n > d])
    rn = sorted([(Fraction(n, d), n, d) for (n, d) in [gr, sr, br] if n < d])

    # Start
    don = N
    # A
    don_max = N
    for kg in range(don // g1 + 1):
        don1 = don - kg * g1
        temp1 = kg * g2
        for ks in range(don1 // s1 + 1):
            don2 = don1 - ks * s1
            temp2 = ks * s2
            if b2 > b1:
                kb = don2 // b1
                don3 = don2 - kb * b1
                temp3 = kb * b2
            else:
                kb = 0
                don3 = don2
                temp3 = 0
            if don_max < don3 + temp1 + temp2 + temp3:
                don_max = don3 + temp1 + temp2 + temp3
                # print(f"1> don_max={don_max} g:{kg} s:{ks} b:{kb}")

    don = don_max
    for kg in range(don // g2 + 1):
        don1 = don - kg * g2
        temp1 = kg * g1
        for ks in range(don1 // s2 + 1):
            don2 = don1 - ks * s2
            temp2 = ks * s1
            if b1 > b2:
                kb = don2 // b2
                don3 = don2 - kb * b2
                temp3 = kb * b1
            else:
                kb = 0
                don3 = don2
                temp3 = 0
            if don_max < don3 + temp1 + temp2 + temp3:
                don_max = don3 + temp1 + temp2 + temp3
                # print(f"2> don_max={don_max} g:{kg} s:{ks} b:{kb}")
    return don_max


print(solve())


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())

N = ni()
g1, s1, b1 = nm()
g2, s2, b2 = nm()

INF = 10 ** 15


def solve():
    x1 = [g1, s1, b1]
    x2 = [g2, s2, b2]

    # dp[i] := max future donguri when we use i donguri
    dp = [-INF] * (N + 1)
    dp[0] = N
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 >= t2:
            continue
        for j in range(t1, N + 1):
            r = dp[j - t1] - t1
            if r >= 0 and dp[j] < r + t2:
                dp[j] = r + t2

    don = max(dp)
    dp = [0] * (don + 1)
    dp[0] = don
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 <= t2:
            continue
        for j in range(t2, don + 1):
            r = dp[j - t2] - t2
            if r >= 0 and dp[j] < r + t1:
                dp[j] = r + t1
    return max(dp)


print(solve())
### BUGGY CODE ###

n=int(input())
A = list(map(int,input().split()))
#t = {}
#for i,a in enumerate(A):
#  if a not in t: t[a]=0
#  t[a]+=1
ans = 0
for k in range(1,n):
  for i in range(k,n):
    if A[i] + A[i-k] == k:
      ans += 1
print(ans)
  

### FIXED CODE ###

N = int(input())
A = [int(v) for v in input().split()]
L, R = {}, {}
for i,a in enumerate(A):
  l,r = i+a,i-a
  if l not in L: L[l]=0
  if r not in R: R[r]=0
  L[l]+=1
  R[r]+=1

count = 0
for X in L:
  if X not in R: continue
  count += L[X]*R[X]
print(count)
### BUGGY CODE ###

def solve():
    a = [int(input()) for i in range(1, int(input()) + 1)]
    # ループしたら終わる
    l = []
    s = a[0]
    l.append(s)
    c = 1
    while(True):
        if s == 2:
            print(c)
            return True
        s = a[s - 1]
        if s in l:
            print(-1)
            return False
        l.append(s)
        c += 1
solve()


### FIXED CODE ###

def solve():
    N = int(input())
    a = [int(input()) for i in range(1, N + 1)]
    # ループしたら終わる
    l = []
    s = a[0]
    l = [0] * N
    c = 1
    l[0]=True
    while(True):
        l[s - 1] = True
        if s == 2:
            print(c)
            return True
        s = a[s - 1]
        if l[s - 1] == True:
            print(-1)
            return False
        c += 1
solve()
### BUGGY CODE ###

n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*10**i
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1
for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)


### FIXED CODE ###

def main():
	N,P = map(int,input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i]%P == 0:
				ans += N-i
		print(ans)
		return
	L = [0]*P
	L[0]=1
	t = 0
	s = 1
	for z in S:
		t = (z*s+t)%P	
		L[t]+=1
		s=s*10%P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

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

#!/usr/bin/env python3

def func(n):
    cnt = 0
    n = min(n, 20)
    for x in range(1, n):
        for y in range(1, n):
            for z in range(1, n):
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    cnt += 1
    return cnt


def main():
    N = int(input())

    for i in range(1, N + 1):
        print(func(i))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())

    ans = [0] * (N + 1)

    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                f = x * x + y * y + z * z + x * y + y * z + z * x
                if f < N + 1:
                    ans[f] += 1
    ans.remove(0)
    print('\n'.join(map(str, ans)))


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

n, k = map(int, input().split())
max_k = k.bit_length()
A = [0] + list(map(int, input().split()))

DB = [[0] * (n + 1) for _ in range(max_k + 1)]
# DB[i][j] 2**i乗回考えた時にjが移動する数
for j in range(1, n + 1):
    DB[0][j] = A[j]
for i in range(max_k):
    for j in range(1, n + 1):
        num = DB[i][j]
        DB[i + 1][j] += DB[i][num]
bit = bin(k)
num = 1
for i in range(max_k):
    if bit[-(i + 1)] == "1":
        num = DB[i][num]
print(num)


### FIXED CODE ###

n, k = map(int, input().split())
A = [0] + list(map(int, input().split()))
cnt = 0
pre = 1
memo = []
kumi = set([])
if k < n:
    for i in range(2 * (10 ** 5) + 5):
        cur = A[pre]
        cnt += 1
        pre = cur
        if cnt == k:
            print(cur)
            exit()

else:
    for i in range(2 * (10 ** 5) + 5):
        cur = A[pre]
        cnt += 1
        memo.append(cur)
        if cur in kumi:
            break
        kumi.add(cur)
        pre = cur
    # 今までに見た物の数を減らしておく、kは残り回数
    k -= cnt

    for j in range(cnt):
        if memo[j] == cur:
            start = j
            break
    loop = memo[start:-1]

    loop_num = i - start
    print(loop[k % loop_num])
### BUGGY CODE ###

n=int(input())
a=[]
m,m2=-1,-1
for i in range(n):
  b=int(input())
  a.append(b)
  m2=max(m2,min(m,b))
  m=max(m,b)

if m==m2:
  for i in range(n):
    print(m)
else:
  for i in range(n):
    if a.index(m)==i:
      print(m2)
    else:
      print(m)

### FIXED CODE ###

n=int(input())
a=[]
m,m2=-1,-1
  
for i in range(n):
  b=int(input())
  a.append(b)
  m2=max(m2,min(m,b))
  m=max(m,b)

if m==m2:
  for i in range(n):
    print(m)
else:
  l=[m]*n
  l[a.index(m)]=m2
  for i in range(n):
    print(l[i])
### BUGGY CODE ###

s=list(input())
q=int(input())

for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        s=s[::-1]
    else:
        if query[1]=='1':
            s=[query[2]]+s
        else:
            s+=[query[2]]
print(*s,sep='')

### FIXED CODE ###

from collections import deque

s=input()
q=int(input())
d=deque(s)

cnt=0
for _ in range(q):
    query=list(input().split())
    if query[0]=='1':
        cnt=(cnt+1)%2
    else:
        if query[1]=='1':
            if cnt==1:
                d.append(query[2])
            else:
                d.appendleft(query[2])
        else:
            if cnt==1:
                d.appendleft(query[2])
            else:
                d.append(query[2])
                
ans=list(d)
                
if cnt==1:
    print(*ans[::-1],sep='')
else:
    print(*ans,sep='')
### BUGGY CODE ###

N = int(input())
S = input().strip()

after = S[0]
for i in range(1, N):
    if S[i] != S[i-1]:
        after += S[i]

print(len(after))


### FIXED CODE ###

N = int(input())
S = input().strip()

after = [S[0]]
for i in range(1, N):
    if S[i] != S[i-1]:
        after.append(S[i])

print(len(after))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline
 
 
def main():
    n = int(input())
    s = list(input())[:n]
 
    # memory = [[0 for j in range(n)] for i in range(n)]
    # for i in range(n):
    #     for j in range(i, n):
    #         memory[i][j] = s[i] == s[j]
    #         memory[j][i] = s[i] == s[j]
    # print(memory)
 
    result = 0
    for i in range(n):
        for j in range(i, n):
            for k in range(j, n):
                if s[i] == s[j] or s[j] == s[k] or s[k] == s[i]:
                    continue
                if j - i == k - j:
                    continue
                result += 1
    print(result)
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = input()

    ans = s.count('R') * s.count('G') * s.count('B')
    # print(ans)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            k = (j - i) + j
            if k >= n:
                # print(i, j, k)
                break

            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                ans -= 1

    print(ans)


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

n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)

max_sumv = sum(V) 
# Dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値小値
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_sumv + 1):
        # i番目の商品を選ぶ場合
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        # i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)

### FIXED CODE ###

n, w = map(int, input().split())
W, V = [], []
for i in range(n):
    wi, vi = map(int, input().split())
    W.append(wi)
    V.append(vi)

max_sumv = sum(V) 
# Dp[i][sum_v] := i-1 番目までの品物から価値がsum_v以上を達成するように選んだときの、重さの総和の最小値小値
dp = [[10 ** 9] * (max_sumv + 1) for _ in range(n+1)]

dp[0][0] = 0

for i in range(n):
    for sum_v in range(max_sumv + 1):
        # i番目の商品を選ぶ場合
        if sum_v - V[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - V[i]] + W[i])
        # i番目の商品を選ばない場合
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
ans = 0
for i in range(max_sumv + 1):
    if dp[n][i] <= w:
        ans = i
print(ans)
### BUGGY CODE ###

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

S = [[0]*2 for i in range(N)]
for i in range(N):
    S[i] = list(map(int, input().split()))
     
S = sorted(S)

quantitys = 0
total = 0

for i in range(N):
    quantity = 0
    x = 0
    for ii in range(S[i][1]):
        if quantitys<M:
            quantitys += 1
            quantity += 1
    x += quantity * S[i][0]
    total += x

print(str(total))



### FIXED CODE ###

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

S = [[0]*2 for i in range(N)]
for i in range(N):
    S[i] = list(map(int, input().split()))
     
S = sorted(S)

quantitys = 0
total = 0

for i in range(N):
    # 【根本註】この for 文の中がソースコードの変更点となります。
    # ここまでのコードで、二次元配列 S に「エナジードリンクが安い順」に
    # 金額と本数のセットを格納できているわけですから、あとは「その店で何本買えばよいか？」
    # を計算し、for 文を使わずに普通の数式ベースで金額・本数の計算を行ってしまうのが正しい方法となります。
    
    #【根本註】必要な本数 M から「今何本購入しているか」を表す quantitys を引くことで、
    # 「あと何本購入する必要があるか」を表す変数 need を計算します。
    need = M - quantitys

    #【根本註】この変数 need：「あと何本必要か」が、今参照している店の在庫本数：S[i][1] 以上ならば、
    # その店の在庫を全部購入することができるはずです。（在庫を全部買うと、残りが 0 本ちょうどか 1 本以上に
    # なります）
    if(need - S[i][1])>=0:
        # 【根本註】そのため、この場合は S[i][1] 本のエナジードリンクを S[i][0] 円で買ったものとして、
        # quantitys には S[i][1] を足し、金額の合計 total には S[i][0] * S[i][1] の 金額 × 本数 の合計額を
        # 足してしまいます。こうすることで、従来は購入する本数分だけ回していた for 文の処理を全て削減し、
        # 1 本の数式に落とし込むことができ、処理にかかる時間を非常に大きく削減することが可能になるのです。
        quantitys += S[i][1]
        total += S[i][0] * S[i][1]

    #【根本註】一方で、変数 need：「あと何本必要か」が、今参照している店の在庫本数：S[i][1] より少なければ、
    # その店では need 本だけ購入すれば、必要な本数ちょうどに揃えることが可能になります。
    else:
        # 【根本註】同様に、この場合は need 本のエナジードリンクを S[i][0] 円で買ったものとして、
        # quantitys には need を足し、金額の合計 total には S[i][0] * need の 金額 × 本数 の合計額を
        # 足してしまいます。
        quantitys += need
        total += S[i][0] * need

    #【根本註】ここまでの処理を終えた段階で、もし M （必要本数）から quantities（購入済の本数）を引いた値が
    # ゼロになったならば、必要な本数を買い揃えることができたということになりますから、ループを終了します。
    if M-quantitys == 0:
        break

print(str(total))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mx = max(a)

dp = [0] * (mx+1)
for i in sorted(a):
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in a:
    if dp[i] == 0 and a.count(i) == 1:
        cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
mx = max(a)
a.sort()
c = Counter(a)

dp = [0] * (mx+1)
for i in a:
    if dp[i] == 1:
        continue
    j = 2
    while i * j <= mx:
        dp[i*j] = 1
        j += 1

cnt = 0
for i in set(a):
    if dp[i] == 0 and c[i] == 1:
        cnt += 1

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

k = int(input())
if k % 2 == 0:
	print(-1)
	exit()
i = 7
cnt = 1
while i % k != 0:
	if i % k != i:
		i = i % k
	i = i * 10 + 7
	cnt += 1
print(cnt)

### FIXED CODE ###

k = int(input())
j = 7

for i in range(k):
	if j % k < 1:
		print(i + 1)
		exit()
	j = (j * 10 + 7) % k
print(-1)