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

N, K = map(int, input().split())
dK = 2*K

MeetDemand =[[0 for c in range(dK+1)] for r in range(dK)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = int(y) 
    if c == "W":
        y += K
    y %= dK
    if 0 <= x < K and 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    elif 0 <= x < K:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2
    elif 0 <= y < K:
        MeetDemand[x-K+1][0] += 1
        MeetDemand[x-K+1][y+1] -= 2
        MeetDemand[0][y+1] += 1
        MeetDemand[0][y+K+1] -= 1
        MeetDemand[x-K+1][y+K+1] += 2
    else:
        MeetDemand[0][0] += 1
        MeetDemand[0][y-K+1] -= 1
        MeetDemand[x-K+1][0] -= 1
        MeetDemand[x-K+1][y-K+1] += 2
        MeetDemand[0][y+1] += 1
        MeetDemand[x-K+1][y+1] -= 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
Ans = max(MeetDemand[0][:dK])
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]
        Ans = max(Ans, MeetDemand[x][y])
print(Ans)

### FIXED CODE ###

N, K = map(int, input().split())
dK = 2*K

MeetDemand =[[0 for y in range(dK+1)] for x in range(K+1)]
for i in range(N):
    x, y, c =input().split()
    x = int(x) % dK
    y = (int(y)+K if c=="W" else int(y)) % dK
    if K <= x:
        if 0 <= y < K:
            x -= K
            y += K
        else:
            x %= K
            y %= K
    if 0 <= y < K:
        MeetDemand[0][0] += 1
        MeetDemand[x+1][y+1] += 2
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][0] -= 1
        MeetDemand[0][y+K+1] += 1
        MeetDemand[x+1][y+K+1] -= 2
    else:
        MeetDemand[0][y-K+1] += 1
        MeetDemand[x+1][y-K+1] -= 2
        MeetDemand[x+1][0] += 1
        MeetDemand[0][y+1] -= 1
        MeetDemand[x+1][y+1] += 2

for x in range(K):
    for y in range(1, dK):
        MeetDemand[x][y] += MeetDemand[x][y-1]
for y in range(dK):
    for x in range(1, K):
        MeetDemand[x][y] += MeetDemand[x-1][y]

Ans = max(MeetDemand[0][:dK])
for i in range(1, K):
    Ans = max(Ans, max(MeetDemand[i][:dK]))
print(Ans)
### BUGGY CODE ###

# TLEを承知で出す
n, m = map(int, input().split())

nums = sorted([int(i) for i in input().split()])[::-1]

for _ in range(m):
    a, b = map(int, input().split())
    nums += [b] * a

nums = sorted(nums)[::-1]
print(sum(nums[:n]))


### FIXED CODE ###

# from collections import defaultdict
# n, m = map(int, input().split())
# nums = [int(i) for i in input().split()]
#
# num_freq = defaultdict(int)
#
# for _ in range(m):
#     b, c = map(int, input().split())
#     num_freq[c] += b
#
#
# new_list = []
# for num, freq in sorted(num_freq.items(), key=lambda x: -x[0]):
#     new_list += [num] * freq
#     if len(new_list) >= n:
#         break
# tmp = sorted(nums + new_list)[::-1]
# print(sum(tmp[:n]))

# ↑と同じ処理なのに↑のはREになる
n, m = map(int, input().split())
nums = list(map(int, input().split()))
exc = []

for i in range(m):
    exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(m):
    freq = exc[i][0]
    e += [exc[i][1]] * freq
    count += freq
    if count >= n:
        break
cards = sorted(nums + e, reverse=True)
print(sum(cards[:n]))
### BUGGY CODE ###

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

