Problem:
 Score : 500 points    Problem Statement 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 1 100
1      Sample Output 1 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        Sample Input 2 25
2      Sample Output 2 14  The following 14 integers satisfy the condition:   11,12,13,14,15,16,17,18,19,21,22,23,24,25        Sample Input 3 314159
2      Sample Output 3 937       Sample Input 4 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
3      Sample Output 4 117879300

Solution (Python):
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


if __name__ == '__main__':
    main()

Solution (Python):
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)):
        dp1, dp1_prev = [0] * (K + 1), dp1
        dp2, dp2_prev = [0] * (K + 1), dp2
        for j in range(K, -1, -1):
            if j > 0:
                dp2[j] = dp2_prev[j - 1] * 9
                if x != 0:
                    dp2[j] += dp1_prev[j - 1] * (x - 1)
            dp2[j] += dp2_prev[j]
            if x != 0:
                dp2[j] += dp1_prev[j]
                
            if x != 0:
                if j > 0:
                    dp1[j] = dp1_prev[j - 1]
            else:
                dp1[j] = dp1_prev[j]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    X = list(map(int, str(N)))
    L = len(X)

    dp1 = [[0] * (K + 1) for _ in range(L + 1)]
    dp2 = [[0] * (K + 1) for _ in range(L + 1)]
    dp1[0][0] = 1

    for i, x in enumerate(X):
        for j in range(K + 1):
            if x != 0:
                if j > 0:
                    dp1[i + 1][j] = dp1[i][j - 1]
            else:
                dp1[i + 1][j] = dp1[i][j]
            if j > 0:
                dp2[i + 1][j] = dp2[i][j - 1] * 9
                if x != 0:
                    dp2[i + 1][j] += dp1[i][j - 1] * (x - 1)
            dp2[i + 1][j] += dp2[i][j]
            if x != 0:
                dp2[i + 1][j] += dp1[i][j]

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


if __name__ == '__main__':
    main()

Solution (Python):
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):
            
            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]
            
            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])


if __name__ == '__main__':
    main()

Solution (Python):

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


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 
        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])

Solution (Python):
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):
    
    
    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):
    
    
    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)

Solution (Python):
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])

Solution (Python):

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7   
N = readline().decode().rstrip()
K = int(readline())
L = len(N)

dp = [[[0 for _ in range(2)] for _ in range(4)] for _ in range(L+1)]
dp[0][0][0] = 1
for i in range(L):
    for j in range(4):
        for k in range(2):
            nd = int(N[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(dp[L][K][0]+dp[L][K][1])

Solution (Python):
N=int(input())
K=int(input())

 
  
   
    
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):
          ap+=1
        ap-=1
        while(a*(10**ap)+b*(10**bp)<=N and bp<ap):
          bp+=1
        bp-=1
        while(a*(10**ap)+b*(10**bp)+c*(10**cp)<=N and cp<bp):
          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)

Solution (Python):
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


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])

Solution (Python):
import sys 
from functools import lru_cache
sys.setrecursionlimit(10**6)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7
N = int(readline())
K = int(readline())
@lru_cache(None)
def f(N,K):
    if K == -1:
        return 0
    if N < 10:
        if K == 0:
            return 1
        elif K == 1:
            return N
        else:
            return 0
    ans = 0
    q, mod = divmod(N, 10)
    ans += f(q,K) + mod * f(q,K-1) + (9-mod) * f(q-1,K-1) 
    return ans
print(f(N,K))

Solution (Python):
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])

Solution (Python):
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[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] += dp[b][j][1] * 9
  

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

Solution (Python):
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])

Solution (Python):
import sys
import bisect
import itertools
import collections
import fractions
import heapq
import math
from operator import mul
from functools import reduce
from functools import lru_cache


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7

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

    
    dp0 = [[0]*5 for _ in range(lenN+1)]
    
    dp1 = [[0]*5 for _ in range(lenN+1)]
    dp1[0][0] = 1

    for i in range(lenN):
        k = int(N[i])
        for zero in range(4):
            dp0[i+1][zero] += dp0[i][zero]
            dp0[i+1][zero+1] += dp0[i][zero] * 9
            if k != 0:
                dp0[i+1][zero] += dp1[i][zero]
                dp0[i+1][zero+1] += dp1[i][zero] * (k-1)
                dp1[i+1][zero+1] += dp1[i][zero]
            else:
                dp1[i+1][zero] += dp1[i][zero]


    ans = dp0[lenN][K] + dp1[lenN][K]
    print(ans)



