Harryxun/stf_run huggingface dataset:
# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
from collections import deque
from decorator import stop_watch
import math


@stop_watch
def solve(N, K, As):
    ans = max(As)
    l, r = 1, ans
    for _ in range(30):
        m = (l + r) // 2
        cnt = 0
        for A in As:
            cnt += math.ceil(A / m) - 1
        if cnt <= K:
            ans = min(ans, m)
            r = m - 1
        else:
            l = m + 1
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(N, K, As)


### FIXED CODE ###

# 解説を参考に作成

# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, K, As):
    ans = max(As)
    l, r = 1, ans
    for _ in range(30):
        m = (l + r) // 2
        if m <= 0:
            break
        cnt = 0
        for A in As:
            cnt += math.ceil(A / m) - 1
        if cnt <= K:
            ans = min(ans, m)
            r = m - 1
        else:
            l = m + 1
    print(ans)


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, K = map(int, input().split())
    As = [int(i) for i in input().split()]
    # Bs = [int(i) for i in input().split()]
    solve(N, K, As)
import math

A,B = (int(x) for x in input().split())

if A==B:
    print(A)
else:
    ans = 0
    if A*2 <= B and B > 4:
        n = int(math.log2(A))
        m = int(math.log2(B))

        if n <= 1:
            for i in range(A,4):
                ans = ans ^ i
            A=4
            n=2
            
        if 2**n != A:
            n += 1
            ans = A
            for i in range(A+1,2**n):
                ans = ans ^ i

        for i in range(2**m,B+1):
            ans = ans ^ i

    else:
        for i in range(A,B+1):
            ans = ans ^ i

    print(ans)

### FIXED CODE ###

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

if A == B:
    print(A)
elif B - A == 1:
    print(A^B)
else:
    ans = 0
    if A % 2 != 0:
        ans ^= A
        A += 1
    if B % 2 == 0:
        ans ^= B
        B -= 1
    ans ^= ((B-A+1)//2)%2

    print(ans)
import sys
x = input()
x = x * x * x
print　(x)

### FIXED CODE ###

import sys
x = int(input())
x = x**3
print (x)
N, K = map(int, input().split())
S = str(input())
ans = []
for i in range(0, K-1):
  ans.append(S[i])
ans.append(S[K].lower())
for j in range(K+1,N):
  ans.append(S[j])
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
S = str(input())
ans = ""
for i in range(N):
  if i == K-1:
    ans += S[i].lower()
  else:
    ans += S[i]
print(ans)
SUM = 0
N = input()
for num in range(N):
	P[num] = input()

P.sort(reverse=True)
P[0] = P[0]/2

for num in range(N):
	SUM += P[num]

print(SUM)

### FIXED CODE ###

S = 0
N = int(input())
P=[]
for num in range(N):
	P.append(int(input()))

P.sort(reverse=True, key=int)
P[0] = P[0]//2

for num in range(N):
	S += P[num]

print(S)
import sysinput = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(s) + 10)] for _ in range(len(s) + 10)]

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ' '
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i][l] == dp[i - 1][l - 1] + 1:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
        elif dp[i-1][l] == dp[i][l]:
            i -= 1
        elif dp[i][l-1] == dp[i][l]:
            l -= 1
    print(ans)


### FIXED CODE ###

import sys
import math
from collections import deque
import copy

input = sys.stdin.readline

s = input()
t = input()

dp = [[0 for _ in range(len(t) + 10)] for _ in range(len(s) + 10)]

for i in range(1, len(s)):
    for l in range(1, len(t)):
        if s[i - 1] == t[l - 1]:
            dp[i][l] = max(max(dp[i - 1][l - 1] + 1, dp[i][l - 1]), dp[i - 1][l])
        else:
            dp[i][l] = max(dp[i][l - 1], dp[i - 1][l])
length = dp[len(s) - 1][len(t) - 1]
if length == 0:
    print("")
else:
    ans = ''
    i = len(s) - 1
    l = len(t) - 1
    while i > 0 and l > 0:
        if dp[i-1][l] == dp[i][l] and i >= 1:
            i -= 1
        elif dp[i][l-1] == dp[i][l] and l >= 1:
            l -= 1
        else:
            ans = s[i - 1] + ans
            i -= 1
            l -= 1
    print(ans)