def gcdlist(*l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

N = int(input())

I = range(1, N+1)
J = range(1, N+1)
K = range(1, N+1)

combinations = [(i, j, k)
                for i in I
                for j in J
                for k in K]

count = 0

for i, j, k in combinations:
    count = count + gcdlist(i, j, k)

print(count)

### FIXED CODE ###

n = int(input())

from math import gcd

y = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = gcd(i, j)
        for k in range(1, n + 1):
            y += gcd(x, k)

print(y)
### BUGGY CODE ###

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

def cmb2(n):
    return n * (n-1) // 2

nums = {}
for a in A:
    if a in nums:
        nums[a] += 1
    else:
        nums[a] = 1

nums_not_1 = {}
for key in nums:
    if nums[key] > 1:
        nums_not_1[key] = nums[key]

for k in range(N):
    ans = 0

    for key in nums_not_1:
        num = nums_not_1[key]
        if A[k] == key:
            num -= 1
        ans += cmb2(num)

    print(ans)


### FIXED CODE ###

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

def cmb2(n):
    return n * (n-1) // 2

nums = {}
for a in A:
    if a in nums:
        nums[a] += 1
    else:
        nums[a] = 1

sum = 0
for key in nums:
    num = nums[key]
    sum += cmb2(num)

for k in range(N):
    ans = sum - cmb2( nums[A[k]] ) + cmb2( nums[A[k]]-1 )
    print(ans)
### BUGGY CODE ###

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

for i in range(N):
  c = 0
  for j in range(N):
    if(A[i] == A[j]):
      c += 1
    if(c > 1):
      print("NO")
      exit()
print("YES")
   

### FIXED CODE ###

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

if (len(A) == len(set(A))):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
ans = 1
for i in range(n):
  ans *= li[i]
if(ans>1000000000000000000):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
ans = 1
flg = 0
for i in range(n):
  if flg==1 and li[i]!=0:
    continue
  elif li[i]==0:
    ans = 0
    break
  else:
    ans *= li[i]
  if(ans>1000000000000000000):
    flg = 1
if flg==1 and ans==0:
  print(ans)
elif flg==1:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
info=[]
for i in range(m):
    b,c=map(int,input().split())
    info.append([c,b])
a=sorted(a) #小さい順に
info=sorted(info,reverse=True)
b=[] #n枚まで、大きい順に変えられるやつを記録
total=0
def add(num,s):
    global b
    for i in range(s):
        b.append(num)
        
for i in range(m):
    total+=info[i][1]
    if n<=total:
        total-=info[i][1]
        add(info[i][0],n-total)
    add(info[i][0],info[i][1])
l=len(b)
ans=0
for i in range(n):
    if i<=l-1:
        ans+=max(a[i],b[i])
    else:
        ans+=a[i]
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
info=[]
for i in range(m):
    b,c=map(int,input().split())
    info.append([c,b])
a=sorted(a) #小さい順に
info=sorted(info,reverse=True)
b=[] #n枚まで、大きい順に変えられるやつを記録
total=0
def add(num,s):
    global b
    for i in range(s):
        b.append(num)
        
for i in range(m):
    total+=info[i][1]
    if n<=total:
        total-=info[i][1]
        add(info[i][0],n-total)
        break
    add(info[i][0],info[i][1])
l=len(b)
ans=0
for i in range(n):
    if i<=l-1:
        ans+=max(a[i],b[i])
    else:
        ans+=a[i]
print(ans)
### BUGGY CODE ###

n = int(input())
arr = []
cnt = 0

for i in range(n):
  s = sorted(list(input()))
  arr.append(s)

for i in range(n):
  for j in range(n):
    if i != j and arr[i] == arr[j]:      
      cnt += 1

print(cnt//2)

### FIXED CODE ###

import collections

from scipy.special import comb


n = int(input())
aa = []

for i in range(n):
  s = sorted(input())
  s = [''.join(s)]
  aa.append(*s)

cc = collections.Counter(aa)
c = [c[1] for c in cc.items() if c[1] >1]

ans = 0
for i in range(len(c)):
  ans += comb(c[i], 2, exact=True)
  

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

n = int(input())
a = [int(input()) for i in range(n)]
T = [False for i in range(n)]
tmp = 1
T[0] = True
count = 1
while True:
    tmp = a[tmp-1]
    if T[tmp -1]:
        print(-1)
        exit()
    if tmp == 2:
        print(count)
        break
    count+=1

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
T = [False for i in range(n)]
tmp = 1
T[0] = True
count = 1
while True:
    tmp = a[tmp-1]
    if T[tmp -1]:
        print(-1)
        exit()
    T[tmp-1] = True
    if tmp == 2:
        print(count)
        break
    count+=1
### BUGGY CODE ###

import itertools

n, k = map(int, input().split())

prices = list(map(int, input().split()))

ans = 999999999

for i in itertools.combinations(prices, k):
    ans = min(ans, sum(i))

print(ans)

### FIXED CODE ###

import itertools

n, k = map(int, input().split())

prices = list(map(int, input().split()))

prices = sorted(prices)

print(sum(prices[:k]))
### BUGGY CODE ###

n = int(input())
print(sum([i for i in range(n)]))

### FIXED CODE ###

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

n = int(input())
num = list(map(int,input().split()))
ans = 1
limit = 1000000000000000000
for i in range(n):
  ans *= num[i]
  if ans == 0:
    break
if ans>limit:
  print(-1)
else:
  print(ans)


### FIXED CODE ###

n = int(input())
num = list(map(int,input().split()))
ans = 1
limit = 1000000000000000000
if 0 in num:
  print(0)
else:
  for item in num:
    ans *= item
    if ans>limit:
      ans = -1
      break

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

N = int(input())
A = list(map(int, input().split()))
idx = [0]
for n in range(1, N+1):
    try:
        idx.append(A[sum(idx):].index(n))
    except:
        idx.append(len(A[sum(idx):]))
        break
if N == A[0] == 1:
    print(0)
elif (N == 1 and A[0] != 1) or (len(idx) == 2):
    print(-1)
else:
    print(sum(idx)-len(idx)+2)

### FIXED CODE ###

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

i = 1
ans = 0
for n in range(N):
  if i == A[n]:
    i += 1
  else:
    ans += 1
if ans == N:
  ans = -1
  
print(ans)
### BUGGY CODE ###

def multiplyList(myList) : 
      
    # Multiply elements one by one 
    result = 1
    for x in myList: 
         result = result * x  
    return result

n = int(input())
l = list(map(int, input().split()))
res = multiplyList(l)
if(res > 10**18):
    print(-1)
else:
    print(res)


### FIXED CODE ###

def multiplyList(myList) : 
      
    # Multiply elements one by one 
    result = 1
    for x in myList: 
        result = result * x
        if result == 0:
             return 0 
        if result > 10**18:
             return -1
    return result
 
n = int(input())
l = list(map(int, input().split()))
l.sort()
res = multiplyList(l)
print(res)
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
dp[1]=abs(h[1]-h[0])
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:  
    for i in range(2,N):
        dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-K),i))
        
        #dp[i]=np.min(list1)
         