if __name__ == '__main__':
    solve()

Solution (Python):
N = input()
K = int(input())

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

for i in range(1,L+1):
    a = int(N[i-1])
    for k in range(K+1):
        dp[i][0][k] += dp[i-1][0][k] if a==0 else dp[i-1][0][k-1]
        dp[i][1][k] += dp[i-1][1][k-1]*9 + dp[i-1][1][k]
        if a>0:
            dp[i][1][k] += dp[i-1][0][k-1]*(a-1) + dp[i-1][0][k]

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

Solution (Python):
s = input()
k = int(input())
l = len(s)
dp = [[[0 for i in range(k+1)] for j in range(2)] for m in range(l+1)]
dp[0][0][0] = 1
for i in range(l):
    for x in range(k+1):
        if s[i] == "0":
            dp[i+1][0][x] += dp[i][0][x]
        else:
            if x < k:
                dp[i+1][0][x+1] += dp[i][0][x]
            dp[i+1][1][x] += dp[i][0][x]
        for j in range(1, int(s[i])):
            if x < k:
                dp[i+1][1][x+1] += dp[i][0][x]
        dp[i+1][1][x] += dp[i][1][x]
        for j in range(1, 10):
            if x < k:
                dp[i+1][1][x+1] += dp[i][1][x]
print(dp[-1][0][-1] + dp[-1][1][-1])

Solution (Python):
N = str(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)):
  n = int(N[i])
  for j in range(K+1):
    for k in range(2): 
      for l in range(10): 
        nj, nk = j, 0
        if k == 0 and l == n:
          nk = 0
        elif k == 0 and l < n:
          nk = 1
        elif k == 0 and l > n:
          continue
        
        if k == 1:
          nk = 1
        
        if l != 0:
          if j < K:
            nj += 1
          else:
            continue
        
        dp[i+1][nj][nk] += dp[i][j][k]

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

Solution (Python):
N = input()
K = int(input())
dp = [[[0 for k in range(K+2)] for j in range(2)] for i in range(len(N)+1)]
dp[0][0][0] = 1
for i in range(len(N)):
    Ni = int(N[i])
    for j in range(2):
        for k in range(K+1):
            for d in range(10 if j else int(Ni)+1):
                dp[i+1][j or (d < Ni)][k + (d != 0)] += dp[i][j][k]
                

ans = dp[-1][0][K] + dp[-1][1][K]

print(ans)

Solution (Python):
n, k = input(), int(input())

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

for i in range(len(n)):
    for j in range(k + 1):
        dp0[i + 1][j] += dp0[i][j]
        dp0[i + 1][j + 1] += dp0[i][j] * 9
        if n[i] != '0':
            dp0[i + 1][j] += dp1[i][j]
            dp0[i + 1][j + 1] += dp1[i][j] * (int(n[i]) - 1)
            dp1[i + 1][j + 1] += dp1[i][j]
        elif n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]

print(dp0[len(n)][k] + dp1[len(n)][k])

Solution (Python):
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)

Solution (Python):
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())

Solution (Python):
n = list(input())
k = int(input())
t = len(n)
ketaDP = [[[0 for i in range(2)] for j in range(k+1)] for u in range(t)]

ketaDP[0][0][0] = 1
ketaDP[0][1][0] = int(n[0])-1
ketaDP[0][1][1] = 1
for i in range(1,t):
    now = int(n[i])
    for j in range(k+1):
        ketaDP[i][j][0] += ketaDP[i-1][j][0]
    for j in range(k):
        ketaDP[i][j+1][0] += ketaDP[i-1][j][0] * 9
    if now == 0:
        for j in range(k+1):
            ketaDP[i][j][1] += ketaDP[i-1][j][1]
    elif now != 0:
        for j in range(k+1):
            ketaDP[i][j][0] += ketaDP[i-1][j][1]
        for j in range(k):
            ketaDP[i][j+1][1] += ketaDP[i-1][j][1]
            ketaDP[i][j+1][0] += ketaDP[i-1][j][1]*(now-1)
