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 numpy as np
N = input()
K = int(input())
keta = len(N)
dp = np.zeros((keta + 1, 2, K + 1), dtype=np.int64)

dp[0][0][0] = 1

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

print(dp[keta][1][K] + dp[keta][0][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")


M = 10**9+7 
N = 100 

def cmb(n, r, M):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return (g1[n] * g2[r] * g2[n-r]) % M

g1 = [None] * (N+1) 
g2 = [None] * (N+1) 
inverse = [None] * (N+1) 
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M 
    g2[i] = (g2[i-1] * inverse[i]) % M 



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

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

if k>l:
    ans = 0
else:
    for i in range(1,l+1):
        for j in range(k+1):
            c = int(n[i-1])
            if j>=1:
                dp0[i][j] += 9 * dp0[i-1][j-1]
            dp0[i][j] += dp0[i-1][j]            
            if c>=1:
                dp0[i][j] += dp1[i-1][j]
                if j>=1:
                    dp0[i][j] += (c-1) * dp1[i-1][j-1]
                
            if c==0:
                dp1[i][j] += dp1[i-1][j]
            elif j>=1:
                dp1[i][j] += dp1[i-1][j-1]
                
ans = dp0[l][k] + dp1[l][k]
print(ans)

Solution (Python):
n = str(input())
k = int(input())
dp = [[[0] * (k+1) for i in range(2)] for j in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    for j in range(k+1):
        if n[i] == "0":
            dp[i+1][0][j] = dp[i][0][j]
            dp[i+1][1][j] = dp[i][1][j]
            if j > 0:
                dp[i+1][1][j] += dp[i][1][j-1]*9
        else:
            dp[i+1][1][j] = dp[i][0][j] + dp[i][1][j]
            if j > 0:
                dp[i+1][0][j] = dp[i][0][j-1]
                dp[i+1][1][j] += dp[i][0][j-1] * (int(n[i])-1) + dp[i][1][j-1] * 9
  
print(dp[-1][0][k] + dp[-1][1][k])

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = LSI()
K = I()
dp = FILL3(0,len(N)+1,K+1,2)
dp[0][0][0] = 1
for i in range(len(N)):
    for j in range(K+1):
        for k in range(2):
            m = N[i]
            max_d = 9 if k else m
            for d in range(max_d+1):
                k_ = k or d<max_d
                j_ = j + (d!=0)
                if j_ > K:
                    continue
                dp[i+1][j_][k_]+=dp[i][j][k]
print(dp[len(N)][K][0] + dp[len(N)][K][1])

Solution (Python):
N = int(input())
S = str(N)
m = len(S)
K = int(input())


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

for i in range(m): 
  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
          elif d < nd: 
            nk = 1
        dp[ni][nj][nk] += dp[i][j][k]

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

Solution (Python):
n = input()
k = int(input())
dp = [[0]*(k+1) for _ in range(2)]
dp[0][0] = 1
for i in range(len(n)):
    newdp = [[0]*(k+1) for _ in range(2)]
    for j in range(k+1):
        if n[i]=='0':
            newdp[0][j] = dp[0][j]
            newdp[1][j] = dp[1][j]
            if j>0:
                newdp[1][j] += dp[1][j-1]*9
        else:
            newdp[1][j] = dp[0][j] + dp[1][j]
            if j>0:
                newdp[0][j] = dp[0][j-1]
                newdp[1][j] += dp[0][j-1]*(int(n[i])-1) + dp[1][j-1]*9
    dp = newdp
print(dp[0][k]+dp[1][k])

Solution (Python):
n = input()
k = int(input())
dp = [[0]*(k+1) for _ in range(2)]
dp[0][0] = 1
for i in range(len(n)):
    newdp = [[0]*(k+1) for _ in range(2)]
    for j in range(k+1):
        if n[i]=='0':
            newdp[0][j] = dp[0][j]
            newdp[1][j] = dp[1][j]
            if j>0:
                newdp[1][j] += dp[1][j-1]*9
        else:
            newdp[1][j] = dp[0][j] + dp[1][j]
            if j>0:
                newdp[0][j] = dp[0][j-1]
                newdp[1][j] += dp[0][j-1]*(int(n[i])-1) + dp[1][j-1]*9
    dp = newdp
print(dp[0][k]+dp[1][k])

Solution (Python):
s = input()
n = int(s)
keta = len(s)
k = int(input())

ans = 0

dp = [[[0] * (2) for _ in range(k + 1)] for _ in range(keta + 1)]
dp[0][0][0] = 1
for i in range(keta):
    d = int(s[i])
    for j in range(k + 1):
        for smaller in range(2):

            for t in range(10):
                ni = i + 1
                nj = j
                nsmaller = smaller
                if t > 0:
                    nj = j + 1
                if nj > k:
                    continue
                if nsmaller == 0:
                    if t > d:
                        continue
                    if t < d:
                        nsmaller = 1
                dp[ni][nj][nsmaller] += dp[i][j][smaller]
print(dp[keta][k][1] + dp[keta][k][0])

Solution (Python):

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

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


dp[0][0][0] = 1


for i, n in enumerate(nn):
    for x in range(0, 10):
        if x == 0:
            dp[i + 1][1][0] += dp[i][1][0]
            dp[i + 1][1][1] += dp[i][1][1]
            dp[i + 1][1][2] += dp[i][1][2]
            dp[i + 1][1][3] += dp[i][1][3]
        else:
            dp[i + 1][1][1] += dp[i][1][0]
            dp[i + 1][1][2] += dp[i][1][1]
            dp[i + 1][1][3] += dp[i][1][2]

    for x in range(0, n + 1):
        if x == 0:
            dp[i + 1][0 if x == n else 1][0] += dp[i][0][0]
            dp[i + 1][0 if x == n else 1][1] += dp[i][0][1]
            dp[i + 1][0 if x == n else 1][2] += dp[i][0][2]
            dp[i + 1][0 if x == n else 1][3] += dp[i][0][3]
        else:
            dp[i + 1][0 if x == n else 1][1] += dp[i][0][0]
            dp[i + 1][0 if x == n else 1][2] += dp[i][0][1]
            dp[i + 1][0 if x == n else 1][3] += dp[i][0][2]


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

Solution (Python):
import sys

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

N = list(input())
n = len(N)
K = int(input())

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

for i in range(n):
    a = int(N[i])

    if a != 0:
        dp2[i + 1] = dp2[i] + 1
    else:
        dp2[i + 1] = dp2[i]
    
    
    for k in range(K + 1):
        dp1[i + 1][k] = dp1[i][k]

    
    for k in range(K):
        dp1[i + 1][k + 1] += dp1[i][k] * 9
    
    
    tmp = dp2[i] 
    if a == 0: 
        continue
    else:
        if tmp > K: 
            continue
        else:
            if tmp == K: 
                dp1[i + 1][tmp] += 1 
            else:
                dp1[i + 1][tmp] += 1 
                dp1[i + 1][tmp + 1] += (a - 1) 

ans = dp1[n][K]
if dp2[n] == K:
    ans += 1

print (ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    
    def digit_DP(S, K):
        L = len(S)
        
        dp = [[[0 for _ in range(4)] for _ in range(2)] for _ in range(101)]
        dp[0][0][0] = 1
        for i in range(L):  
            D = int(S[i])
            for j in range(2):  
                for k in range(4):  
                    for d in range(10 if j else D + 1):
                        cnt = k
                        if d != 0:
                            cnt += 1
                        if cnt > K:
                            continue
                        dp[i + 1][j or (d < D)][cnt] += dp[i][j][k]

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

    print(digit_DP(n, k))


if __name__ == '__main__':
    resolve()

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



def digit_dp(S,K):
    L = len(S)
    
    
    dp = [[[0 for k in range(K+1)] for j in range(2)] for i in range(L+1)]
    dp[0][0][0] = 1

    for i in range(L):
        D = int(S[i])
        for j in range(2):
            for d in range((9 if j else D)+1):
                for k in range(K+1):
                    if d != 0:
                        if k == K:
                            continue
                        dp[i+1][j or d<D][k+1] += dp[i][j][k]
                    else:
                        dp[i+1][j or d<D][k] += dp[i][j][k]

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

print(digit_dp(S,K))

Solution (Python):
from functools import lru_cache

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

@lru_cache(maxsize=None)
def search(d, k, isLess):
    if k == K:
        return 1
    if d == len(N):
        return 0

    n = int(N[d])

    if isLess:
        return search(d + 1, k, isLess) + search(d + 1, k + 1, isLess) * 9

    ret = 0
    for i in range(n + 1):
        ret += search(d + 1, k + (1 if i > 0 else 0) , isLess or (i < n))
    return ret

print(search(0, 0, False))

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

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

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

for i in range(1,len(N)):
    for k in range(K-1,-1,-1):
        dpsm[i][k+1]+=dpsm[i-1][k]*9

    
    if N[i]=="0":
        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dp[i][k]+=dp[i-1][k]
    else:
        for k in range(K-1,-1,-1):
            dpsm[i][k+1]+=dp[i-1][k]*(int(N[i])-1)
            dp[i][k+1]+=dp[i-1][k]

        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dpsm[i][k]+=dp[i-1][k]
          
print(dp[-1][-1]+dpsm[-1][-1])

Solution (Python):
import math
import numpy as np
import queue
from collections import deque
import heapq

def cmb(n,r):
    c = 1
    for i in range(r):
        c *= (n-i)
    for i in range(r):
        c //= (i+1)
    return c

n = input()
k = int(input())
ln = len(n)
ans = 0

nn0 = 0
for i in range(ln):
    if int(n[i]) > 0:
        ans += cmb(ln-i-1,k-nn0)*(9**(k-nn0))
        nn0 += 1
        ans += (int(n[i])-1)*cmb(ln-i-1,k-nn0)*(9**(k-nn0))
    if nn0 == k:
        ans += 1
        break

print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    n=len(s)
    K=int(input())
    dp_0=[[0]*(K+1) for _ in range(n+1)]
    dp_1=[[0]*(K+1) for _ in range(n+1)]
    dp_0[0][0]=1 
    for i in range(n):
        for j in range(K+1):
            for k in range(2):
                nd=int(s[i])-0
                for d in range(10): 
                    ni=i+1
                    nj=j
                    if d!=0:nj+=1
                    if nj>K:continue
                    if k==0:
                        if d>nd:continue
                        if d<nd:dp_1[ni][nj]+=dp_0[i][j]
                        else:dp_0[ni][nj]+=dp_0[i][j]
                    else:dp_1[ni][nj]+=dp_1[i][j]
    print(dp_0[n][K]+dp_1[n][K])

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    s=input()
    n=len(s)
    K=int(input())
    dp_0=[[0]*(K+1) for _ in range(n+1)]
    dp_1=[[0]*(K+1) for _ in range(n+1)]
    dp_0[0][0]=1 
    for i in range(n):
        for j in range(K+1):
            for k in range(2):
                nd=int(s[i])-0
                for d in range(10): 
                    ni=i+1
                    nj=j
                    if d!=0:nj+=1
                    if nj>K:continue
                    if k==0:
                        if d>nd:continue
                        if d<nd:dp_1[ni][nj]+=dp_0[i][j]
                        else:dp_0[ni][nj]+=dp_0[i][j]
                    else:dp_1[ni][nj]+=dp_1[i][j]
    print(dp_0[n][K]+dp_1[n][K])

if __name__=='__main__':
    main()

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

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

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



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

Solution (Python):
n=int(input())
k=int(input())
dp0=[[0 for i in range(4)] for i in range(len(str(n))+1)]
dp1=[[0 for i in range(4)] for i in range(len(str(n))+1)]

for i in range(1,len(str(n))+1):
    dp0[i][0]=1
dp0[1][1]=int(str(n)[0])-1
dp1[1][1]=1

for N in range(2,len(str(n))+1):
    for num in range(10):
        for K in range(1,4):
            if num!=0:
                if num<int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]+dp1[N-1][K-1]
                elif num==int(str(n)[N-1]):
                    dp0[N][K]+=dp0[N-1][K-1]
                    dp1[N][K]+=dp1[N-1][K-1]
                else:
                    dp0[N][K]+=dp0[N-1][K-1]
            else:
                if int(str(n)[N-1])>0:
                    dp0[N][K]+=dp0[N-1][K]+dp1[N-1][K]
                elif int(str(n)[N-1])==0:
                    dp1[N][K]+=dp1[N-1][K]
                    dp0[N][K]+=dp0[N-1][K]


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

Solution (Python):
def solve():
    N = input()
    K = int(input())
    l = len(N)
    dp = [[[0]*(K+2) for i in range(2)] for j in range(l+1)]
    dp[0][False][0] = 1 

    for i in range(l):
        for smaller in [False,True]:
            for k in range(K+1):
                for x in range(10 if smaller else int(N[i])+1):
                    if x == 0:
                        dp[i+1][smaller or (x < int(N[i]))][k] += dp[i][smaller][k]
                    else:
                        dp[i+1][smaller or (x < int(N[i]))][k+1] += dp[i][smaller][k]
    
    print(dp[l][False][K] + dp[l][True][K])

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    
    dp_1 = [[0] * (10) for _ in range(length)]

    
    dp_2 = [[0] * (10) for _ in range(length)]

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

    dp_2[0][1] = 1

    for i in range(1, length):
        
        for k in range(1, K + 2):
            dp_1[i][k] += dp_1[i - 1][k - 1] * 9

        
        for k in range(0, K + 2):
            dp_1[i][k] += dp_1[i - 1][k]

        
        if N[i] == "0":
            for k in range(K + 2):
                dp_2[i][k] += dp_2[i - 1][k]
        else:
            
            for k in range(K + 2):
                dp_1[i][k] += dp_2[i - 1][k]

            
            for k in range(1, K + 2):
                dp_1[i][k] += dp_2[i - 1][k - 1] * (int(N[i]) - 1)

            
            for k in range(1, K + 2):
                dp_2[i][k] += dp_2[i - 1][k - 1]

    ans = dp_1[-1][K] + dp_2[-1][K]
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

def main():
  s=input()
  k=int(input())
  n=len(s)
  def dp(i,j,smaller):
    
    
    if n==i: 
      return 0 if j>0 else 1
    if smaller:
      if j==0:
        return 1
      elif j==1:
        return (n-i)*9
      elif j==2:
        return ((n-i)*(n-i-1))//2*9**2
      elif j==3:
        return ((n-i)*(n-i-1)*(n-i-2))//6*9**3
    if j==0: 
      return 1
    ret=0
    
    if s[i]=='0':
      ret+=dp(i+1,j,smaller)
    else:
      ret+=dp(i+1,j-1,smaller) 
      ret+=(int(s[i])-1)*dp(i+1,j-1,True) 
      ret+=dp(i+1,j,True) 
    return ret
  print(dp(0,k,False))
if __name__=='__main__':
  main()

Solution (Python):
n = str(input())
p = int(input())

keta = len(n)
Dp = [[[0 for _ in range(2)] for _ in range(keta+1)]for _ in range(keta+1)]

Dp[0][0][1] = 1
10
for i in range(keta):
    for j in range(i+1):
        for k in range(10):
            if k == 0:
                if k < int(n[i]):
                    Dp[i+1][j][0] += Dp[i][j][0]
                    Dp[i+1][j][0] += Dp[i][j][1]
                    
                elif k == int(n[i]):
                    Dp[i+1][j][1] += Dp[i][j][1]
                    Dp[i+1][j][0] += Dp[i][j][0]
                
                else:
                    Dp[i+1][j][0] += Dp[i][j][0]
            
            else:
                if k < int(n[i]):
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                    Dp[i+1][j+1][0] += Dp[i][j][1]
                elif k == int(n[i]):
                    Dp[i+1][j+1][1] += Dp[i][j][1]
                    Dp[i+1][j+1][0] += Dp[i][j][0]
                else:
                    Dp[i+1][j+1][0] += Dp[i][j][0]

if p > keta:
    print(0)
else:
    print(sum(Dp[-1][p]))

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


target = list(map(int, list(input())[:-1]))
k = inp()



dp = [[[0] * 2 for _ in range(k + 2)] for i in range(len(target) + 1)]
dp[0][0][0] = 1
for i in range(len(target)):
    for j in range(k + 1):
        for smaller in range(2):
            for x in range(10 if smaller else target[i] + 1):  
                conditions = 1 if x != 0 else 0  

                dp[i + 1][j + conditions][smaller or x < target[i]]\
                    += dp[i][j][smaller]
    

ans = sum(dp[len(target)][k])
print(ans)

Solution (Python):
from scipy import misc

N = int(input())
K = int(input())
d = len(str(N))
first = int(str(N)[0])
if K == 1:
    print(9*(d-1)+first)
elif K == 2:
    if d == 1:
        print('0')
    else:
        for i in range(1,d):
            if str(N)[i] != '0':
                second_dig = i+1
                second_num = int(str(N)[i])
                break
        else:
            second_dig = d
            second_num = 0
        print(((d-1)*(d-2)//2*81)+(first-1)*(d-1)*9+(d-second_dig)*9+second_num)
else:
    if K < 3:
        print('0')
    else:
        found_second = False
        found_third = False
        for i in range(1,d):
            if str(N)[i] != '0':
                if found_second == False:
                    second_dig = i+1
                    second_num = int(str(N)[i])
                    found_second = True
                else:
                    third_dig = i+1
                    third_num = int(str(N)[i])
                    found_third = True
                    break
        if found_second == False:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81))
        elif found_third == False:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81)+(second_num-1)*(d-second_dig)*9+(d-second_dig)*(d-second_dig-1)//2*81)
        else:
            print((d-1)*(d-2)*(d-3)//6*729+(first-1)*((d-1)*(d-2)//2*81)+(second_num-1)*(d-second_dig)*9+(d-second_dig)*(d-second_dig-1)//2*81+(d-third_dig)*9+third_num)

Solution (Python):
N,K=int(input()),int(input())
def f(n,k):
  if k<1: return 1
  if n<10:
    if k<2: return n
    return 0
  d,m=n//10,n%10
  return f(d,k-1)*m+f(d-1,k-1)*(9-m)+f(d,k)
print(f(N,K))

Solution (Python):
N = int(input())
K = int(input())
l = len(str(N))
dp = [[[0]*(K+1) for _ in range(2)] for _ in range(l+1)]





dp[0][0][0] = 1
for i in range(l):
  n = int(str(N)[i])
  for j in range(2):
    for k in range(K+1):
      for m in range(10):
        
        if j == 0 and m > n:
          continue
        if j == 0 and m == n:
          nj = 0 
          if m == 0:
            nk = k 
          else:
            if k < K:
              nk = k + 1 
            else:
              nk = k
              continue
        if j == 0 and m < n:
          nj = 1
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

        
        if j == 1:
          nj = j
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

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

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

Solution (Python):
N = int(input())
K = int(input())
l = len(str(N))
dp = [[[0]*(K+2) for _ in range(2)] for _ in range(l+1)]





dp[0][0][0] = 1
for i in range(l):
  n = int(str(N)[i])
  for j in range(2):
    for k in range(K+1):
      for m in range(10):
        
        if j == 0 and m > n:
          continue
        if j == 0 and m == n:
          nj = 0 
          if m == 0:
            nk = k 
          else:
            if k < K:
              nk = k + 1 
            else:
              nk = k
              continue
        if j == 0 and m < n:
          nj = 1
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

        
        if j == 1:
          nj = j
          if m == 0:
            nk = k
          else:
            if k < K:
              nk = k + 1
            else:
              nk = k
              continue

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

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

Solution (Python):
n = input()
k = int(input())
dp = [[[0] * (k + 2) for i in range(2)] for j in range(len(n) + 1)]
dp[0][0][0] = 1

for i in range(len(n)):
    value = int(n[i])
    for j in range(2):
        for l in range(k + 1):
            for d in range(10 if j == 1 else value + 1):
                dp[i + 1][1 if j == 1 else 1 if (d < value) else 0][l if d == 0 else l + 1] += dp[i][j][l]
print(dp[len(n)][0][k] + dp[len(n)][1][k])

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



dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(N+1)]
dp[0][0][0] = 1
"""
遷移
dp[i][1][j] -> dp[i+1][1][j] : i-1桁目までに0以外の数字がj個あり、i桁目に0を入れた
dp[i][1][j] -> dp[i+1][1][j+1] : i-1桁目までに0以外の数字がj個あり、i桁目に0以外を入れた
dp[i][0][j] -> dp[i+1][1][j] : i-1桁目がSと一致していて、i-1桁目までに0以外の数字がj個あり、までに0以外の数字がj個あり、i桁目に0を入れた
dp[i][0][j] -> dp[i+1][1][j] : i-1桁目がSと一致していて、i-1桁目までに0以外の数字がj個あり、までに0以外の数字がj個あり、i桁目に0以外を入れた
dp[i][0][j] -> dp[i+1][0][j+?] : i桁目までSと一致。i桁目が0以外なら、?=1

"""

for i in range(N):
    for k in range(4):
        for j in range(10):
        


            if j == 0:
                 
                dp[i+1][1][k] += dp[i][1][k]
            else:
                
                dp[i+1][1][k+1] += dp[i][1][k]


            if j < int(S[i]):
                if j == 0:
                    dp[i+1][1][k] += dp[i][0][k]
                else:
                    dp[i+1][1][k+1] += dp[i][0][k]
            elif j == int(S[i]):
                if j == 0:
                    dp[i+1][0][k] += dp[i][0][k]
                else:
                    dp[i+1][0][k+1] += dp[i][0][k]


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

Solution (Python):
def solve():
    N = input()
    K = int(input())
    dp = [[[0]*(K+2) for i in range(2)] for j in range(len(N)+1)]
    dp[0][False][0] = 1

    for i in range(len(N)):
        for k in range(K+1):
            dp[i+1][True][k+1] += dp[i][True][k] * 9
            dp[i+1][True][k] += dp[i][True][k]

            if int(N[i]) > 0:
                dp[i+1][True][k+1] += dp[i][False][k] * (int(N[i]) - 1)
                dp[i+1][True][k] += dp[i][False][k]
            
            if int(N[i]) > 0:
                dp[i+1][False][k+1] = dp[i][0][k]
            else:
                dp[i+1][False][k] = dp[i][0][k]
    
    print(dp[-1][False][K] + dp[-1][True][K])

if __name__ == '__main__':
    solve()

Solution (Python):
from sys import stdin, setrecursionlimit


def main():
    input = stdin.buffer.readline
    n = list(map(int, list(input()[:-1].decode())))
    N = len(n)
    k = int(input())

    dp = [[[0] * (k + 1) for _ in range(2)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(1, N + 1):
        num = n[i - 1]
        for j in range(k + 1):
            dp[i][1][j] += dp[i - 1][1][j]
            if num != 0:
                dp[i][1][j] += dp[i - 1][0][j]
            else:
                dp[i][0][j] += dp[i - 1][0][j]
            if j >= 1:
                dp[i][1][j] += 9 * dp[i - 1][1][j - 1]
                if num != 0:
                    dp[i][0][j] += dp[i - 1][0][j - 1]
                    dp[i][1][j] += (num - 1) * dp[i - 1][0][j - 1]

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


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

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

digit = len(str(n))

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

for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            for d in range(10 if b == 1 else digitvalue + 1):
                dp[a][1 if b == 1 else 1 if (d < digitvalue) else 0][c if d == 0 else c + 1] += dp[a - 1][b][c]

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

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

digit = len(str(n))

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

for a in range(1, digit + 1):
    digitvalue = int(str(n)[a - 1])
    for b in range(2):
        for c in range(k + 1):
            for d in range(10 if b == 1 else digitvalue + 1):
                dp[a][1 if b == 1 else 1 if (d < digitvalue) else 0][c if d == 0 else c + 1] += dp[a - 1][b][c]

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

Solution (Python):
n = input()
k = int(input())
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 in range(len(n)):
    for j in range(k+1):
        if int(n[i]) == 0:
            dp0[i+1][j] += dp0[i][j]
        if int(n[i]) > 0:
            dp1[i+1][j] += dp0[i][j]
            if j < k:
                dp0[i+1][j+1] += dp0[i][j]
                dp1[i+1][j+1] += dp0[i][j]*(int(n[i])-1)
        if j < k:
            dp1[i+1][j+1] += dp1[i][j]*9
        dp1[i+1][j] += dp1[i][j]
print(dp0[len(n)][k]+dp1[len(n)][k])

Solution (Python):
import itertools
N = input()
K = int(input())
l = len(N)
S = list(map(int, N))
N = int(N)

if K == 1:
    ans = S[0] + 9*(l-1)
elif K == 2 and l >= 2:
    
    ans = (S[0]-1)*9*(l-1)
    
    for i in range(1, l):
        if S[0]*10**(l-1)+9*10**(l-i-1) <= N:
            ans += 9
        else:
            ans += S[i]
    
    if l > K:
        ans += (l-1)*(l-2)//2*9**2
elif K == 3 and l >= 3:
    
    ans = (S[0]-1)*(l-1)*(l-2)//2*9**2
    
    for a, b in itertools.combinations(range(1, l), 2):
        if S[0]*10**(l-1)+9*10**(l-a-1) <= N:
            if S[0]*10**(l-1)+9*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += 9**2
            else:
                ans += 8*9 + S[b]
        else:
            if S[0]*10**(l-1)+S[a]*10**(l-a-1)+9*10**(l-b-1) <= N:
                ans += S[a]*9
            else:
                if S[a] == 0:
                    pass
                else:
                    ans += (S[a]-1)*9 + S[b]
    
    ans += (l-1)*(l-2)*(l-3)//6*9**3
else:
    ans = 0
print(ans)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

sys.setrecursionlimit(10 ** 7)

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()
s = str(n)
K = ni()

dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(len(s) + 1)]
dp[0][0][0] = 1
for i in range(len(s)):
    for j in range(K + 1):
        for k in range(2):
            dmax = 9 if k else int(s[i])
            for d in range(dmax + 1):
                ni = i + 1
                nj = j + (d != 0)
                nk = k | (d < dmax)
                dp[ni][nj][nk] += dp[i][j][k]

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