print(dp[N-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array(list(map(int,input().split())))
dp=np.array([0 for i in range(N)])
dp[0]= 0
dp[1]=abs(h[1]-h[0])
if N<=K:
    dp[N-1]=abs(h[0]-h[N-1])
else:  
    for i in range(2,N):
      j=max(0,i-K)
      dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
      #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
C = []
for _ in range(M):
    b,c = map(int,input().split())
    for _ in range(b):
        C.append(c)
C.sort(reverse=True)
ans = []

for n in range(N+1):
    ans.append(sum(A[:n])+sum(C[:N-n]))

print(max(ans))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1], reverse=True)
 
ans = 0
b,c = BC.pop(0)
for i,a in enumerate(A):
    if b>=1:
        if c > a:
            ans += c
            b -= 1
        else:
            ans += a
    if b<=0:
        if len(BC)==0:
            ans += sum(A[i+1:])
            break
        else:
            b,c = BC.pop(0)
 
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
card = list(map(int,input().split()))
for i in range(M):
    card = sorted(card)
    B,C = map(int,input().split())
    for j in range(B):
        if card[j] <= C:
            card[j] = C
        else:
            break
print(sum(card))
    


### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
BC = [list(map(int,input().split())) for i in range(M)]
BC.sort(key = lambda x:-x[1])

index = 0
for i in range(len(BC)):
    for j in range(BC[i][0]):
        if index == len(A) or A[index] >= BC[i][1]:
            break

        else:
            A[index] = BC[i][1]
            index += 1

print(sum(A))
### BUGGY CODE ###

#import itertools
N = int(input())
S = input()
ans = 0

for i in range(0, N):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if j - i == k - j:
                continue
            if S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
                continue
            ans += 1
            #print(f"i={i},j={j},k={k}")
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
total = S.count('R') * S.count('G') * S.count('B')
cnt = 0

for i in range(0, N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        k = 2 * j - i
        if k > N - 1:
            break
        if S[i] == S[k] or S[j] == S[k]:
            continue
        cnt += 1
print(total - cnt)
### BUGGY CODE ###

import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

current_step, prev_step, two_prev_step = 0, 1, 0
for i in sorted(range(N), reverse=True):
    if i in A:
        prev_step, two_prev_step = 0, prev_step
        continue

    current_step = prev_step + two_prev_step
    prev_step, two_prev_step = current_step, prev_step

print(current_step % max_num)

### FIXED CODE ###

import sys
max_num = 1000000007
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(input()) for i in range(M)]

stairs = [1] * (N+1)
for i in A:
    stairs[i] = 0

for i in range(1, N):
    if stairs[i+1] != 0:
        stairs[i+1] = stairs[i] + stairs[i-1]