print(sum(ketaDP[t-1][k]))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = input()
k = int(input())
l = len(n)
dp1 = [[0]*(k+1) for _ in range(l+1)]
dp0 = [[0]*(k+1) for _ in range(l+1)]
dp1[0][0] = 1
dp0[0][0] = 0
for i in range(1, l+1):
    for j in range(0, k+1):
        if n[i-1]=="0":
            dp1[i][j] = dp1[i-1][j]
        else:
            if j>=1:
                dp1[i][j] = dp1[i-1][j-1]
            dp0[i][j] += dp1[i-1][j]
        if int(n[i-1])>=2 and j>=1:
            dp0[i][j] += dp1[i-1][j-1] * (int(n[i-1])-1)
        if j>=1:
            dp0[i][j] += dp0[i-1][j-1]*9
        dp0[i][j] += dp0[i-1][j]
print(dp0[l][k]+dp1[l][k])

Solution (Python):
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])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







"""
N = '9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999'
K = 3
L = len(N)
"""

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

def judge(a):
    return a != 0


def digit_dp(n, k):
    l = len(n)

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

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

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    if judge(d_j):
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

    return dp

dp = digit_dp(N, K)
print(dp[L][0][K] + dp[L][1][K])


"""
N = '999999999'
L = len(N)

def judge_2(a):
    return a == 1



def digit_dp_2(n, k):
    l = len(n)

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

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

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    if judge_2(d_j):
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

    return dp

dp = digit_dp_2(N, L)

ans = 0
for j in range(L + 1):
    
    ans += (dp[L][0][j] + dp[L][1][j]) * j
print(ans)
"""

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






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

def judge(a):
    return a == 0


def digit_dp(n, k):
    l = len(n)

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

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

        for j in range(2):
            for d_j in range(10 if j else d + 1):
                for k_j in range(k + 1):
                    
                    if not judge(d_j):
                        
                        if k_j + 1 <= k:
                            dp[i + 1][j | (d_j < d)][k_j + 1] += dp[i][j][k_j]
                    else:
                        dp[i + 1][j | (d_j < d)][k_j] += dp[i][j][k_j]

    return dp[l][0][k] + dp[l][1][k]

print(digit_dp(N, K))

Solution (Python):

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)



ans += sum(dp[K]) 

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: 
            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]) 
            ans+=t
            break
        
        ans += sum(dp[K-count][:keta-j])*(t-1)  
        ans += sum(dp[K-count+1][:keta-j])   
        
   
        
print(ans)

Solution (Python):
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])

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

def resolve():
    
    
    
    n = input()
    d=int(input())
    


    dp = [[[0] * (d+2) for _ in range(2)] for _ in range(len(n) + 1)]
    dp[0][0][0] = 1
    
    MOD = 10**9 + 7
    for i in range(len(n)):
        c = ord(n[i]) - ord('0')
        for j in range(d+1):
            
            dp[i+1][1][j+1]+=dp[i][1][j]*9
            dp[i+1][1][j]+=dp[i][1][j]

            
            if c>0: 
                dp[i + 1][1][j+1]+=dp[i][0][j]*(c-1) 
                dp[i + 1][1][j]+=dp[i][0][j]
            

            
            if c>0:
                dp[i + 1][0][j+1]+=dp[i][0][j]
            else:
                dp[i+1][0][j]+=dp[i][0][j]
                dp[i + 1][0]
    
    print(dp[len(n)][1][d] + dp[len(n)][0][d])
    
    
    
resolve()

Solution (Python):
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[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])

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



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


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



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])


if __name__ == '__main__':
    main()

Solution (Python):
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]

print(dp[l][0][k]+dp[l][1][k])

Solution (Python):
import sys

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x


def kdp(s,K):
    
    
    
    keta=len(s)
    dp=[[[0,0] for _ in range(K+1)] for _ in range(keta+1)]
    

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

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

if __name__ == "__main__":
    s = input()
    K= int(input())
    kdp(s,K)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    s = input()
    K= int(input())
    
    
    
    
    keta=len(s)
    dp=[[[0,0] for _ in range(K+1)] for _ in range(keta+1)]
    

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


    
    

        
    



if __name__ == "__main__":
    main()