def test():
    nums = list(map(int, list(input())))
    for i in range(2 ** 3):
        ans = nums[0]
        res = '{}'.format(nums[0])
        for j in range(3):
            if (i >> j) & 1:
                ans += nums[j+1]
                res += '+{}'.format(nums[j+1])
            else:
                ans -= nums[j+1]
                res += '-{}'.format(nums[j+1])
        if ans == 7:
            print('{}=7'.format(res))
            exit(1)

if __name__ == '__main__':
    test()

### FIXED CODE ###

def test():
    nums = list(map(int, list(input())))
    end = False
    for i in range(2 ** 3):
        ans = nums[0]
        res = '{}'.format(nums[0])
        for j in range(3):
            if (i >> j) & 1:
                ans += nums[j+1]
                res += '+{}'.format(nums[j+1])
            else:
                ans -= nums[j+1]
                res += '-{}'.format(nums[j+1])
        if ans == 7:
            end = True
            break
    print('{}=7'.format(res))

if __name__ == '__main__':
    test()
Cube = [int(i) for i in input().split(" ")]
# 一番長い辺で切れば断面の数は最小
L = max(Cube)
A,B = map(int,[i for i in Cube if i!=L])

print(abs((A*B*(L//2))-(A*B*(L-(L//2)))))

### FIXED CODE ###

Cube = [int(i) for i in input().split(" ")]
# 一番長い辺で切れば断面の数は最小
L = max(Cube)
plane = [i for i in Cube if i!=L]
if len(plane)==0:
    A = L
    B = L
elif len(plane)==1:
    A = plane[0]
    B = L
else:
    A,B = map(int,plane)
print(abs((A*B*(L//2))-(A*B*(L-(L//2)))))
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines

from collections import deque

def main():

    lines = input()
    n, k = list(map(int, lines[0].split()))
    a = [[] for i in range(n+1)]

    for i in range(1, n):
        r, l = list(map(int, lines[i].split()))
        a[r].append(l)
        a[l].append(r)

    que = deque()
    que.append(1)
    colors = [-1] * (n+1)
    colors[1] = k
    ways = k

    def bfs(que, height):
        if que:
            nonlocal ways
            p = que.popleft()
            # root no toki
            if height == 0:
                now_color = k
                for son in a[p]:
                    now_color -= 1
                    ways = (ways * now_color) % 1_000_000_007
                    colors[son] = now_color
                    que.append(son)
            else:
                now_color = k-1
                for son in a[p]:
                    if colors[son] < 0:
                        now_color -= 1
                        colors[son] = now_color
                        ways = (ways * now_color) % 1_000_000_007
                        que.append(son)

        bfs(que, height+1)

    bfs(que, 0)

    print(ways)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readlines

from collections import deque

def main():

    lines = input()
    n, k = list(map(int, lines[0].split()))
    a = [[] for i in range(n+1)]

    for i in range(1, n):
        r, l = list(map(int, lines[i].split()))
        a[r].append(l)
        a[l].append(r)

    que = deque()
    que.append(1)
    colors = [-1] * (n+1)
    colors[1] = k
    ways = k

    while que:
        p = que.popleft()
        # root no toki
        if p == 1:
            now_color = k
            for son in a[p]:
                now_color -= 1
                ways = (ways * now_color) % 1_000_000_007
                colors[son] = now_color
                que.append(son)
        else:
            now_color = k-1
            for son in a[p]:
                if colors[son] < 0:
                    now_color -= 1
                    colors[son] = now_color
                    ways = (ways * now_color) % 1_000_000_007
                    que.append(son)

    print(ways)

main()
a,b = (4,5)

print(a*b)
print(2a+2b)


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
a,b = int(input())
num = a*b
if num % 2 ==0:
    print("Even")
else:
     print("Odd")  

### FIXED CODE ###

a,b=map(int,input().split())
if(a*b % 2 == 0):
  print('Even')
else:
  print('Odd')
import collections
import itertools
import functools
import math

s = set([])
if __name__ == "__main__":
    n = math.factorial(int(input()))
    prims = (n + 1) * [0]
    p = 2
    while n >= p*p:
        if n % p == 0:
            prims[p] += 1
            n = n // p
        else:
            p += 1
    prims[n] += 1
    print(functools.reduce(lambda x, y: x * (y + 1), prims, 1))

### FIXED CODE ###

import collections
import itertools
import functools
import math

s = set([])
if __name__ == "__main__":
    n = int(input())
    m = math.factorial(n)
    res = 1
    for j in range(2, n + 1):
        tmp = 1
        while m % j == 0:
            m = m//j
            tmp += 1
        res *= tmp
    print(res % (10**9 + 7))
import sys
from math import factorial
from scipy.misc import comb

def ncr(n, r, p): 
    return comb(n,r,exact=True) % p 

def check(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    n = x - y
    x -= 2 * n

    if (x + y) % 3 == 0:
        return True
    else:
        return False
    

# Read
line = sys.stdin.readlines()[0]
X, Y = map(int,line.split(' '))

# if not check(X, Y):
#     print(0)
#     exit(0)

m = int(1/3 * (2*Y - X))
n = int(Y - 2 * m)

if n < 0 or m < 0:
    print(0)
else:
    p = m if m < n else n
    print(ncr(n+m, p))


### FIXED CODE ###

import sys

for line in sys.stdin:
    r = int(line.rstrip())
    print(r*r)
n,k = int(input()).split()
p = list(int(input()).split())
 
p1 = sorted(p)
 
temp = 0
for i in p[k] :
  temp += i
print(temp)

### FIXED CODE ###

n,k = map(int , input().split( ))
p = list(map(int , input().split( )))
 
p.sort()
 
temp = 0
for i in p[:k] :
  temp += i
print(temp)
def main(x: int, y: int):
    award: int = 0

    if (x and y) == 1:
        award += 400000

    for i in [x, y]:
        if i == 1:
            award += 300000
        elif i == 2:
            award += 200000
        elif i == 3:
            award += 100000

    print(award)


if __name__ == "__main__":
    x, y = map(int, input().split())

    main(x, y)


### FIXED CODE ###

def main(x: int, y: int):
    award = 0

    if x == y == 1:
        award += 400000

    for i in [x, y]:
        if i == 1:
            award += 300000
        elif i == 2:
            award += 200000
        elif i == 3:
            award += 100000

    print(award)


if __name__ == "__main__":
    x, y = map(int, input().split())

    main(x, y)
import fraction
N, X = [int(i) for i in input().split()]
x = [int(x) for x in input().split()]
x.append(X)
x.sort()

distance = []
for i,xe in enumerate(x):
    if i is not 0:
        distance.append(xe - x[i-1])

print(fraction.gcd(distance))

### FIXED CODE ###

from functools import reduce
import fractions
N, X = [int(i) for i in input().split()]
x = [int(x) for x in input().split()]
x.append(X)
x.sort()

distance = []
for i,xe in enumerate(x):
    if i is not 0:
        distance.append(xe - x[i-1])

print(reduce(fractions.gcd, distance))
n = int(input())

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

for i in range(n):
    print(A.count(i+1))

### FIXED CODE ###

import math

r = int(input())

print(2*math.pi*r)
import numpy as np

n, w = map(int, input().split())
l = [list(map(int,input().split())) for i in range(n)]


dp = np.zeros((n + 1, w + 1), dtype=np.int64)

for i in range(n):
    tmp = np.zeros(w + 1, dtype=int)
    tmp[l[i][0]:] = dp[i][:-l[i][0]] + l[i][1]
    dp[i + 1] = np.maximum(dp[i], tmp)
    
print(dp[n][w])

### FIXED CODE ###

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

items = [list(map(int,input().split())) for i in range(n)]

dp = [[0]*(w+1) for i in range(n+1)]

for i in range(n):
    for j in range(w+1):
        if j >= items[i][0]:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-items[i][0]] + items[i][1])
            
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[n][w])
import collections


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n = int(input())
sieve = eratosthenes(n)
primes = [i for i in range(n + 1) if sieve[i]]
counter = collections.Counter()
for i in range(2, n + 1):
    for p in primes:
        while i % p == 0:
            counter[p] += 1
            i //= p
        if i == 1:
            break

counter2 = collections.Counter()
for i in [2, 4, 14, 24, 74]:
    for p in primes:
        if counter[p] >= i:
            counter2[i] += 1

c0 = counter2[74]
c1 = counter2[24] * (counter2[2] - 1)
c2 = counter2[14] * (counter2[4] - 1)
c3 = (counter2[4] * (counter2[4] - 1) * (counter2[2] - 2)) // 2
print(c0 + c1 + c2 + c3)

### FIXED CODE ###

import collections


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False
    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


n = int(input())
sieve = eratosthenes(n)
primes = [i for i in range(n + 1) if sieve[i]]
counter = collections.Counter()
for i in range(2, n + 1):
    for p in primes:
        while i % p == 0:
            counter[p] += 1
            i //= p
        if i == 1:
            break

counter2 = collections.Counter()
for i in [2, 4, 14, 24, 74]:
    for p in primes:
        if counter[p] >= i:
            counter2[i] += 1

c0 = counter2[74]
c1 = counter2[24] * (counter2[2] - 1)
c2 = counter2[14] * (counter2[4] - 1)
c3 = (counter2[4] * (counter2[4] - 1) * (counter2[2] - 2)) // 2
print(c0 + c1 + c2 + c3)
N, K = map(int,(input().split()))
H = list(map(int,(input().split())))
atk=0
for i in range(K):
  H.remove(max(H))

for j in range(len(H)):
  atk += H[j]
print(atk)

### FIXED CODE ###

N, K = map(int,(input().split()))
H = list(map(int,(input().split())))
atk=0
H.sort(reverse=True)
del H[0:K]

atk=sum(H)
print(atk)
list = list(map(int, input().split())) 
hajime=list[0]
kaisuu=list[1]
hohaba=list[2]
if hajime>=0:
  ayumi=hajime//hohaba
  nokori=kaisuu-ayumi
  kouho_1=hajime-hohaba*kaisuu
  kouho_2=hajime-hohaba*ayumi
  kouho_3=-hajime+hohaba*(ayumi+1)
  if kaisuu=<ayumi:
    print(kouho_1)
  else:
    if nokori%2==0:
      print(kouho_2)
    else:
      print(kouho_3)
      
if hajime<0:  
  ayumi=-hajime//hohaba
  nokori=kaisuu-ayumi
  kouho_1=hajime+hohaba*kaisuu
  kouho_2=hajime+hohaba*ayumi
  kouho_3=-hajime-hohaba*(ayumi+1)
  if kaisuu=<hohaba:
    
    print(kouho_1)  else:
    if nokori%2==0:
      print(kouho_2)
    else:
      print(-kouho_3)

### FIXED CODE ###

list = list(map(int, input().split())) 
hajime=list[0]
kaisuu=list[1]
hohaba=list[2]
if hajime>=0:
  ayumi=hajime//hohaba
  nokori=kaisuu-ayumi
  kouho_1=hajime-hohaba*kaisuu
  kouho_2=hajime-hohaba*ayumi
  kouho_3=hajime-hohaba*(ayumi+1)
 
  
  
  if kaisuu <= ayumi:
    print(kouho_1)
  else:
    if nokori%2==0:
      print(kouho_2)
    else:
      print(-kouho_3)
      
if hajime<0:  
  ayumi=-hajime//hohaba
  nokori=kaisuu-ayumi
  kouho_1=hajime+hohaba*kaisuu
  kouho_2=hajime+hohaba*ayumi
  kouho_3=hajime+hohaba*(ayumi+1)
  if kaisuu<=ayumi:
    
    print(-kouho_1)  
  else:
    if nokori%2==0:
      print(-kouho_2)
    else:
      print(kouho_3)
try:
    while True:  
        n = raw_input().strip().upper()
        oxList = raw_input().strip().lower()
        ans = -1
        for s0 in ["S", "W"]:
            for s1 in ["S","W"]:
                swList = [0]*int(n)
                swList[0] = s0
                swList[1] = s1
                for i in range(2, int(n)):
                    nextAnimal = findNextAnimal(oxList, swList, i-1)
                    swList[i] = nextAnimal
                    flag = checkList(oxList, swList)
                    if(flag == 1):
                        ans = ""
                        for s in swList:
                            ans += s
        print ans
                        
except EOFError:
    pass

### FIXED CODE ###

def findNextAnimal(oxList, swList, index):
    nextAns = oxList[index]
    before = swList[index-1]
    animal = swList[index]
    nextAnimal = ""
    if(nextAns == "o" and before == "S" and animal == "S"):
        nextAnimal = "S"
    elif(nextAns == "o" and before == "S" and animal == "W"):
        nextAnimal = "W"
    elif(nextAns == "o" and before == "W" and animal == "S"):
        nextAnimal = "W"
    elif(nextAns == "o" and before == "W" and animal == "W"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "S" and animal == "S"):
        nextAnimal = "W"
    elif(nextAns == "x" and before == "S" and animal == "W"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "W" and animal == "S"):
        nextAnimal = "S"
    elif(nextAns == "x" and before == "W" and animal == "W"):
        nextAnimal = "W"
    return nextAnimal

def checkList(oxList, swList):
    ans = 0
    if(swList[-1] == "S"):
        if(oxList[-1] == "x" and swList[-2] != swList[0]):
            ans = 1
        elif(oxList[-1] == "o" and swList[-2] == swList[0]):
            ans = 1
    elif(swList[-1] == "W"):
        if(oxList[-1] == "x" and swList[-2] == swList[0]):
            ans = 1
        elif(oxList[-1] == "o" and swList[-2] != swList[0]):
            ans = 1
            
    ans2 = 0    
    if(swList[0] == "S"):
        if(oxList[0] == "x" and swList[1] != swList[-1]):
            ans2 = 1
        elif(oxList[0] == "o" and swList[1] == swList[-1]):
            ans2 = 1
    elif(swList[0] == "W"):
        if(oxList[0] == "x" and swList[1] == swList[-1]):
            ans2 = 1
        elif(oxList[0] == "o" and swList[1] != swList[-1]):
            ans2 = 1
    
    return ans*ans2

try:
    while True:  
        n = raw_input().strip().upper()
        oxList = raw_input().strip().lower()
        ans = -1
        for s0 in ["S", "W"]:
            for s1 in ["S","W"]:
                swList = [0]*int(n)
                swList[0] = s0
                swList[1] = s1
                for i in range(2, int(n)):
                    nextAnimal = findNextAnimal(oxList, swList, i-1)
                    swList[i] = nextAnimal
                    flag = checkList(oxList, swList)
                    if(flag == 1):
                        ans = ""
                        for s in swList:
                            ans += s
        print ans
                        
except EOFError:
    pass
#encoding=utf-8
import sys

printf = sys.stdout.write
ans = []
def gcd(a,b):
    if a == b:
        return a
    else:
        return gcd(b, abs(a-b))

def lcm(a,b,g):
    return a*b/g

if __name__ == "__main__":
    for i in sys.stdin:
        a,b = map(int, i.split())
        ans.append(gcd(a,b))
        ans.append(lcm(a,b,gcd(a,b)))
        
    for i in xrange(0,len(ans)  - 2,2):
        printf(str(ans[i]) + " " + str(ans[i + 1]) + "\n")
        
    printf(str(ans[len(ans) - 2]) + " " + str(ans[len(ans) - 1]))

### FIXED CODE ###

import sys
for i in sys.stdin:
    m, n = map(int, i.split())
    t1, t2 = m, n
    while True:
        if m % n == 0:
            break
        m, n = n, m % n
    a = n
    b = (t1/ a) * t2
    print("{} {}".format(a, b))
a , b = map(int(),input().split())
 
X = 0
Y = 0

for i in b:
  X = 'X' + 'a'
  
for v in a:
  Y = 'Y' + 'b'
  
if 'X' <= 'Y':
  print('X')
else:
  print('Y')

### FIXED CODE ###

a , b =input().split()
 
if a <= b:
    print(a*int(b))
else:
	print(b*int(a))
alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)

print('None')


### FIXED CODE ###

alphabets = [i for i in range(ord('a'), ord('z') + 1)]
lists = [ord(i) for i in input()]
lists=list(set(lists))
lists.sort()
for i in range(len(alphabets)):
    if i+1>=len(lists) and i!=25:
        if alphabets[i] == lists[i]:
            print(chr(alphabets[i+1]))
            exit(0)
    if alphabets[i]!=lists[i]:
        print(chr(alphabets[i]))
        exit(0)


print('None')
T = list(input())
for i in range(len(T)):
  if i > 0 and T[i] == "?" and T[i-1] == "P":
    T[i] = "D"
  elif i <= len(T) -1 and T[i] == "?" and (T[i+1] == "D" or T[i+1] == "?"):
    T[i] = "P"
  elif T[i] == "?":
    T[i] = "D"
print("".join(T))

### FIXED CODE ###

T = list(input())
if len(T) == 1:
  if T[0] == "?":
    print("D")
  else:
    print("".join(T))
else:
  for i in range(len(T)):
    if i > 0 and T[i] == "?" and T[i-1] == "P":
      T[i] = "D"
    elif i < len(T) -1 and T[i] == "?" and (T[i+1] == "D" or T[i+1] == "?"):
      T[i] = "P"
    elif T[i] == "?":
      T[i] = "D"
  print("".join(T))
import sys
sys.setrecursionlimit(10030)
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
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(e) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print(f(k,0)-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10070)
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
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(max(2,e)) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print((f(k,0)-1)%MOD)