Find the number of integers between 1 and N (inclusive) that contains exactly K non-zero digits when written in base ten.

-----Constraints-----
 - 1 \leq N < 10^{100}
 - 1 \leq K \leq 3

-----Input-----
Input is given from Standard Input in the following format:
N
K

-----Output-----
Print the count.

-----Sample Input-----
100
1

-----Sample Output-----
19

The following 19 integers satisfy the condition:
 - 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100

Difficulty: interview

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10000)

n = input()
k = int(input())
m = {}


def doit(n, k):
    if len(n) == 0:
        return k == 0
    d = int(n[0])
    if (n, k) not in m:
        ret = 0
        for i in range(d + 1):
            if i == d:
                ret += doit(n[1:], k - 1 if i > 0 else k)
            else:
                ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
        m[(n, k)] = ret
    return m[(n, k)]


print((doit(n, k)))


import numpy as np


def solve(S, N, K):
    dp = np.zeros((N + 1, 2, K + 1), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(K + 1):
                for l in range(10 if is_less else S[i] + 1):
                    k_ = k + (l > 0)
                    if k_ > K:
                        continue
                    is_less_ = is_less or l < S[i]
                    dp[i + 1][int(is_less_)][k_] += dp[i][is_less][k]
    return dp[N][0][K] + dp[N][1][K]


S = np.array([c for c in input()], dtype=np.int64)
N = len(S)
K = int(input())
print((solve(S, N, K)))


'''桁dpの典型問題　n以下の非負整数について条件を満たすものの個数を求める
nより小さいことが確定しているかどうかで場合分けをし、遷移を書いて式にすれば良い。'''
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ns()
k = ni()
dp = [[[0]*2 for _ in range(k+1)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    x = int(n[i])
    for j in range(k):
        dp[i+1][j+1][1] += dp[i][j][1]*9
        dp[i+1][j][1] += dp[i][j][1]
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)
            dp[i+1][j+1][0] += dp[i][j][0]
        else:
            dp[i+1][j][0] += dp[i][j][0]
    dp[i+1][k][1] += dp[i][k][1]
    dp[i+1][k][x>0] += dp[i][k][0]
    #インデックスjのところが拾いきれていないので拾う
    #iとkはぶつかっていないので普通に二重ループでかける
print(sum(dp[len(n)][k]))

# coding: utf-8
# Your code here!
n = int(input())
K = int(input())

def make_list(n):
    N = []
    while(n>0):
        N.append(n%10)
        n = n //10
    N.reverse()
    return N

N = make_list(n)
m = len(N)
dp = [[[ 0 for k in range(K+1)] for j in range(2)] for i in range(m)]  
#dp[i][j][k]:上からi桁目で、j=0:nのi桁目までと等しくない,j=1:等しい、0でない数字がk個であるものの個数
dp[0][0][0] =  1 #x = 0
dp[0][0][1] = N[0] - 1 #0 < x < N[0]
dp[0][1][0] = 0
dp[0][1][1] = 1 #x = N[0]

for i in range(1,m):
    dp[i][0][0] = 1 #i桁目まで全部0
    #dp[i][1][0] = 0:最上位が0はありえない
    for k in range(1,K+1):
        if N[i] == 0:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k]
            dp[i][1][k] = dp[i-1][1][k]
        else:
            dp[i][0][k] = dp[i-1][0][k-1] * 9 + dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][1][k-1] * (N[i] - 1)
            dp[i][1][k] = dp[i-1][1][k-1]
#print(dp)
print((dp[m-1][1][K] + dp[m-1][0][K]))


n=input()
k=int(input())
l=len(n)
dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=dp[b][j][1]*9
  dp[i][1][1]+=9
print((dp[l-1][k][0]+dp[l-1][k][1]))
           


N = int(input())
K = int(input())
S = str(N)
L = len(S)
# dp0 N未満であることが未確定
# dp1 N未満であることが確定
# [上から何桁][0以外を選んだ回数]
dp0 = [[0 for _ in range(5)] for _ in range(L+1)]
dp1 = [[0 for _ in range(5)] for _ in range(L+1)]
dp0[0][0] = 1
dp0[0][1] = 0
for i in range(L):
    D = int(S[i])
    for j in range(4):
        if D > 0:
            # 0を選ぶ
            dp1[i+1][j] += dp1[i][j] + dp0[i][j]
            # 1~9を選ぶ
            dp0[i+1][j+1] += dp0[i][j]
            dp1[i+1][j+1] += dp1[i][j]*9 + dp0[i][j]*(D-1)
        else:
            # 0を選ぶ
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            # 1~9を選ぶ
            dp1[i+1][j+1] += dp1[i][j]*9
print((dp0[L][K]+dp1[L][K]))


from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    # n以下で0でないものがちょうどk個ある数字の個数
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q, r = divmod(n, 10)
    ret = 0
    if k >= 1:
        ret += F(q, k-1) * r
        ret += F(q-1, k-1) * (9-r)
    ret += F(q, k)
    return ret

print(F(n, k))

import math

#-桁dpなる書き方に挑戦-#
#-dp[k][j][i] 先頭からi桁目まで決めたときに,
    #- 0でない要素をj個使っていて、k=0 小さいことが確定していない , k=1 確定

def solve(sN):
    dp = [[[0]*105 for _ in range(4)] for _ in range(2) ] #余分に取っておく。あとでlen(N)の要素を取り出し
    #初期条件
    dp[0][0][0]=1 #なにも決めていな状態。空集合。一致
    for i in range(len(sN)):
        for j in range(4):
            for k in range(2):
                nd = int(sN[i])#sNの今の桁をnd。これから決める桁数字をdとする
                for d in range(10):
                    ni = i+1;nj=j;nk=k
                    if d != 0: #dが0でないならnjを１つ足す
                        nj +=1
                    if nj > K:#使える0以外の数字の個数を超えていたらだめ
                        continue
                    if k ==0:#これまでの桁が一致している。
                        if d > nd:#数字が超えるからだめ
                            continue
                        if d < nd:#小さいなら、以降小さくなることが確定
                            nk = 1
                    dp[nk][nj][ni]+=dp[k][j][i]
    ans = dp[0][K][len(sN)]+dp[1][K][len(sN)]#小さいものが確定＆一致
    return ans

sN = input()
K = int(input())
lenN = len(sN)
ans = solve(sN)
print(ans)


import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ins()
K = ini()


def solve():
    M = len(N)
    dp_eq = [[0 for _ in range(K + 1)] for _ in range(M)]
    dp_less = [[0 for _ in range(K + 1)] for _ in range(M)]

    dp_eq[0][K - 1] = 1
    dp_less[0][K] = 1
    dp_less[0][K - 1] = ord(N[0]) - ord("0") - 1
    for i in range(1, M):
        is_zero = N[i] == "0"
        for k in range(K + 1):
            if is_zero:
                dp_eq[i][k] = dp_eq[i - 1][k]
            elif k < K:
                dp_eq[i][k] = dp_eq[i - 1][k + 1]

            dp_less[i][k] = dp_less[i - 1][k]
            if k < K:
                dp_less[i][k] += dp_less[i - 1][k + 1] * 9
            if not is_zero:
                dp_less[i][k] += dp_eq[i - 1][k]
                if k < K:
                    dp_less[i][k] += dp_eq[i - 1][k + 1] * (ord(N[i]) - ord("0") - 1)
    return dp_eq[M - 1][0] + dp_less[M - 1][0]


print(solve())


N = input()
K = int(input())

if len(N) < K:
  print(0)
  return