print(stairs[N] % max_num)
### BUGGY CODE ###

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
A=input_array()
MAX=10**18
ans=1

for i in A:
	ans*=i
if ans>MAX:
	print(-1)
else:
	print(ans)

### FIXED CODE ###

import sys

#入力:N(int:整数)
def input1():
	return int(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=input1()
A=input_array()
if 0 in A:
	print(0)
	sys.exit()
ans=1

for a in A:
	ans=ans*a
	if ans > 10**18:
		break

if ans > 10**18:
	print(-1)
else:
	print(ans)
### BUGGY CODE ###

import sys

# inputを高速化する。
input = sys.stdin.readline

# 入力
N, W = map(int, input().split())
lst_weight_value = [list(map(int, input().split())) for _ in range(N)]

def chmax(a, b):
    if a >= b:
        return a
    else:
        return b

dp = [0] * (W + 1)

for weight, value in lst_weight_value:
    for wk in range(W, weight-1, -1):
        tv = dp[wk - weight] + value
        if tv > dp[wk]:
            dp[wk] = tv

print(dp[-1])

### FIXED CODE ###


import sys

input = sys.stdin.readline

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

dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]

print(knapsack(N, W))
### BUGGY CODE ###

N=int(input())

ans=0
for i in range(1,N):
    ans+=i
print(ans)
    


### FIXED CODE ###

N=int(input())

ans=N*(N-1)//2
    
print(ans)
### BUGGY CODE ###

from collections import defaultdict

n,m = map(int,input().split())
uf = [-1]*n
def root(x):
    if uf[x] < 0:
        return x
    uf[x] = root(uf[x])
    return uf[x]
def unite(x,y):
    rx, ry = root(x), root(y)
    if rx==ry: return False
    if rx > ry: rx, ry = ry, rx
    uf[rx] += uf[ry]
    uf[ry] = rx
    return True

edge = [[-1]*n for i in range(n)]
edge = defaultdict(list)
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))
    unite(l-1, r-1)

dist = [0]*n
visited = [False]*n

from collections import deque

for i in range(n):
    if uf[i] >= 0:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")

### FIXED CODE ###

from collections import defaultdict, deque

n,m = map(int,input().split())
edge = [[] for i in range(n)]
for i in range(m):
    l,r,d = map(int, input().split())
    edge[l-1].append((r-1,d))
    edge[r-1].append((l-1,-d))

dist = [0]*n
visited = [False]*n

for i in range(n):
    if visited[i]:
        continue
    q = deque()
    q.append((i,0))
    while q:
        to, d = q.popleft()
        if visited[to]:
            if dist[to] != d:
                print("No")
                exit()
        else:
            visited[to] = True
            dist[to] = d
            for ind, j in edge[to]:
                q.append((ind,d+j))

print("Yes")
### BUGGY CODE ###

MAX_A = 10**6 + 1
is_prim = [True] * MAX_A
is_prim[0] = is_prim[1] = False
for i in range(2, MAX_A):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_A, i): is_prim[j] = False

# 素数と個数を求める
def factorize(n):
    res = []
    for i in range(2,n):
        if i*i > n: break
        if n%i: continue
        res += [[i,0]]
        while n%i == 0:
            n //= i
            res[-1][1] += 1
    if n != 1: res += [[n,1]]
    return res

def solve():
    prim = [i for i in range(1100) if is_prim[i]]
    C = [0] * MAX_A
    for a in A:
        for p,c in factorize(a): C[p] += 1
    max_c = max(C)
    if max_c <= 1: return 'pairwise'
    elif max_c <= n-1: return 'setwise'
    return 'not'

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        next_A_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            for j in range(i-d, i+d+1):
                if j >= 0 and j <= N-1:
                    next_A_list[j] += 1
        A_list = next_A_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""

def simulation(N, K, A_list):
    for k in range(min(K, 42)):
        #next_A_list = [0 for i in range(N)]
        imos_list = [0 for i in range(N)]
        for i in range(N):
            d = A_list[i]
            imos_list[max(i-d, 0)] += 1
            if i+d+1 <= N-1:
                imos_list[i+d+1] -= 1
            #for j in range(i-d, i+d+1):
            #    if j >= 0 and j <= N-1:
            #        next_A_list[j] += 1
        for i in range(1, N):
            imos_list[i] += imos_list[i-1]
        A_list = imos_list[:]
        #print(" ".join([ str(i).zfill(2) for i in A_list]))
    return A_list