ans = [1, int(N[-1]), 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = a
print(ans[K])

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return list(map(int, input().split()))
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10


N = list(map(int, list(input())))
K = INT()

n = len(N)

if n < K:
	print((0))
	return

dp = [[[0, 0] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(n):
	for j in range(n):
		for k in range(2):
			for x in range(10):
				ni, nj, nk = i+1, j, k
				if x != 0:
					nj += 1
				if k == 0:
					if N[i] < x:
						continue
					elif x < N[i]:
						nk = 1
				dp[ni][nj][nk] += dp[i][j][k]

ans = 0

print((dp[n][K][0] + dp[n][K][1]))


N = input()
k = int(input())
# 桁数
length = len(N)
# dp[ 決めた桁数 ][ 未満フラグ ][0以外の個数] := 総数
dp = [[[0 for _ in range(k+1)] for _ in range(2)] for _ in range(length+1)]
dp[0][0][0] = 1

for i in range(length):
    max_digit = int(N[i])
    
    for k_num in range(k+1):
        for flag_less in range(2):
            range_digit = 9 if flag_less else max_digit
            for d in range(range_digit+1):
                flag_less_next = 0
                if flag_less==1 or d < max_digit:
                    flag_less_next = 1
                # 0 の時は0以外の個数は増えない
                k_num_next = k_num
                if d != 0:
                    k_num_next = k_num + 1
                    if k_num_next > k:
                        continue
                dp[i+1][flag_less_next][k_num_next] += dp[i][flag_less][k_num]
print((dp[length][0][k]+dp[length][1][k]))


n = input()
k = int(input())
l = len(n)

def k2(l, n):
    ans = 81 * (l - 1) * (l - 2) // 2
    ans += (int(n[0]) - 1) * 9 * (l - 1)
    for i, s in enumerate(n[1:]):
        if s == "0":
            continue
        ans += int(s)
        ans += max((l - i - 2), 0) * 9
        break
    return ans

if k == 1:
    ans = (l - 1) * 9 + int(n[0])
elif k == 2:
    if l == 1:
        print(0)
        return
    ans = k2(l, n)
else:
    if l < 3:
        print(0)
        return
    ans = 9 ** 3 * (l - 1) * (l - 2) * (l - 3) // 6
    ans += (int(n[0]) - 1) * 81 * (l - 1) * (l - 2) // 2
    n = n[1:]
    n = str(int(n))
    ans += k2(len(n), n)
print(ans)

def nCkpow(n,k):
    if n<k:
        return 0
    y=1
    for i in range(k):
        y*=n-i
        y//=i+1
        y*=9
    return y
def f(s,m,k):
    #print(m,k)
    if len(s)-m<k:
        return 0
    if  k==0:
        return 1
    if s[m]=='0':
        return f(s,m+1,k)
    l=len(s)-m
    y=nCkpow(l-1,k)
    y+=(int(s[m])-1)*nCkpow(l-1,k-1)
    return y+f(s,m+1,k-1)
N=input()
K=int(input())
print(f(N,0,K))

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k == 0: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ
        else: # k >= 1
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]

#print(dp)
print((dp[m][0][K] + dp[m][1][K]))


s=input()
n=len(s)

K=int(input())

dp=[[[0] * 5 for _ in range(2)] for _ in range(n+1)]
dp[0][0][0]=1

for i in range(n):
    ni= int(s[i])

    for k in range(4):
            # smaller 1 -> 全部OK
            dp[i + 1][1][k + 1] += dp[i][1][k] * 9;  
            dp[i + 1][1][k] += dp[i][1][k];  

            # smaller 0,next smaller 1 -> nowより小さいのを全部
            # 次の桁からsmallerであるためにはN＜ni であることが必要で
            # Nは0より大きい必要がある。（0より小さいものがない＝確定しない
            if (ni > 0):
                dp[i + 1][1][k + 1] += dp[i][0][k] * (ni - 1)
                dp[i + 1][1][k] += dp[i][0][k]
                
            # smaller 0,next smaller 0 -> nowだけ
            if (ni > 0) :
                dp[i + 1][0][k + 1] = dp[i][0][k]
            else:
                dp[i + 1][0][k] = dp[i][0][k]

ans=dp[n][0][K] + dp[n][1][K]
print(ans)

sN = input()
K = int(input())
N = int(sN)


def run():
    dp = [[[0] * 4 for _ in range(2)] for _ in range(len(sN) + 1)]
    dp[0][0][0] = 1

    for i in range(len(sN)):
        for j in range(2):
            # j=0 : 現在の桁まで数字が同じ
            # j=1 : すでに小さい数値とわかっている

            # limには次の桁の数字の最大値を代入する
            lim = 9 if j == 1 else (ord(sN[i]) - ord('0'))
            for k in range(lim + 1):
                for l in range(4):
                    nl = l + int(k > 0)
                    if nl >= 4: continue
                    dp[i + 1][k < lim or j == 1][nl] += dp[i][j][l]

        # print(dp)

    print((dp[len(sN)][0][K] + dp[len(sN)][1][K]))


def __starting_point():
    run()

__starting_point()

import math
n = int(input())
K = int(input())

def calk1(n):
    if n == 0: return 0
    m = int(math.log10(n))
    num = m * 9
    num += n//(10**m)
    return num

def calk2(n):
    m = int(math.log10(n))
    num = m * (m - 1) // 2 * 9**2
    num += (n//(10**m)-1) * m * 9
    num += calk1(n - (n//(10**m)*10**m))
    return num

def calk3(n):
    m = int(math.log10(n))
    num = m * (m - 1) * (m - 2) // 6 * 9**3
    num += (n//(10**m)-1) * (m * (m - 1) // 2 * 9**2)
    num += calk2(n - (n//(10**m)*10**m))
    return num
if n < 10 ** (K - 1): print((0))
else:
    if K == 1: print((calk1(n)))
    elif K == 2: print((calk2(n)))
    else: print((calk3(n)))


S = input()
L = len(S)
K = int(input())

dp = [[[0,0] for _ in range(K+1)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(S):
    c = int(c)
    for k in reversed(range(K+1)):
        for d in range(10):
            nk = k + (d>0)
            if nk > K: continue
            dp[i+1][nk][1] += dp[i][k][1]
            if d > c: continue
            less = int(d < c)
            dp[i+1][nk][less] += dp[i][k][0]
print(sum(dp[-1][-1]))

N = list(map(int, list(input())))
L = len(N)
K = int(input())

dp = [[[0] * (K+1) for j in range(2)] for i in range(L+1)]
dp[0][0][0] = 1

for i in range(L):
    ni = N[i]
    if ni == 0:
        for j in range(K):
            dp[i+1][1][j+1] += dp[i][1][j] * 9
        for j in range(K+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(K+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(K):
            dp[i+1][1][j+1] += (dp[i][0][j] * (ni-1) + dp[i][1][j] * 9)
            dp[i+1][0][j+1] += dp[i][0][j]

    for j in range(K+1):
        dp[i+1][1][j] += dp[i][1][j]

print((dp[L][0][K]+dp[L][1][K]))


import math
def isMore(N,K):#- N以上の数で、０でないのが丁度K個
    #-len(N)よりもKがおおきかったら0 埋められない
    if len(N) < K:
        return 0
    #最高位の数字を1つ繰り上げれば、なんでも大きい。ただし、Kは1以上
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        #一桁ならtmpを返す
        if len(N)==1:
            return tmp
        #２桁以上あるなら＆最高位が０なら、最高桁繰り上げ＋最高桁同じ＋０でないものがK個
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        #２桁以上あるなら＆最高位が０以外なら、最高桁繰り上げ＋最高桁同じ＋０でないものがK-1個
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    #Kが0ならどうやってもNより大きいものが作れない0
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)


N = input()
K = int(input())
nSize = len(N)

dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(nSize + 1)]
dp[0][0][0] = 1

for i in range(nSize):
    for j in range(K + 1):
        for k in range(2):
            for l in range(10):
                ni = i + 1
                nj = j
                nk = k
                if l != 0: nj += 1
                if nj > K: continue
                if k == 0:
                    if l > int(N[i]): continue
                    if l < int(N[i]): nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[nSize][K][0] + dp[nSize][K][1])

N = input()
K = int(input())

keta = len(N)

dp = [[[0]*(keta+1) for _ in range(K+1)] for _ in range(2)]

for i in range(keta-1):
    dp[0][0][i] = 1
dp[0][1][0] = int(N[0])-1
dp[1][1][0] = 1

for i in range(1, K+1):
    for j in range(i-1, keta):
        x = int(N[j])
        dp[0][i][j] += dp[0][i][j-1] + dp[0][i-1][j-1]*9
        dp[0][i][j] += dp[1][i][j-1] if N[j]!="0" else 0
        dp[0][i][j] += dp[1][i-1][j-1] * max(int(N[j])-1, 0)

        dp[1][i][j] += dp[1][i][j-1]*int(N[j]=="0")
        dp[1][i][j] += dp[1][i-1][j-1]*int(N[j]!="0")

print(dp[0][-1][-2] + dp[1][-1][-2])

import sys

# import numba as nb
import numpy as np

input = sys.stdin.readline


# @nb.njit("i8(i8[:],i8,i8)", cache=True)
def solve(N, K, L):
    dp = np.zeros(shape=(L + 1, 2, K + 1), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

    return dp[L][0][K] + dp[L][1][K]


def main():
    N = np.array(list(input().rstrip()), dtype=np.int64)
    K = int(input())

    L = N.shape[0]
    ans = solve(N, K, L)

    print(ans)


def __starting_point():
    main()

__starting_point()

n = input()
k = int(input())

dp = [[[0] * (k+1) for _ in range(2)] for _ in range(len(n)+1)]
dp[0][0][0] = 1

for i in range(1, len(n) + 1):
    t = int(n[i-1])
    for j in range(k+1):
        if t != 0:
            if j != 0:
                dp[i][0][j] += dp[i-1][0][j-1]
                dp[i][1][j] += dp[i-1][1][j-1] * 9 + dp[i-1][0][j-1] * (t-1)
            dp[i][1][j] += (dp[i-1][1][j] + dp[i-1][0][j])
        else:
            dp[i][0][j] += dp[i-1][0][j]
            if j != 0:
                dp[i][1][j] += dp[i-1][1][j-1] * 9
            dp[i][1][j] += dp[i-1][1][j]

print(dp[len(n)][0][k] + dp[len(n)][1][k])

n = input()
k = int(input())
l = len(n)
dp = [[[0] * (k + 1) for j in range(2)] for i in range(l + 1)]
dp[0][0][0] = 1
for i in range(l):
    for j in range(2):
        for o in range(k + 1):
            for m in range(10):
                if not j and m > int(n[i]):
                    continue
                f = j or m < int(n[i])
                o2 = o + (m != 0)
                if o2 > k:
                    continue
                dp[i + 1][f][o2] += dp[i][j][o]
print(dp[-1][0][k] + dp[-1][1][k])

N = input()
K = int(input())
L = len(N)

dp =[[[ 0 for _ in range(2)] for _ in range(5)] for _ in range(len(N)+1)]
# dp[i][j][flg] i+1桁目までで0以外の個数がj個
# flg = 1 -> N 以下が確定している

dp[0][1][1] = int(N[0])-1
dp[0][1][0] = 1
dp[0][0][1]=1
for i in range(1,L):
  for j in range(4):
    b = i-1 # hitotumae
    now = int(N[i])
    ## N上限に張り付いてる方
    if now == 0:
      dp[i][j][0] += dp[b][j][0]
    else:
      dp[i][j][1] += dp[b][j][0]
      dp[i][j+1][1] += dp[b][j][0] * (now-1)
      dp[i][j+1][0] += dp[b][j][0]
    ## 張り付いてない方
    dp[i][j][1] += dp[b][j][1]
    dp[i][j+1][1] += dp[b][j][1] * 9
  

print((dp[L-1][K][0] + dp[L-1][K][1]))


#!/usr/bin python3
# -*- coding: utf-8 -*-
# 桁DP
# 1以上n以下の整数であって、 10進法で表したときに、0でない数字がちょうど
# k個あるようなものの個数

n = input()
k = int(input())
l = len(n)
#dp[i][j][status]   status=0 は小さいのが未確定=i文字まで同じ
#                   status=1 は小さいことが確定
# i桁目まで決めて、0でない桁がj個
# 初期値は1 からスタート s=0,i=0,j=0
dp = [[[0]*2 for j in range(k+1)] for i in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    ni = int(n[i])
    for j in range(k+1):
        for st in range(2):
            for x in range(10):
                i_ = i+1
                j_ = j
                st_ = st
                if x != 0:
                    j_ += 1
                if j_ > k:
                    continue
                if st_ == 0 and x > ni:
                    continue
                if st_ == 0 and x < ni:
                    st_ = 1
                dp[i_][j_][st_] += dp[i][j][st]

print((sum(dp[l][k])))


N = input()
K = int(input())

if len(N) < K:
  print(0)
  return

ans = [1, int(N[-1]), 0, 0];
nine = [1, 9, 81, 729]

def combination(N,K):
  if N < K:
    return 0
  elif K == 0:
    return 1
  elif K == 1:
    return N
  elif K == 2:
    return N*(N-1)//2
  else:
    return N*(N-1)*(N-2)//6

for k in range(1, len(N)):
  if int(N[-k-1]) > 0:
    a = [1, 0, 0, 0]
    for j in range(1, K+1):
      a[j] += nine[j]*combination(k, j)
      a[j] += (int(N[-k-1])-1)*combination(k, j-1)*nine[j-1] + ans[j-1]
    ans = a
print(ans[K])

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
    # n以下で0でないものがちょうどk個ある数字の個数
    if n < 10:
        if k == 0:
            return 1
        if k == 1:
            return n
        return 0
    q, r = divmod(n, 10)
    ret = 0
    if k >= 1:
        # 1の位が0
        ret += F(q, k-1) * r
        ret += F(q-1, k-1) * (9-r)
    ret += F(q, k)
    return ret

print(F(n, k))

import sys
 
read = sys.stdin.read
 
 
def main():
    N, K = map(int, read().split())
 
    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1
 
    for x in map(int, str(N)):
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] += dp2[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
                    dp1[j] = dp1[j - 1]
            else:
                dp1[j] = 0
                dp2[j] = 1
 
    print(dp1[K] + dp2[K])
    return
 
 
def __starting_point():
    main()
__starting_point()

from sys import stdin
from functools import lru_cache
N = int(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())

@lru_cache(None)
def f(N, K):
    #大きい桁から小さい桁へ
    if K < 0:
        return 0
    if N < 10:
        if K == 0:
            # 0のみ
            return 1
        elif K == 1:
            # 例えばN=4 なら0でないものが1,2,3,4の合計4個存在
            return N
        else:
            return 0
    q, r = divmod(N, 10)
    ret = 0
    if K >= 1:
        # 1の位が0以外の場合Kを消費する
        ret += f(q, K-1) * r
        ret += f(q-1, K-1) * (9-r)
    # 1の位が0の場合
    ret += f(q, K)
    return ret

print(f(N, K))

import math
n=int(input())
k=int(input())

def comb(n,k):
    s=1
    for i in range(k):
        s*=n-i
    for i in range(k):
        s//=i+1
    return s

def ans(n,k):

    s=0
    if int(str(n)[0])==0:
        return 0
    if len(str(n))<k:
        return 0
    elif len(str(n))==k:
        s+=(int(str(n)[0])-1) * comb(len(str(n))-1,k-1)*9**(k-1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        return s
    else:
        s += (int(str(n)[0]) - 1) * comb(len(str(n)) - 1, k - 1) * 9 ** (k - 1)
        if k-1==0:
            s+= 1
        else:
            s+= ans(int(str(n)[1:]),k-1)
        s+=comb(len(str(n))-1,k)*9**(k)
        return s

print(ans(n,k))

N = list(map(int, list(input())))
L = len(N)
K = int(input())
 
dp = [[[0] * (K+1) for j in range(2)] for i in range(L+1)]
dp[0][0][0] = 1
 
for i in range(L):
    ni = N[i]
    if ni == 0:
        for j in range(K):
            dp[i+1][1][j+1] += dp[i][1][j] * 9
        for j in range(K+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(K+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(K):
            dp[i+1][1][j+1] += (dp[i][0][j] * (ni-1) + dp[i][1][j] * 9)
            dp[i+1][0][j+1] += dp[i][0][j]
 
    for j in range(K+1):
        dp[i+1][1][j] += dp[i][1][j]
 
print(dp[L][0][K]+dp[L][1][K])

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    n = input()
    k = ni()

    l = len(n)

    dp_true = [[0 for _ in range(k + 2)] for i in range(l + 1)]
    dp_false = [[0 for i in range(k + 2)] for j in range(l + 1)]
    dp_false[0][0] = 1

    for i in range(l):
        num = int(n[i])

        for j in range(k + 1):
            dp_true[i + 1][j] += dp_true[i][j]
            dp_true[i + 1][j + 1] += dp_true[i][j] * 9

            if num > 0:
                dp_true[i + 1][j + 1] += dp_false[i][j] * (num - 1)
                dp_true[i + 1][j] += dp_false[i][j]

            if num > 0:
                dp_false[i + 1][j + 1] += dp_false[i][j]
            else:
                dp_false[i + 1][j] += dp_false[i][j]

    print((dp_true[l][k] + dp_false[l][k]))


def __starting_point():
    main()

__starting_point()

n = input()
K = int(input())
len_n = len(n)
dp = [[[0]*2 for _ in range(K+2)] for _ in range(len_n+1)]


dp[0][0][1] = 1
for i in range(1, len_n+1):
    d = int(n[i-1])
    for j in range(K+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j+1][0] += dp[i-1][j][0]*9
        if 0 < d:
            dp[i][j+1][0] += dp[i-1][j][1]*(d-1)
            dp[i][j][0] += dp[i-1][j][1]
            dp[i][j+1][1] += dp[i-1][j][1]
        else:
            dp[i][j][1] += dp[i-1][j][1]

ans = dp[-1][K][0]+dp[-1][K][1]
print(ans)


import sys
import numpy as np
input = lambda: sys.stdin.readline().rstrip()

N = list(map(int, input()))
K = int(input())


def solve():

    dp_sm = np.zeros((len(N), K + 1), np.int64)
    dp_lg = np.zeros((len(N), K + 1), np.int64)
    dp_sm[0][0] = 1
    dp_sm[0][1] = N[0] - 1
    dp_lg[0][0] = 0
    dp_lg[0][1] = 1

    for i in range(len(N) - 1):
        for j in range(K + 1):

            dp_sm[i + 1][j] += dp_sm[i][j]

            if N[i + 1] != 0:
                dp_sm[i + 1][j] += dp_lg[i][j]

            if j < K:
                dp_sm[i + 1][j + 1] += dp_sm[i][j] * 9

            if j < K and N[i + 1] != 0:
                dp_sm[i + 1][j + 1] += dp_lg[i][j] * (N[i + 1] - 1)
                dp_lg[i + 1][j + 1] += dp_lg[i][j]

            if N[i + 1] == 0:
                dp_lg[i + 1][j] += dp_lg[i][j]

    print((dp_sm[len(N) - 1][K] + dp_lg[len(N) - 1][K]))


def __starting_point():
    solve()

__starting_point()

N = int(input())
K = int(input())

def pow(a,n):
    ans = 1
    while n > 1:
        if bin(a&1)==bin(1):
            ans = ans*a
        a = a*a
        n = n>>1
    return ans

def com(N,k):
    if k<0 or k>N: return 0
    if k==1:return N
    elif k==2: return N*(N-1)//2
    else: return N*(N-1)*(N-2)//6

S = len(str(N))
N = str(N)
def helper(i,k,smaller):
    if i==S:
        if k==0: return 1
        else: return 0
    if k ==0: return 1
    if smaller: return com(S-i,k)*(9**k)
    else:
        if N[i]=='0': return helper(i+1,k,False)
        else:
            zero = helper(i+1,k,True)
            a = helper(i+1,k-1,True)*(int(N[i])-1)
            b = helper(i+1,k-1,False)
            return zero + a + b
print((helper(0,K,False)))


N = int(input())
K = int(input())

keta = len(str(N))
dp = [[[0] * 2 for _ in range(4)] for _ in range(keta+1)]

dp[0][0][0] = 1
dp[0][1][0] = 0
dp[0][2][0] = 0
dp[0][3][0] = 0
dp[0][0][1] = 0
dp[0][1][1] = 0
dp[0][2][1] = 0
dp[0][3][1] = 0

for i in range(1, keta+1):
    n = int(str(N)[i-1])
    if n == 0:
        # 桁，0でない数字の数，未満フラグ
        dp[i][0][0] = dp[i-1][0][0]
        dp[i][1][0] = dp[i-1][1][0]
        dp[i][2][0] = dp[i-1][2][0]
        dp[i][3][0] = dp[i-1][3][0]
        
        dp[i][0][1] = dp[i-1][0][1]
        dp[i][1][1] = dp[i-1][1][1] + dp[i-1][0][1]*9
        dp[i][2][1] = dp[i-1][2][1] + dp[i-1][1][1]*9
        dp[i][3][1] = dp[i-1][3][1] + dp[i-1][2][1]*9
    elif n != 0:
        dp[i][0][0] = 0
        dp[i][1][0] = dp[i-1][0][0]
        dp[i][2][0] = dp[i-1][1][0]
        dp[i][3][0] = dp[i-1][2][0]
        
        dp[i][0][1] = dp[i-1][0][0] + dp[i-1][0][1]
        dp[i][1][1] = (dp[i-1][1][0]+dp[i-1][1][1]) \
                     + dp[i-1][0][0]*(n-1) + dp[i-1][0][1]*9
        dp[i][2][1] = (dp[i-1][2][0]+dp[i-1][2][1]) \
                     + dp[i-1][1][0]*(n-1) + dp[i-1][1][1]*9
        dp[i][3][1] = (dp[i-1][3][0]+dp[i-1][3][1]) \
                     + dp[i-1][2][0]*(n-1) + dp[i-1][2][1]*9
print(sum(dp[keta][K]))

s = input()
K = int(input())
n =len(s)

dp = [[[0] * 2 for _ in range(4)] for _ in range(101)]

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])

            for d in range(10):
                ni = i+1; nj = j; nk = k

                if d != 0 :nj+=1
                if nj > K:continue
                if k==0:
                    if d > nd:continue
                    if d < nd:nk =1
                dp[ni][nj][nk] += dp[i][j][k]
                # print(d,k)
                # print(i,j,k,dp[i][j][k])
                # print(ni,nj,nk,dp[ni][nj][nk])
                # [print(i) for i in dp]

ans=dp[n][K][0] + dp[n][K][1]
print(ans)
# [print(i) for i in dp]


def zeroTrim(s):
    while s[0] == '0':
        if len(s) == 1:
            break
        s = s[1:]
    return s

N = input()
K = int(input())

def calc(N, K):
    digit = len(N)
    res = 0

    if K == 1:
        if digit > 1:
            res += (digit - 1) * 9
        res += int(N[0])
    elif K == 2:
        if digit <= 1:
            return 0
        if digit > 2:
            res += 9 * 9 * (digit - 1) * (digit - 2) // 2
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 1)
        res += calc(zeroTrim(N[1:]), 1)
    else:
        if digit <= 2:
            return 0
        if digit > 3:
            res += 9 * 9 * 9 * (digit - 1) * (digit - 2) * (digit - 3) // 6
        
        for i in range(int(N[0])-1):
            res += calc('9'*(digit-1), 2)
        res += calc(zeroTrim(N[1:]), 2)
    return res

print(calc(N, K))

n = input()
l = len(n)
k = int(input())
dp = [[[0]*(k+1) for _ in range(2)] for _ in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    nd = int(n[i])
    if nd == 0:
        for j in range(k+1):
            dp[i+1][0][j] += dp[i][0][j]
    else:
        for j in range(k+1):
            dp[i+1][1][j] += dp[i][0][j]
        for j in range(k):
            dp[i+1][0][j+1] += dp[i][0][j]
            dp[i+1][1][j+1] += dp[i][0][j]*(nd-1)
    for j in range(k):
        dp[i+1][1][j+1] += dp[i][1][j]*9
    for j in range(k+1):
        dp[i+1][1][j] += dp[i][1][j]
# for i in range(l+1): print(dp[i])
print(dp[l][0][k]+dp[l][1][k])

#!/usr/bin/env python3
import sys
# from scipy.special import comb
sys.setrecursionlimit(10**4)
from math import factorial

def comb(n, r):
    '''
    >>> comb(2, 1)
    2
    >>> comb(3, 2)
    3
    '''
    if r == 0:
        return 1
    if n == 0 or r > n:
        return 0
    return factorial(n) // factorial(n - r) // factorial(r)

def f(S, i, k):
    # ここに来るのは繰り下がりが発生していない状態...
    if k == 0:
        # 以降は0を選び続けるしかない
        return 1
    if len(S) <= i:
        # 走破したのにK個使いきれていない
        return 0
    n = int(S[i])
    if n == 0:
        # 注目する桁が0の場合、0を選ぶしかない
        return f(S, i+1, k)
    # 注目する桁の数値nより小さい値を選べば、以降は繰り下げで選び放題
    ret = (n - 1) * comb(len(S)-i-1, k-1) * pow(9, k-1)
    ret += comb(len(S)-i-1, k) * pow(9, k)
    # 注目する桁の数値nを選んだ場合、繰り下げができない状態が続行    
    ret += f(S, i+1, k-1)
    return ret

def solve(S: str, K: int):
    return f(S, 0, K)


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = next(tokens)  # type: str
    K = int(next(tokens))  # type: int
    print((solve(N, K)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    test()
    main()

__starting_point()

import sys

from functools import lru_cache

N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())


@lru_cache(None)
def F(N, K):
    """(0以上）N以下で、0でないものがちょうどK個"""

    assert N >= 0  # Nが非負であることを保証する

    if N < 10:  # N が一桁
        if K == 0:  # 使える 0 以外の数がない場合
            return 1  #
        if K == 1:
            return N  # 1,2,...,N までのどれか
        return 0  # それ以上 K が余っていたら作れない

    q, r = divmod(N, 10)  # N = 10*q + r と置く

    ret = 0
    if K >= 1:
        # 1の位(r)が nonzero
        ret += F(q, K - 1) * r  #
        ret += F(q - 1, K - 1) * (9 - r)

    # 1の位(r)が zero
    ret += F(q, K)
    return ret


print((F(N, K)))


def f(N,K):
    n=len(str(N))
    if n==1:
        if K==1:
            return N
        else:
            return 0
    elif n==2:
        if K==1:
            return 9+N//10
        elif K==2:
            return N-9-N//10
        else:
            return 0
    elif n==3:
        if K==1:
            return 18+N//100
        elif K==2:
            return 81+18*((N//100)-1)+f(N%100,1)
        else:
            return 81*((N//100)-1)+f(N%100,2)
    else:
        if K==1:
            return 9*(n-1)+N//(10**(n-1))
        elif K==2:
            return 81*(n-1)*(n-2)/2+9*(n-1)*((N//((10**(n-1))))-1)+f(N%(10**(n-1)),1)
        else:
            return 243*(n**3-6*(n**2)+11*n-6)/2+81*(n-1)*(n-2)*((N//(10**(n-1)))-1)/2+f(N%(10**(n-1)),2)
N=int(input())
K=int(input())
print(int(f(N,K)))

N=list(map(int,input()))
K=int(input())
L = len(N)
dp = [[[0]*(L+1) for _ in range(4)] for _ in range(2)]
dp[0][0][0] = 1
for i in range(2):
    for j in range(4):
        for k in range(L):
            for d in range(10 if i else N[k]+1):
                fl = 1 if i == 1 or d < N[k] else 0
                cnt = j+1 if d != 0 else j
                if cnt > K:
                    continue
                dp[fl][cnt][k+1] += dp[i][j][k]
print(dp[0][K][L]+dp[1][K][L])

N = input()
K = int(input())

if len(N) < K:
  print(0)
  return

keta = []
for k in range(len(N)):
  keta.append(int(N[-k-1]))
ans = [1, keta[0], 0, 0];

def combination(N,K):
  if N < K:
    return 0
  else:
    p = 1
    for k in range(K):
      p *= N
      N -= 1
    for k in range(1, K+1):
      p //= k
    return p
for k in range(1, len(N)-1):
  if keta[k] > 0:
    a = [1, 0, 0, 0]
    for j in range(1, 4):
      a[j] += (9**(j))*combination(k, j)
      a[j] += (keta[k]-1)*combination(k, j-1)*(9**(j-1)) + ans[j-1]
    ans = [] + a
answer = (9**(K))*combination(len(N)-1, K)
answer += (keta[-1]-1)*(9**(K-1))*combination(len(N)-1, K-1)
answer += ans[K-1]
print(answer)

strN = input().rstrip()
K = int(input())

maxD = len(strN)

dp = [[[0]*(K+1) for j in range(2)] for i in range(maxD+1)]
dp[0][0][0] = 1
for d, Nd in enumerate(strN):
    Nd = int(Nd)
    for isLtN in range(2):
        for numNot0 in range(K+1):
            for x in range(10):
                if not isLtN and x > Nd: continue
                isLtN2 = isLtN or x < Nd
                numNot02 = numNot0 + (x != 0)
                if numNot02 > K: continue
                dp[d+1][isLtN2][numNot02] += dp[d][isLtN][numNot0]

ans = dp[-1][0][K] + dp[-1][1][K]
print(ans)


import numpy as np

N = input()
K = int(input())

n = len(N)
dp0 = np.zeros((n, K+1), np.int64)
dp1 = np.zeros((n, K+1), np.int64)

dp0[0, 0] = 1
dp0[0, 1] = int(N[0]) - 1
dp1[0, 1] = 1
for i, d in enumerate(N[1:]):
    dp0[i+1] += dp0[i]
    dp0[i+1, 1:] += dp0[i, :-1] * 9
    if int(d) == 0:
        dp1[i+1] = dp1[i]
    elif int(d) == 1:
        dp0[i+1] += dp1[i]
        dp1[i+1, 1:] = dp1[i, :-1]
    elif int(d) >= 2:
        dp0[i+1] += dp1[i]
        dp0[i+1, 1:] += dp1[i, :-1] * (int(d) - 1)
        dp1[i+1, 1:] = dp1[i, :-1]

print((dp0[-1, K] + dp1[-1, K]))


# 桁DP練習
# 「0以外の値をkより多く使ったか」でとくに枝切りしてない
# ループでどうしてもかけない...

from sys import setrecursionlimit

setrecursionlimit(10**7)

n = input()
k = int(input())
dp = {}


def rec(i, smaller, count):
    if (i, smaller, count) in dp:
        return dp[(i, smaller, count)]
    if i == len(n):
        if count == k:
            return 1
        else:
            return 0
    limit = 10
    if not smaller:
        limit = int(n[i]) + 1
    ret = 0
    for j in range(limit):
        if smaller or j < int(n[i]):
            if j == 0:
                ret += rec(i + 1, True, count)
            else:
                ret += rec(i + 1, True, count + 1)
        else:
            if j == 0:
                ret += rec(i + 1, False, count)
            else:
                ret += rec(i + 1, False, count + 1)
    dp[(i, smaller, count)] = ret
    return ret


print((rec(0, False, 0)))


N=int(input())
K=int(input())
#for i in range(100):
 # for j in range(100):
  #  for k in range(100):
   #   if(i!=j and i!=k and j!=k):
    #    if(i*(10**))
ans=0
if(K==3):
  for a in range(1,10):
    for b in range(1,10):
      for c in range(1,10):
        ap=0
        bp=0
        cp=0
        while(a*(10**ap)<=N):#aについてみる
          ap+=1
        ap-=1
        while(a*(10**ap)+b*(10**bp)<=N and bp<ap):#bについてみる
          bp+=1
        bp-=1
        while(a*(10**ap)+b*(10**bp)+c*(10**cp)<=N and cp<bp):#cについてみる
          cp+=1
        cp-=1
        ans+=1+cp+(bp*(bp-1))//2+(ap*(ap-1)*(ap-2))//6
  print(ans)
elif(K==2):
  ans=0
  for i in range(100):
    for j in range(100):
      if(i>j):
        for a in range(1,10):
          for b in range(1,10):
            if(a*(10**i)+b*(10**j)<=N):
              ans+=1
  print(ans)
else:
  ans=0
  for i in range(100):
    for a in range(1,10):
      if(a*(10**i)<=N):
        ans+=1
  print(ans)

import numpy as np

N = list(map(int, input()))
K = int(input())
l = len(N)
if l < K:
    print((0))
    return

# dp[d][k] := d 桁目まで見て 0 でない数字が k 個ある場合の数
dp_small = np.zeros((l+1, K+1), dtype=np.int64)
dp_large = np.zeros((l+1, K+1), dtype=np.int64)
dp_large[0, 0] = 1
for d, digit in enumerate(N, 1):
    for k in range(K+1):
        # 0 を配置する
        dp_small[d, k] += dp_small[d-1, k]
        if digit != 0:
            dp_small[d, k] += dp_large[d-1, k]
            dp_large[d, k] = 0
        else:
            dp_large[d, k] = dp_large[d-1, k]
        if k!=0:
            # 0 以外を配置する
            dp_small[d, k] += dp_small[d-1, k-1] * 9
            if digit >= 1:
                dp_small[d, k] += dp_large[d-1, k-1] * (digit-1)
                dp_large[d, k] += dp_large[d-1, k-1]
print((dp_small[l, K] + dp_large[l, K]))


from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return list(map(int,input().split()))
def MAP1()  : return [int(x)-1 for x in input().split()]
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve(n, k, m):
    ans = 0
    for i in range(k, m):
        # i: 桁数
        if k == 1:
            ans += 9
        else:
            ans += pow(9, k)*comb(i-1, k-1)
    if k == 1:
        ans += int(n[0])
    elif k == 2:
        ans += (int(n[0])-1)*pow(9, k-1)*comb(m-1, k-1)
        j = 1
        while j < m and n[j] == '0':
            j += 1
        if j < m:
            ans += int(n[j]) + pow(9, k-1)*comb(m-1-j, k-1)
    else:
        while m >= k and n.count('0') > m - k:
            n = str(int(n)-1)

        if m > len(n):
            print(ans)
            return ans

        m = len(n)
        a = []
        for i in range(m):
            if len(a) < 3 and n[i] != '0':
                a.append(i)

        if len(a) == 3:
            ans += 1 + int(n[a[2]])-1 + 9*comb(m-1-a[2], 1)
            ans += (int(n[a[1]])-1)*9*comb(m-1-a[1], 1) + 9*9*comb(m-1-a[1], 2)
            ans += (int(n[a[0]])-1)*9*9*comb(m-1-a[0], 2)
    print(ans)
    return ans

def solve2(n, k, m):
    ans = 0
    for i in range(1, int(n)+1):
        if len(str(i)) - str(i).count('0') == k:
            ans += 1
    print(ans)
    return ans

def __starting_point():
    n = input()
    k = INT()
    m = len(n)

    solve(n,k,m)
    #solve2(n,k,m)
    #for i in range(10000):
    #    print(i)
    #    if solve(str(i), k, len(str(i))) != solve2(str(i), k, len(str(i))):
    #        break

__starting_point()

n = list(map(int, list(input())))
k = int(input())

dp0 = [0]*3
dp1 = [[0]*3]*len(n)
dp0[0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    dp1[i] = [
        dp1[i-1][0]+dp0[0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[1]*(n[i]!=0)+dp0[0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[2]*(n[i]!=0)+dp0[1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]
    if n[i] != 0:
        dp0 = [0]+dp0[:2]
print(dp0[k-1]+dp1[-1][k-1])

import numpy as np

s = input()
n = int(s)
k = int(input())

m = len(s)
dp = np.zeros((m+1, 2, k+2), dtype=np.int64)
dp[0][1][0] = 1
for cs in range(m):
    cn = int(s[cs])
    for ck in range(k+2):
        if ck == k+1:
            nk = ck
        else:
            nk = ck + 1
        dp[cs+1][0][nk] += 9 * dp[cs][0][ck]
        dp[cs+1][0][ck] += dp[cs][0][ck]

        if cn == 0:
            dp[cs+1][1][ck] += dp[cs][1][ck]
        else:
            dp[cs+1][1][nk] += dp[cs][1][ck]
            dp[cs+1][0][nk] += (cn - 1) * dp[cs][1][ck]
            dp[cs+1][0][ck] += dp[cs][1][ck]
print(dp[m][0][k] + dp[m][1][k] )

import sys

input = sys.stdin.readline


def solve(N, K, L):
    dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = N[i]
        for j in range(2):
            d_max = 9 if j == 1 else D
            for k in range(K + 1):
                if k < K:
                    for d in range(d_max + 1):
                        dp[i + 1][int(j or (d < D))][k + int(d > 0)] += dp[i][j][k]
                else:
                    dp[i + 1][j][k] += dp[i][j][k]

    return dp[L][0][K] + dp[L][1][K]


def main():
    N = list(map(int, input().rstrip()))
    K = int(input())

    L = len(N)
    ans = solve(N, K, L)

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    N = list(map(int, input()))
    K = int(input())

    if K == 1:
        ans = (len(N) - 1) * 9 + N[0]

    elif K == 2:

        if len(N) < 2:
            print((0))
            return

        ans = (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2
        ans += (N[0] - 1) * (len(N) - 1) * 9

        for i in range(1, len(N)):
            if N[i] != 0:
                ans += N[i] + (len(N) - i - 1) * 9
                break

    elif K == 3:

        if len(N) < 3:
            print((0))
            return

        ans = (9 ** 3) * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6
        ans += (N[0] - 1) * (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2

        for i in range(1, len(N) - 1):
            if N[i] != 0:
                ans += (9 ** 2) * (len(N) - i - 1) * (len(N) - i - 2) // 2
                ans += (N[i] - 1) * (len(N) - i - 1) * 9
                for j in range(i + 1, len(N)):
                    if N[j] != 0:
                        ans += N[j] + (len(N) - j - 1) * 9
                        break
                break

    print(ans)


def __starting_point():
    solve()

__starting_point()

# from collections import defaultdict
import math

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
K = int(input())
keta = len(str(N))
dp = [[0]*(keta) for i in range(4)]
ans = 0

for k in range(1, 4):
    for i in range(1, keta):
        if i<k:
            continue
        else:
            dp[k][i] = comb(i-1, i-k)*(9**k)
#print(dp)
# dp[k][i]: i桁で、k個の0でない数            

ans += sum(dp[K]) # (N の桁)-1 までの累積和

count = 0

for j in range(keta):
    t = int(str(N)[j])
    

    if j==0:
        count+=1
        ans += sum(dp[K-count])*(t-1)
        if count == K: # K==1
            ans+=t
            break
        continue
        
    elif j==keta-1:
        if t!=0:
            count+=1
        if count==K:
            ans+=t
        break
        
        
    if t !=0:
        count+=1
        if count==K:
            ans+=sum(dp[K-count+1][:keta-j]) #0のとき
            ans+=t
            break
        
        ans += sum(dp[K-count][:keta-j])*(t-1)  #0より大きいとき
        ans += sum(dp[K-count+1][:keta-j])   #0のとき
        
   
        
print(ans)

N = input()
n = len(N)
k = int(input())
dp = [[[0]*2 for _ in range(k+1)]for _ in range(n+1)]
dp[0][0][1] = 1
for i in range(1, n+1):
    d = int(N[i-1])
    for j in range(k+1):
        if 0 <= j-1:
            dp[i][j][0] += dp[i-1][j-1][0]*9
        dp[i][j][0] += dp[i-1][j][0]
        if d:
            if 0 <= j-1:
                dp[i][j][1] += dp[i-1][j-1][1]
                dp[i][j][0] += dp[i-1][j-1][1]*(d-1)
            dp[i][j][0] += dp[i-1][j][1]
        else:
            dp[i][j][1] += dp[i-1][j][1]

ans = dp[-1][-1][0]+dp[-1][-1][1]
print(ans)



def resolve():
    # 十進数表記で1~9までの数字がK個入るN桁の数字の数を答える問題
    S = input()
    K = int(input())
    n = len(S)

    # dp[i][k][smaller]:
    # i:桁数
    # K:0以外の数字を使った回数
    # smaller:iまでの桁で値以上になっていないかのフラグ

    dp = [[[0] * 2 for _ in range(4)] for _ in range(105)]
    dp[0][0][0] = 1

    for i in range(n):
        for j in range(4):
            for k in range(2):
                nd = int(S[i])
                for d in range(10):
                    ni = i+1
                    nj = j
                    nk = k
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if k == 0:
                        if d > nd: # 値を超えている
                            continue
                        if d < nd:
                            nk += 1
                    dp[ni][nj][nk] += dp[i][j][k]
    ans = dp[n][K][0] + dp[n][K][1]
    print(ans)


def __starting_point():
    resolve()
__starting_point()

S = input()
N = len(S)
K = int(input())

dp = [[[0] * 2 for _ in range(4)] for _ in range(N + 10)]
dp[0][0][0] = 1

for i, s in enumerate(S):
    nd = int(s)
    for j in range(K+1):
        for k in range(2):
            for d in range(10):
                ni = i + 1
                nj = j
                nk = k
                if d != 0:
                    nj += 1
                if nj > K:
                    continue
                if nk == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk += 1
                dp[ni][nj][nk] += dp[i][j][k]

print(dp[N][K][0]+dp[N][K][1])

n=input()
k=int(input())

len_n=len(n)
dp0=[[0]*(k+1) for _ in range(len_n+1)]
dp1=[[0]*(k+1) for _ in range(len_n+1)]
dp0[0][0]=1
# dp0: N以下であることが未確定
# dp1: N以下であることが確定
for i, n_i in enumerate(n):
    for k_i in range(k+1):
        if n_i=='0':
            dp0[i+1][k_i]+=dp0[i][k_i]
            dp1[i+1][k_i]+=dp1[i][k_i]
            if k_i<k:
                dp1[i+1][k_i+1]+=9*dp1[i][k_i]
        else:
            if k_i<k:
                dp0[i+1][k_i+1]+=dp0[i][k_i]
                dp1[i+1][k_i+1]+=(int(n_i)-1)*dp0[i][k_i]
                dp1[i+1][k_i+1]+=9*dp1[i][k_i]
            dp1[i+1][k_i]+=dp0[i][k_i]
            dp1[i+1][k_i]+=dp1[i][k_i]

print((dp0[-1][k]+dp1[-1][k]))


import numpy as np

N = input()
K = int(input())

dp = np.zeros((len(N)+1, K+1), np.int64)
dp[1, 1] = 1
for d in range(1, len(N)):
    dp[d+1] = dp[d]
    dp[d+1, 1:] += dp[d, :-1]

ans = 0
for i, c in enumerate(N):
    n = len(N)-i
    if c != '0':
        ans += np.sum(dp[:n, K]) * (9 ** K)
        ans += dp[n, K] * (int(c) - 1) * (9 ** (K-1))
        K -= 1
        if K == 0:
            ans += 1
            break

print(ans)

import sys

input = sys.stdin.readline


def solve_K_1(N):
    S = str(N)
    d = len(S)
    return 9 * (d - 1) + int(S[0])


def solve_K_2(N):
    if N <= 99:
        return N - solve_K_1(N)
    S = str(N)
    d = len(S)
    res = 0
    res += 81 * (d - 1) * (d - 2) // 2
    res += 9 * (d - 1) * (int(S[0]) - 1)
    x = 0
    for i in range(1, d):
        if S[i] != "0":
            x = int(S[i])
            break
    i += 1
    res += x + 9 * (d - i)
    return res


def solve_K_3(N):
    if N <= 999:
        return N - solve_K_1(N) - solve_K_2(N)
    S = str(N)
    d = len(S)
    res = 0
    for n in range(3, d):
        res += 729 * (n - 1) * (n - 2) // 2
    res += 81 * (d - 1) * (d - 2) // 2 * (int(S[0]) - 1)
    res += solve_K_2(int(S[1:]))
    return res


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

    if K == 1:
        ans = solve_K_1(N)
    elif K == 2:
        ans = solve_K_2(N)
    elif K == 3:
        ans = solve_K_3(N)

    print(ans)


def __starting_point():
    main()

__starting_point()

n = input()
k = int(input())
ln = len(n) + 1

dp=[[[0]* (ln) for _ in range(2)] for i in range(ln)]
dp[0][0][0] = 1
for i in range(len(n)):
  for smaller in range(2):
    x = int(n[i])
    t = 9 if smaller else x
    for j in range(t+1):
      for knum in range(ln-1):
        if j == 0:
          dp[i+1][int(smaller or j < x)][knum] += dp[i][smaller][knum]
        else:
          dp[i+1][int(smaller or j < x)][knum+1] += dp[i][smaller][knum]
try:
  print(dp[-1][0][k] + dp[-1][1][k])
except:
  print(0)

#!/usr/bin/env python3
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()


def per(n, r, mod=10**9+7):  # 順列数
    per = 1
    for i in range(r):
        per = per*(n-i) % mod
    return per


def com(n, r, mod=10**9+7):  # 組み合わせ数
    bunshi = per(n, r, mod)
    bunbo = 1
    for i in range(1, r+1):
        bunbo = bunbo*i % mod
    return bunshi*pow(bunbo, -1, mod) % mod


def main():
    n = list(map(int, list(input())))
    k = int(input())
    keta = len(n)
    count = [n[0]-1+com(keta-1, 1)*9, (n[0]-1)*com(keta-1, 1)*9+com(keta-1, 2)
             * 9**2, (n[0]-1)*com(keta-1, 2)*9**2+com(keta-1, 3)*9**3]
    nonzero = 1
    #print(count)
    for i in range(1, keta):
        if n[i] != 0:
            nonzero+=1
            if nonzero==2:
                count[1]+=(n[i]-1)+com(keta-i-1,1)*9
                count[2]+=(keta-i-1)*(n[i]-1)*9+com(keta-i-1,2)*9**2
            elif nonzero==3:
                count[2]+=(n[i]-1)+com(keta-i-1,1)*9
        #print(count)
    print((count[k-1]+(nonzero>=k)))



def __starting_point():
    main()

__starting_point()


def resolve():
    S = input()
    K = int(input())
    N = len(S)

    # dp[i][j][smaller]
    # i桁目まで見たときに0以外の数字をｊ個使用し、条件を満たす個数
    # smaller:
    # 0:i桁目まで見たときに一致している(次の桁は余裕が無い)
    # 1:次の桁は余裕がある

    dp = [[[0]*2 for _ in range(4)] for _ in range(N+1)]
    dp[0][0][0] = 1

    for i in range(N):
        for j in range(4):
            for smaller in range(2):
                now = int(S[i])
                for d in range(10):
                    ni = i+1
                    nj = j
                    n_smaller = smaller
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if smaller == 0:
                        if d > now: # 値を超えている
                            continue
                        if d < now: # 次の桁は余裕がある
                            n_smaller = 1
                    dp[ni][nj][n_smaller] += dp[i][j][smaller]
    ans = dp[N][K][0] + dp[N][K][1]
    print(ans)


def __starting_point():
    resolve()

__starting_point()

def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)/2*81
  else:
    return (a-1)*(D-1)*(D-2)/2*81 + (D-1)*(D-2)*(D-3)/6*729

N=str(input())
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):	
  if a!="0":
    score+=calc(int(a),D-i,K)
    K-=1
  if K==0:
    break
print(int(score))

N = list(map(int, input()))
K = int(input())


dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
    for j in range(K + 1):
        for is_smaller in range(2):
            for l in range(10):
                if not is_smaller and l > N[i] or l != 0 and j + 1 > K:
                    continue
                i_ = i + 1
                j_ = j
                is_smaller_ = is_smaller

                if l != 0:
                    j_ += 1

                if not is_smaller and l < N[i]:
                    is_smaller_ = 1
                dp[i_][j_][is_smaller_] += dp[i][j][is_smaller]
print((dp[len(N)][K][0] + dp[len(N)][K][1]))


n = list(map(int, list(input())))
k = int(input())

dp0 = [[0]*3]*len(n)
dp1 = [[0]*3]*len(n)
dp0[0][0] = 1
dp1[0][0] = max(0, n[0]-1)
for i in range(1, len(n)):
    if n[i]==0:
        dp0[i] = dp0[i-1]
    else:
        dp0[i] = [0]+dp0[i-1][:2]

    dp1[i] = [
        dp1[i-1][0]+dp0[i-1][0]*(n[i]!=0)+9,
        dp1[i-1][1]+dp0[i-1][1]*(n[i]!=0)+dp0[i-1][0]*max(0, n[i]-1)+dp1[i-1][0]*9,
        dp1[i-1][2]+dp0[i-1][2]*(n[i]!=0)+dp0[i-1][1]*max(0, n[i]-1)+dp1[i-1][1]*9,
    ]

print(dp0[-1][k-1]+dp1[-1][k-1])

def main():
    n = input()
    non_zero = int(input())
    length = len(n)
    dp = [[[0, 0] for _ in range(non_zero + 1)] for _ in range(length + 1)]
    dp[0][0][0] = 1
    for i in range(length):
        for j in range(non_zero + 1):
            for k in range(2):
                now_digit = int(n[i])
                for next_d in range(10):
                    new_i = i + 1
                    new_j = j
                    new_k = k
                    if next_d > 0:
                        new_j += 1
                    if new_j > non_zero:
                        continue
                    if k == 0:
                        if next_d > now_digit:
                            continue
                        elif next_d < now_digit:
                            new_k = 1
                    dp[new_i][new_j][new_k] += dp[i][j][k]
    print((sum(dp[length][non_zero])))


def __starting_point():
    main()


__starting_point()

s = input()
K = int(input())
n =len(s)

dp = [[[0] * 2 for _ in range(4)] for _ in range(105)]

dp[0][0][0]=1
for i in range(n):
    for j in range(4):
        for k in range(2):
            nd = int(s[i])- 0

            for d in range(10):
                ni = i+1; nj = j; nk = k

                if d != 0 :nj+=1
                if nj > K:continue
                if k==0:
                    if d > nd:continue
                    if d < nd:nk =1

                dp[ni][nj][nk] += dp[i][j][k]

ans=dp[n][K][0] + dp[n][K][1]
print(ans)

n = str(input())
k = int(input())
l = len(n)

def f(dig, under, num):
  if num > l - dig: return 0
  if num == 0: return 1
  if dig == l-1:
    if under: return int(n[dig])
    else: return 9
  if under:
    if n[dig] == '0':
      res = f(dig+1, True, num)
      #print(dig, under, num, res, 'aaa')
      return res
    else:
      res = f(dig+1, False, num)
      if int(n[dig]) > 1:
        res += (int(n[dig])-1) * f(dig+1, False, num-1)
      res += f(dig+1, True, num-1)
      #print(dig, under, num, res, 'bbb')
      return res
  else:
    res = f(dig+1, False, num)
    res += 9 * f(dig+1, False, num-1)
    #print(dig, under, num, res, 'ccc')
    return res

ans = f(0, True, k)
print(ans)

def calc(a,D,K):
  if K==1:
    return a+(D-1)*9
  elif K==2:
    return (a-1)*(D-1)*9 + (D-1)*(D-2)//2*81
  else:
    return (a-1)*(D-1)*(D-2)//2*81 + (D-1)*(D-2)*(D-3)//6*729

N=input()
K=int(input())
D = len(N)
score=0
for i,a in enumerate(N):
  if a!="0":
    score+=calc(int(a),D-i,K)
    K-=1
  if K==0:
    break
print(score)

N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1 #[i][j][k] i桁目まで決める　N未満で確定でj=1 0でない数がk個

for i in range(1, m + 1):
    l = int(N[i - 1])
    for k in range(K + 1): # 0でない数の個数 k を変化させていく
        if k -1 >= 0:
            if l != 0: #i桁目 1～9
                dp[i][0][k] = dp[i - 1][0][k-1]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1] + dp[i - 1][0][k] + (l-1)*dp[i - 1][0][k-1]
            else: #i桁目 0
                dp[i][0][k] = dp[i - 1][0][k]
                dp[i][1][k] = dp[i - 1][1][k] + 9*dp[i - 1][1][k-1]
        else: #すべての数が0ではない場合
            dp[i][0][k] = 0 # i桁目　Nと一致　すべてが0　→　該当なし　0コ
            dp[i][1][k] = 1 # i桁目　N未満　  すべてが0  →　0のみ　  1コ

#print(dp)
print(dp[m][0][K] + dp[m][1][K])

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  K=I()

  dp=[[[0]*2 for _ in range(4)] for __ in range(n+1)]
  dp[0][0][0]=1
  for i in range(n):
    nd=int(s[i])
    for j in range(4):
      for k in range(2):
        for d in range(10):
          ni=i+1
          nj=j
          nk=k

          if d!=0:
            nj+=1

          if K<nj:
            continue

          if nk==0:
            if d<nd:
              nk=1
            if nd<d:
              continue
          
          dp[ni][nj][nk]+=dp[i][j][k]

  return dp[n][K][0]+dp[n][K][1]

# main()
print((main()))


from functools import lru_cache

N = int(input())
K = int(input())

@lru_cache(None)
def f(n, k):
  if k < 0:
    return 0
  if n < 10:
    if k == 0:
      return 1
    elif k == 1:
      return n
    else:
      return 0
  a, b = divmod(n, 10)
  return f(a, k) + f(a, k-1) * b + f(a-1, k-1) * (9-b)
  
print(f(N, K))

import bisect, collections, copy, functools, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()
    K = I()

    # [0, N]で、non0の数字がK個あるものの数
    @functools.lru_cache
    def f(N, K):
        if N == K == 0:
            ret = 1
        elif N > 0 and K >= 0:
            ret = f(N // 10, K) + N % 10 * f(N // 10, K - 1) + (9 - N % 10) * f(N // 10 - 1, K - 1)
        else:
            ret = 0
        return ret
    
    ans = f(N, K)
    print(ans)

def __starting_point():
    resolve()

__starting_point()

def main():
    n = list(input())
    k = int(input())
    N = len(n)
    for i in range(N):
        n[i] = int(n[i])
    dp1 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp2 = [[0 for _ in range(k+1)] for _ in range(N+1)]
    dp1[0][0] = 1
    for i in range(N):
        for j in range(k+1):
            dp2[i+1][j] += dp2[i][j]
            if j < k:
                dp2[i+1][j+1] += dp2[i][j]*9
            if n[i]:
                dp2[i+1][j] += dp1[i][j]
                if j == k:
                    continue
                dp1[i+1][j+1] += dp1[i][j]
                dp2[i+1][j+1] += dp1[i][j] * (n[i]-1)
            else:
                dp1[i+1][j] += dp1[i][j]
    print(dp1[N][k]+dp2[N][k])
    
def __starting_point():
    main()
__starting_point()

n=[int(x) for x in list(input())]
l=len(n)
k=int(input())
"""
桁DP
桁数,0でないcount,ギリギリflagでdp
"""
dp = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(l+1)]
#n[0]は0ではない
dp[1][0][0] = 1
dp[1][1][0] = n[0] - 1
dp[1][1][1] = 1
for i in range(2,l+1):
  for j in range(0,min(i,k)+1):
    if j > 0:
      dp[i][j][1] += dp[i-1][j-1][1]*(n[i-1]>0)
      dp[i][j][0] += dp[i-1][j-1][0]*9+dp[i-1][j-1][1]*max(0,n[i-1]-1)
    dp[i][j][1] += dp[i-1][j][1]*(n[i-1]==0)
    dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j][1]*(n[i-1]>0)
    #print(i,j,dp[i][j])
print(sum(dp[l][k]))

def main():
    N = input()
    L = len(N)
    K = int(input())
    dp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
    dpp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
    dpp[0][0] = 1
    for i in range(1, L + 1):
        n = int(N[i - 1])
        for k in range(K + 1):
            # from dpp
            kk = k + (1 if n > 0 else 0)
            if kk <= K:
                dpp[kk][i] = dpp[k][i - 1]
            if n > 0:
                dp[k][i] += dpp[k][i - 1]
                if k + 1 <= K:
                    dp[k + 1][i] += (n - 1) * dpp[k][i - 1]
            # from dp
            dp[k][i] += dp[k][i - 1]
            if k + 1 <= K:
                dp[k + 1][i] += 9 * dp[k][i - 1]
    print(dp[K][L] + dpp[K][L])


def __starting_point():
    main()
__starting_point()

import sys

read = sys.stdin.read


def main():
    N, K = list(map(int, read().split()))

    dp1 = [0] * (K + 1)
    dp2 = [0] * (K + 1)
    dp1[0] = 1

    for x in map(int, str(N)):
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] += dp2[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
                    dp1[j] = dp1[j - 1]
            else:
                dp1[j] = 0
                dp2[j] = 1

    print((dp1[K] + dp2[K]))
    return


def __starting_point():
    main()

__starting_point()

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MAXN = 100

n = input()
k = int(input())

dl = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]
de = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]


def n_num_e(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        if i == 0:
            return 1
        else:
            return 0
    elif de[d][i] is not None:
        return de[d][i]
    else:
        if int(n[d - 1]) == 0:
            result = n_num_e(d - 1, i)
        else:
            result = n_num_e(d - 1, i - 1)
        de[d][i] = result
        return result


def n_num_l(d, i):
    # d: n of digits
    # i: n of nonzero digits
    if d == 0:
        return 0
    elif dl[d][i] is not None:
        return dl[d][i]
    else:
        if int(n[d - 1]) == 0:
            ne = 0
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl
        else:
            ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
            nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
            result = ne + nl

        dl[d][i] = result
        return result


answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)



n=input()
k=int(input())
l=len(n)

dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]

dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print((dp[l-1][k][0]+dp[l-1][k][1]))



N = input()
K = int(input())

# dp[is未満][K][桁]
dp = [[[0] * len(N) for _ in range(K+1)] for _ in range(2)]
dp[0][0][0] = 0
dp[1][0][0] = 1
dp[0][1][0] = 1
dp[1][1][0] = max(0,int(N[0])-1)

man_k = 1
for i in range(1, len(N)):
    n = N[i]
    is_nonzero = 1 if n != '0' else 0
    man_k += is_nonzero
    if man_k <= K:
        dp[0][man_k][i] = dp[0][man_k-is_nonzero][i-1]

    dp[1][0][i] = dp[1][0][i-1]
    for k in range(1,K+1):
        dp[1][k][i] = dp[1][k][i-1] + dp[1][k-1][i-1] * 9 # n==0のパターンとn!=0のパターン
        if n != "0":
            dp[1][k][i] += dp[0][k-1][i-1] * (int(n)-1) + dp[0][k][i-1] 

print(dp[0][K][-1] + dp[1][K][-1]) 

import math
def isMore(N,K):#- N以上の数で、０でないのが丁度K個
    #-len(N)よりもKがおおきかったら0
    if len(N) < K:
        return 0
    #最高位の数字を1つ繰り上げれば、なんでも大きい。ただし、Kは1以上
    if K>=1:
        tmp = (9-int(N[0]))*fact[len(N)-1]//((fact[len(N)-K])*(fact[K-1]))*(9**(K-1))
        if len(N)==1:
            return tmp
        elif len(N)>1 and N[0]=='0':
            return tmp + isMore(N[1:],K)
        elif len(N)>1 and N[0]!='0':
            return tmp + isMore(N[1:],K-1)
    if K == 0:
        return 0

N = input()
K = int(input())
lenN = len(N)
fact = [1]*101
for i in range(1,101):
    fact[i] = fact[i-1]*i

ans = fact[lenN]//((fact[lenN-K])*fact[K])*(9**K)
ans -= isMore(N,K)
print(ans)


N = input()
K = int(input())
L = len(N)

dp =[[[ 0 for _ in range(2)] for _ in range(5)] for _ in range(len(N)+1)]
# dp[i][j][flg] i+1桁目までで0以外の個数がj個
# flg = 1 -> N 以下が確定している

dp[0][1][1] = int(N[0])-1
dp[0][1][0] = 1

for i in range(1,L):
  for j in range(4):
    b = i-1 # hitotumae
    now = int(N[i])
    ## N上限に張り付いてる方
    if now == 0:
      dp[i][j][0] += dp[b][j][0]
    else:
      dp[i][j][1] += dp[b][j][0]
      dp[i][j+1][1] += dp[b][j][0] * (now-1)
      dp[i][j+1][0] += dp[b][j][0]
    ## 張り付いてない方
    dp[i][j][1] += dp[b][j][1]
    dp[i][j+1][1] += dp[b][j][1] * 9
  dp[i][1][1] += 9 # i桁目から始まった物（それより上がZEROのもの。）

print(dp[L-1][K][0] + dp[L-1][K][1])

from math import factorial
from itertools import product

S = input()
N = int(S)
m = len(S)
K = int(input())

# 0でない数字がちょうどK個でK桁のものを数える
product_K = product(['1', '2', '3', '4', '5', '6', '7', '8', '9'], repeat=K)
product_K = [int(''.join(x)) for x in product_K]
ans = len([x for x in product_K if x <= N])

if m > K:
    # K+1桁からlen(N)-1桁までを数える
    for i in range(1, m-K):
        ans += 9**K * factorial(i+K-1)//factorial(i)//factorial(K-1)
    
    # Nと同じ桁数で条件を満たすものを数える
    zero_n = m-K
    non_zero_n = K
    for i in range(m):
        l = int(S[i])
        if l == 0:
            zero_n -= 1
            continue
        if i > 0 and zero_n > 0:
            ans += 9**non_zero_n\
                * factorial(zero_n-1 + non_zero_n)\
                //factorial(zero_n-1)\
                //factorial(non_zero_n)
        non_zero_n -= 1
        ans += len([x for x in range(1, l)])\
                * 9**non_zero_n\
                * factorial(zero_n + non_zero_n)\
                //factorial(zero_n)\
                //factorial(non_zero_n)
        
        if non_zero_n <= 0:
            ans += 1
            break
print(ans)



#  愚直に数え上げる方法

import sys

input = lambda: sys.stdin.readline().rstrip()


def solve():

    N = list(map(int, input()))
    K = int(input())

    if K == 1:
        ans = (len(N) - 1) * 9 + N[0]

    elif K == 2:

        if len(N) < 2:
            print((0))
            return

        ans = (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2
        ans += (N[0] - 1) * (len(N) - 1) * 9

        for i in range(1, len(N)):
            if N[i] != 0:
                ans += N[i] + (len(N) - i - 1) * 9
                break

    elif K == 3:

        if len(N) < 3:
            print((0))
            return

        ans = (9 ** 3) * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6
        ans += (N[0] - 1) * (9 ** 2) * (len(N) - 1) * (len(N) - 2) // 2

        for i in range(1, len(N) - 1):
            if N[i] != 0:
                ans += (9 ** 2) * (len(N) - i - 1) * (len(N) - i - 2) // 2
                ans += (N[i] - 1) * (len(N) - i - 1) * 9
                for j in range(i + 1, len(N)):
                    if N[j] != 0:
                        ans += N[j] + (len(N) - j - 1) * 9
                        break
                break

    print(ans)


def __starting_point():
    solve()

__starting_point()

# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    S = Scanner.string()
    N = len(S)
    K = Scanner.int()
    dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(4):
            for k in range(2):
                nd = int(S[i])
                for d in range(10):
                    ni, nj, nk = i + 1, j, k
                    if d != 0:
                        nj += 1
                    if nj > K:
                        continue
                    if k == 0:
                        if d > nd:
                            continue
                        if d < nd:
                            nk += 1
                    dp[ni][nj][nk] += dp[i][j][k]
    print((dp[N][K][0] + dp[N][K][1]))


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


def __starting_point():
    main()

__starting_point()