def main():
    N, K = map(int, input().split())
    A_list = list(map(int, input().split()))
    print(" ".join([ str(i) for i in simulation(N, K, A_list)]))

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce (math.gcd, numbers)


k = int(input())
A=list()

for i in range(1,k+1):
  for j in range(1,k+1):
    for k in range(1,k+1):
        a=(gcd(i,j,k))
        A.append(a)
print(sum(A))



### FIXED CODE ###

from functools import reduce
from math import gcd
 
 
k = int(input())
B=list()
D=list()
 
for i in range(1,k+1):
  for j in range(1,k+1):
        a=[i,j]
        b = reduce(gcd,a)
        B.append(b)
 
for i in B:
    for k in range(1,k+1):
        c = [i,k]
        d = reduce(gcd,c)
        D.append(d)
print(sum(D))
### BUGGY CODE ###



s=input()
l=len(s)
mod = 10**9+7
dp=[[0]*13 for _ in range(l+1)]

dp[0][0]=1 #初期値設定
for i in range(l):
  if s[i]!="?":
    for k in range(13):
      dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
  else:
    for j in range(10):
      for k in range(13):
        dp[i+1][(k*10+j)%13]+=dp[i][k]
        
print(dp[-1][5]%mod)

### FIXED CODE ###

def main():
  s=input()
  l=len(s)
  mod = 10**9+7
  dp=[[0]*13 for _ in range(l+1)]
  dp[0][0]=1 #初期値設定
  for i in range(l):
    if s[i]!="?":
      for k in range(13):
        dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]%mod
    else:
      for j in range(10):
        for k in range(13):
          dp[i+1][(k*10+j)%13]+=dp[i][k]%mod

  print(dp[-1][5]%mod)

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

import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
#from bisect import bisect_left
from itertools import combinations
def main():
    n, *l = map(int, read().split())
    com = tuple(combinations(l, 3))
    r = 0
    for c in com:
        r += sum(c) > max(c) * 2
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from bisect import bisect_left
def main():
    n, *l = map(int, read().split())
    l.sort()
    r = n * (n - 1) * (n - 2) // 6
    for i1 in range(n - 2):
        for i2 in range(i1 + 1, n - 1):
            r -= (n - bisect_left(l, l[i1] + l[i2]))
    print(r)

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

# -*- coding: utf-8
N = 0
C = []
S = []
F = []

# i駅での到着時間を指定すると、次の乗車時間が帰ってくる
def getNextTrain(i, time):
  t = S[i]
  while(1):
    if time <= 0:
      break
    if t >= time:
      break
    t += F[i]

  return t

# 入力部分
N = int(raw_input())
for i in range(N-1):
  c, s, f = map(int, raw_input().split())
  C.append(c)
  S.append(s)
  F.append(f)

# 処理部分
for k in range(N):
  arrive = 0
  for p in range(k, N-1): 
    # p駅から出発して
    arrive = getNextTrain(p, arrive)
    #print str(arrive) + '-> ' + str(p),
    arrive += C[p]
    #print '->' + str(arrive)
  print arrive

# 出力部分

### FIXED CODE ###

# -*- coding: utf-8
N = 0
C = []
S = []
F = []

# i駅での到着時間を指定すると、次の乗車時間が帰ってくる
def getNextTrain(i, time):
  # t = S[i]
  if time <= S[i]:
    return S[i]
  else:
    n = time / F[i]
    m = time % F[i]
    t = F[i] * n
    if m != 0:
      t += F[i]
    # while(1):
    #   if t >= time:
    #     break
    #   t += F[i]

    return t

# 入力部分
N = int(raw_input())
for i in range(N-1):
  c, s, f = map(int, raw_input().split())
  C.append(c)
  S.append(s)
  F.append(f)

# 処理部分
for k in range(N):
  arrive = 0
  for p in range(k, N-1): 
    # p駅から出発して
    arrive = getNextTrain(p, arrive)
    #print str(arrive) + '-> ' + str(p),
    arrive += C[p]
    #print '->' + str(arrive)
  print arrive

# 出力部分
### BUGGY CODE ###

def main():
    N,K=map(int,open(0).read().split())
    keta=1
    flag=0
    while flag==0:
        if pow(K,keta)<=N and pow(K,keta+1)>N:
            print(keta+1)
            return
        keta= keta+1
main()

### FIXED CODE ###

def Base_10_to_n(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out
    
def main():
    N,K=map(int,input().split())
    print(len(Base_10_to_n(N,K)))
main()