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):
n = input()
k = int(input())

dp1 = [ [ i+1 for i in range(9) ] for i in range(201)]
dp2 = [ [ 0 for i in range(9) ] for i in range(201)]
dp3 = [ [ 0 for i in range(9) ] for i in range(201)]

for i in range(200):
    for j in range(9):
        if j == 0:
            dp1[i+1][j] = dp1[i][-1] + 1
        else:
            dp1[i+1][j] = dp1[i+1][j-1] + 1

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(200):
    for j in range(9):
        if j == 0:
            dp2[i+1][j] = dp2[i][-1] + 9 * (i)
        else:
            dp2[i+1][j] = dp2[i+1][j-1] + 9 * (i+1)

for i in range(100):
    for j in range(9):
        if j == 0:
            dp3[i+1][j] = dp3[i][-1] + 81 * i*(i-1)//2
        else:
            dp3[i+1][j] = dp3[i+1][j-1] + 81 * (i+1) * i //2


def solve(s, x):
    if s == "0":
        return 0
    elif s[0] == "0":
        return solve(s[1:], x)

    if x == 1:

        return  dp1[len(s)-1][int(s[0]) - 1]
    elif x == 2:
        if len(s) < 2:
            return 0
        return  dp2[len(s)-1][int(s[0]) - 1] + solve(s[1:], 1)
    elif x == 3:
        if len(s) < 3:
            return 0
        return  dp3[len(s)-1][int(s[0]) - 1] + solve(s[1:], 2)

print(solve(n, k))

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

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

def getMiman(X):
  if X>0:
    return X-1
  else:
    return 0

x0=int(N[0])
dp[0][0][0]=0
dp[0][1][0]=1
dp[0][0][1]=1
dp[0][1][1]=getMiman(x0)

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

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

def solve(num_str, k, smaller):
    if num_str == "" and k > 0:
        return 0
    if k == 0 or num_str == "":
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

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

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

print(res)

Solution (Python):
from math import factorial

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


def ncr(n, r):
    if n < r:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)


def k1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])


def k2(n):
    if n < 10:
        return 0
    s = str(n)
    res = ncr(len(s)-1, 2) * 9 * 9
    res += (int(s[0]) - 1) * k1(10 ** (len(s) - 1) - 1) + k1(int(s[1:]))
    return res


def k3(n):
    s = str(n)
    res = ncr(len(s)-1, 3)*9*9*9
    res += (int(s[0]) - 1) * k2(10 ** (len(s) - 1) - 1) + k2(int(s[1:]))
    return res


kf = [k1, k2, k3]
print(kf[K-1](N))

Solution (Python):

from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            
            dp[("T",i,k)]+=dp[("T",i-1,k)]      
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9  
            
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) 
                dp[("T",i,k)]+=dp[("F",i-1,k)]  
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 
            else: 
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Solution (Python):

from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            
            dp[("T",i,k)]+=dp[("T",i-1,k)]      
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9  
            
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) 
                dp[("T",i,k)]+=dp[("F",i-1,k)]  
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 
            else: 
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import log10, ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = input()
K = INT()
L = len(N)
dp = [[[0]*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, 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]
ans = dp[L][K][0] + dp[L][K][1]
print(ans)

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

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])

Solution (Python):
s=int(input())
n=len(str(s))
k=int(input())
S=[int(i) for i in str(s)]
dpl=[[0]*(k+1) for i in range(n+1)]
dpj=[[0]*(k+1) for i in range(n+1)]
dpj[0][0]=1
for i in range(n):
    for j in range(k+1):
        dpj[i+1][j]+=dpj[i][j]*(S[i]==0)
        dpl[i+1][j]+=dpl[i][j]+dpj[i][j]*(S[i]>0)
        if j<k:
            dpj[i+1][j+1]+=dpj[i][j]*(S[i]>0)
            dpl[i+1][j+1]+=dpl[i][j]*9+dpj[i][j]*max(0,S[i]-1) 
print(dpl[n][k]+dpj[n][k])

Solution (Python):
S = input()
n = len(S)
K = int(input())
dp = [[[0]*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(K+1):    
        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]
ans = dp[n][K][0] + dp[n][K][1]
print(ans)

Solution (Python):

import numpy as np

N=input()
K=input()
dp=np.zeros((len(str(N))+10,len(str(N))+10,2))
dp=dp.tolist()


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


for i in range(0,len(N),1):
    for j in range(0,4,1):
        for k in range(0,2,1):
            nd=int(N[i])
            for d in range(0,10,1):
                ni=i+1
                nj=j
                nk=k
                if not(d==0):
                    nj=nj+1
                if ((k==0)and(d<nd)):
                    nk=1
                if (not(nj>int(K)))and(not((k==0)and(d>nd))):
                    dp[ni][nj][nk]=dp[ni][nj][nk]+dp[i][j][k]


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

Solution (Python):

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

'''
桁DP
dp[i][j][k] := 
i桁目まで使って
j個の0ではない数値を使って
k=0:i桁目までSと一致
  1:S未満(以下？)
'''
dp = [[[0]*2 for _ in range(K+1)] for _ in range(101)]
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])
            
            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
                    elif d != nd:
                        nk = 1
                dp[ni][nj][nk] += dp[i][j][k]

print(sum(dp[N][K]))

Solution (Python):


import sys
from pprint import pprint
import math

INF = float("inf")
  
def solve(N: str, K: int):
    M = len(N)
    DP = [[[0]*2 for __ in range(K+1)] for _ in range(M+1)]
    Nstr = N
 
    DP[0][0][False] = 1
 
    for i in range(M):
        DP[i+1][0][True] = 1
        DP[i+1][0][False] = 0
        for k in range(K):
            DP[i+1][k+1][True] = DP[i][k][True]*9 + DP[i][k+1][True]*1
            if int(Nstr[i]) != 0:
                DP[i+1][k+1][True] += DP[i][k+1][False]
                DP[i+1][k+1][True] += DP[i][k][False]*(int(Nstr[i])-1)
            if int(Nstr[i]) == 0:
                DP[i+1][k+1][False] = DP[i][k+1][False]
            else:
                DP[i+1][k+1][False] = DP[i][k][False]
    print(DP[M][K][True]+DP[M][K][False])
    
 
    return
 
 
if __name__ == '__main__':
 
    n = sys.stdin.readline().strip()
    k = int(sys.stdin.readline().strip())
     
    solve(n, k)

Solution (Python):
from math import factorial


def cmb(n, r):
    if n-r < 0 or r < 0:
        return 0
    else:
        return factorial(n) // (factorial(r) * factorial(n - r))


def solve(n, k):
    if k < 0:
        return 0

    if n == [] or sum(n) == 0:
        if k == 0:
            return 1
        else:
            return 0

    for i in range(len(n)):
        if n[i] != 0:
            break

    n = n[i:]

    l = len(n)
    ans = 0

    
    tmp1 = (9**k)*cmb(l-1, k)

    
    tmp2 = (n[0]-1)*(9**(k-1))*cmb(l-1, k-1)

    
    tmp3 = solve(n[1:], k-1)

    ans = tmp1 + tmp2 + tmp3
    return int(ans)


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

print(solve(n, k))

Solution (Python):
from math import factorial


def cmb(n, r):
    if n-r < 0 or r < 0:
        return 0
    else:
        return factorial(n) // (factorial(r) * factorial(n - r))


def solve(n, k):
    if n == [] or sum(n) == 0:
        if k == 0:
            return 1
        else:
            return 0

    for i in range(len(n)):
        if n[i] != 0:
            break

    n = n[i:]

    l = len(n)
    ans = 0

    
    tmp1 = (9**k)*cmb(l-1, k)

    
    tmp2 = (n[0]-1)*(9**(k-1))*cmb(l-1, k-1)

    
    if k > 1:
        tmp3 = solve(n[1:], k-1)
    elif k == 1:
        if len(n) == 1:
            tmp3 = 1
        else:
            tmp3 = solve(n[1:], k-1)
    else:
        tmp3 = 0

    ans = tmp1 + tmp2 + tmp3
    return int(ans)


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

print(solve(n, k))

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

s=int(input()); n=len(str(s))
k=int(input())
S=[int(i) for i in str(s)]
dpl=[[0]*(k+1) for i in range(n+1)]
dpj=[[0]*(k+1) for i in range(n+1)]
dpj[0][0]=1
for i in range(n):
    for j in range(k+1):
        dpj[i+1][j] += dpj[i][j]*(S[i]==0)
        dpl[i+1][j] += dpl[i][j] + dpj[i][j]*(S[i] >= 1)
        if j+1 < k+1:
            dpj[i+1][j+1] += dpj[i][j]*(S[i] > 0)
            dpl[i+1][j+1] += dpl[i][j]*9 + dpj[i][j]*max(0,S[i]-1) 

print(dpl[n][k]+dpj[n][k])

Solution (Python):
from collections import Counter
N=input()
K=int(input())
km = len(N)
res = 0
if int(N)<=1000:
    for i in range(int(N)):
        c = Counter(str(i+1))
        if len(str(i+1)) - c['0']==K:
            res += 1
    print(res)
    exit()
d = [[0]*3 for _ in range(100001)]
for i in range(100000):
    d[i+1] = d[i][:]
    c = Counter(str(i+1))
    k=len(str(i+1)) - c['0']
    if k<=3:
        d[i+1][k-1] += 1
def rec(n,k):
    re = 0
    if int(n)<100000:
        re = 0
        return d[int(n)][k-1]
    if k==1:
        n = str(int(n))
        return 9*(len(n)-1)+int(n[0])
    t = ''.join(['9']*(len(n)-1))
    t2 = t
    w = (int(n[0])-1)
    if n[0] == '0':
        t2 = n[1:]
        w = 0
    return rec(t2, k) + w*rec(t2, k-1) + rec(str(int(n[1:])), k-1)
print(rec(N,K))

Solution (Python):
N = int(input())
K = int(input())
A = 0
if N <= 100000:
    for i in range(1,N+1):
        c = str(i)
        d = len(c) - c.count('0')

        if d == K:
            A += 1
else:
    keta = len(str(N))
    if K ==1:
        A = 9*(keta-1)
    if K ==2:
        A = 9*9*(keta-1)*(keta-2)//2
    if K ==3:
        A = 9*9*9*(keta-1)*(keta-2)*(keta-3)//6
    nc = 1

    while nc <= 3 and keta >=1:
        
        T = N//(10**(keta-1))%10

        if T == 0:
            keta -=1
        else:
            if (nc == 1 and K==1) or (nc==2 and K==2) or (nc==3 and K==3):
              A = A + (T)
            if ((nc == 1 and K ==2) or (nc ==2 and K==3)):
                A = A + int((T-1)*9*(keta-1))
            if (nc==2 and K==2) or (nc==3 and K==3):
                A = A + 9*(keta-1)
            if (nc==1 and K ==3):
                A = A + int((T-1)*9*9*(keta-1)*(keta-2)/2)
            if (nc==2 and K==3):
                A = A + int(9*9*(keta-1)*(keta-2)/2)
            nc +=1
            keta -=1

        
print(A)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
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 LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

S=input()
K=II()
DP=[[[0]*len(S) for _ in range(K+1)] for _ in range(2)]

for i in range(int(S[0])+1):
    if i < int(S[0]) and i > 0:
        DP[1][1][0] += 1
    elif i == 0:
        DP[1][0][0] = 1
    else:
        DP[0][1][0] = 1

for i in range(1, len(S)):
    n = int(S[i])
    DP[1][0][i] = DP[1][0][i-1]
    for j in range(K):
        DP[1][j+1][i] = (
            
            DP[1][j+1][i-1] +
            
            9*DP[1][j][i-1])
        if n != 0:
            DP[1][j+1][i] += (n-1)*DP[0][j][i-1]
            DP[0][j+1][i] = DP[0][j][i-1]

    for j in range(K+1):
        if n != 0:
            DP[1][j][i] += DP[0][j][i-1]
        else:
            DP[0][j][i] = DP[0][j][i-1]

print(DP[1][K][len(S)-1] + DP[0][K][len(S)-1])

Solution (Python):

import sys
import math
import numpy as np
import itertools


n = int(input())

k = int(input())

a=n
p=0
nn=[]
while a>0:
    p+=1
    r=a%10
    nn.insert(0,r)
    a=a//10



dp0=np.zeros((p+1,k+2),dtype="int64")
dp1=np.zeros((p+1,k+2),dtype="int64")

dp1[0][0]=1
for i in range(p):
    for j in range(k+1):
        dp0[i+1][j]    += dp0[i][j] + dp1[i][j] * (nn[i]>0)
        dp0[i+1][j+1]  += dp0[i][j] * 9 + dp1[i][j] * max(nn[i]-1,0)
        dp1[i+1][j]    += dp1[i][j] * (nn[i]==0)
        dp1[i+1][j+1]  += dp1[i][j] * (nn[i]!=0)
        

answer=dp0[p][k]+dp1[p][k]


print(answer)

Solution (Python):
N = input().strip()
n = len(N)
A = [0 for _ in range(n)]
A[0]=1
for i in range(1,n):
    if N[i]=="0":
        A[i] = A[i-1]
    else:
        A[i] = A[i-1]+1
K = int(input())
if K>n:
    print(0)
else:
    dp = [[[0 for _ in range(n+1)] for _ in range(2)] for _ in range(n+1)]
    dp[0][0][0] = 1
    for i in range(1,n+1):
        for k in range(n+1):
            if k==A[i-1]:
                dp[i][0][k] = 1
                break
    for i in range(1,n+1):
        for k in range(n+1):
            dp[i][1][k] = dp[i-1][1][k]
            if int(N[i-1])>0:
                dp[i][1][k] += dp[i-1][0][k]
            if k>=1:
                dp[i][1][k] += dp[i-1][1][k-1]*9
                if i==1 and k-1==0 and int(N[i-1])>=2:
                    dp[i][1][k] += dp[i-1][0][k-1]*(int(N[i-1])-1)
                elif i>=2 and k-1==A[i-2] and int(N[i-1])>=2:
                    dp[i][1][k] += dp[i-1][0][k-1]*(int(N[i-1])-1)
    print(dp[n][0][K]+dp[n][1][K])

Solution (Python):
import sys
from functools import lru_cache

sys.setrecursionlimit(10**3)

import math

n = 0
k = 0

def format_input(filename = None):
	global n
	global k
	if filename == None:
		n = list(map(int, input().split())).pop()
		k = list(map(int, input().split())).pop()

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 10**100)
		k = rng(1, 3)

@lru_cache(maxsize=None)
def comb_rec(n, k, digits):
	if digits < k - 1:
		return 0
	if k == 0:
		return 1
	if digits == 0:
		return n
	top = n // 10 ** digits
	if top == 0:
		combination = comb_rec(n, k, digits - 1)
	elif top == 1:
		combination = comb_rec(n - 10 ** digits, k - 1, digits - 1)
		combination += comb_rec(10 ** digits - 1, k, digits - 1)
	else:
		combination = comb_rec(n - top * 10 ** digits, k - 1, digits - 1)
		combination += (top - 1) * comb_rec(10 ** digits - 1, k - 1, digits - 1)
		combination += comb_rec(10 ** digits - 1, k, digits - 1)
	return combination


def get_answer():
	digits = math.floor(math.log10(n))
	answer = comb_rec(n, k, digits)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Solution (Python):
''' Hey stalker :) '''
INF = 10**10
def main():
    
    ''' Cook your dish here! '''
    n = list(input())
    k = get_int()
    ln = len(n)
    ans = 0
    def solve(nz, ind, locked = False):
        if nz == 0: return 1
        if ind>=ln: return 0
        num = int(n[ind])
        ans = 0
        for index in range(ind,ln):
            if locked and ind==index:
                if nz==1: ans += 1
                else:
                    for i in range(index+1, ln):
                        if int(n[i])>0:
                            ans += solve(nz-1, i, True)
                            break
                ans += solve(nz-1, index+1)*(num-1)
            else: ans += solve(nz-1, index+1)*9
            
        
        return ans

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


''' Pythonista fLite 1.1 '''
import sys
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right

import math

out = []
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
main()

print(*out, sep='\n')

Solution (Python):
strN = input()
N = int(strN)
K = int(input())
ans = 0
lenN = len(strN)
if K == 1:
    while(1):
        if N >= 10:
            ans += 9
            N //= 10
        else:
            ans += N
            break
elif K == 2:
    if lenN >= 2:
        index = 1
        while (index < lenN):
            if int(strN[index]) != 0:
                ans += 9 * (lenN - 1 - index)
                ans += int(strN[index])
                break
            index += 1
        ans += (int(strN[0]) - 1) * 9*(lenN-1)

        ans += 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)


elif K == 3:
    if lenN >= 3:
        index = 1
        index_2 = 0
        while (index < lenN and index_2 == 0):
            if int(strN[index]) != 0:
                ans += (int(strN[index]) - 1) * 9 * (lenN - 1 - index)
                ans += 9*9*(((lenN - 1-index) * (lenN - 2-index)) // 2)
                index_2 += index+1
                while (index_2 < lenN):
                    if int(strN[index_2]) != 0:
                        ans += int(strN[index_2])
                        ans += 9*(lenN-1-index_2)
                        break
                    index_2 += 1
            index += 1
        
        ans += (int(strN[0]) - 1) * 9 * 9 * (((lenN - 1) * (lenN - 2)) // 2)
        ans += 9*9*9*(((lenN-1)*(lenN-2)*(lenN-3))//6)
        
        
print(ans)

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

def keta1(n):
    s = str(n)
    return (len(s) - 1) * 9 + int(s[0])

def keta2(n):
    if n < 10:
      return 0
    s = str(n)
    cnt = [0] * 101
    for i in range(2, 101):
        cnt[i] = 9 * 9 * (i - 1)
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta1(10 ** (len(s) - 1) - 1) + keta1(int(s[1:]))
    return res

def keta3(n):
    s = str(n)
    cnt = [0] * 101
    for i in range(3, 101):
        cnt[i] = 9 * 9 * 9 * (i - 1) * (i - 2) // 2
    res = 0
    for i in range(len(s)):
        res += cnt[i]
    res += (int(s[0]) - 1) * keta2(10 ** (len(s) - 1) - 1) + keta2(int(s[1:]))
    return res

if K == 1:
    print(keta1(N))
elif K == 2:
    print(keta2(N))
elif K == 3:
    print(keta3(N))

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

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

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

for i in range(1, l):

    dp[i][1][0] = dp[i-1][1][0] + 9
    dp[i][2][0] = dp[i-1][2][0] + 9 * dp[i-1][1][0]
    dp[i][3][0] = dp[i-1][3][0] + 9 * dp[i-1][2][0]

    if int(n[i]) == 0:
        dp[i][1][1] = dp[i-1][1][1]

    elif dp[i-1][1][1] == 1:
        dp[i][2][1] = 1
        dp[i][2][0] += int(n[i])-1
        dp[i][1][0] += 1

    elif dp[i-1][2][1] == 1:
        dp[i][3][1] = 1
        dp[i][3][0] += int(n[i])-1
        dp[i][2][0] += 1

    elif dp[i-1][3][1] == 1:
        dp[i][3][0] += 1

print(sum(dp[-1][k]))

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)

def g(m, k):
    if k == 0:
        return 1
    if k == 1:
        return m * 9
    if k == 2:
        return m * (m-1) // 2 * 81
    if k == 3:
        return m * (m-1) * (m-2) // 6 * 729

@lru_cache(maxsize=None)
def f(n, k):
    if n == 0 and k:
        return 0
    if k == 0:
        return 1
    S = str(n)
    t = int(S[0])
    m = len(S)
    return f(int("0" + S[1:]), k-1) + ((t-1) * g(m-1, k-1) if t else 0) + g(m-1, k)

N = int(input())
K = int(input())
print(f(N, K))

Solution (Python):
def e_almost_everywhere_zero():
    def digit_dp(n):  
        """n 以下の非負整数で、0でない数字がちょうど K 個あるような数の個数"""
        digit = len(n)

        
        
        dp = [[[0] * (K + 2) for j in range(2)] for i in range(digit + 1)]
        dp[0][0][0] = 1
        for i in range(digit):
            for j in range(2):
                for k in range(K + 1):
                    lim = 9 if j == 1 else ord(n[i]) - ord('0')
                    for d in range(lim + 1):
                        
                        t = k + int(d != 0)
                        if t >= K + 1:
                            t = K + 1
                        dp[i + 1][j or (d < lim)][t] += dp[i][j][k]
        return sum(dp[digit][j][K] for j in range(2))

    N = input()
    K = int(input())
    return digit_dp(N)

print(e_almost_everywhere_zero())

Solution (Python):
n=int(input())
K=int(input())
if K==1:
    counter=0
    for i in range(100):
        for j in range(1,10):
            a="0"*(i)+str(j)+"0"*(99-i)
            if 1<=int(a)<=n:
                counter+=1
    print(counter)
elif K==2:
    counter=0
    for i in range(100):
        for j in range(i+1,100):
            for k in range(1,10):
                for l in range(1,10):
                    a="0"*(i)+str(k)+"0"*(j-i-1)+str(l)+"0"*(99-j)
                    if 1<=int(a)<=n:
                        counter+=1
    print(counter)
elif K==3:
    counter=0
    for i in range(100):
        if 100-i>len(str(n)):
            pass
        elif 100-i<len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):
                    counter+=9*9*9
        elif 100-i==len(str(n)):
            for j in range(i+1,100):
                for k in range(j+1,100):

                        for b in range(1,10):
                            for c in range(1,10):
                                P=(str(n)[0])+"0"*(j-i-1)+str(b)+"0"*(k-j-1)+str(c)+"0"*(99-k)
                                if 1<=int(P)<=n:
                                    counter+=1
            counter+=((98-i)*(99-i)//2)*9*9*(int(str(n)[0])-1)
    print(counter)

Solution (Python):

from collections import defaultdict

N=raw_input()
K=input()

dp=defaultdict(lambda: 0)  

l=len(N)

for i in range(l):
    x=int(N[i])
    i+=1
    if i==1:
        if x==1:
            dp[("T",i,0)]=1
            dp[("F",i,1)]=1
        else:
            dp[("T",i,0)]=1
            dp[("T",i,1)]=x-1
            dp[("F",i,1)]=1
    else:
        for k in range(K+1):
            dp[("T",i,k)]+=dp[("T",i-1,k)]
            dp[("T",i,k+1)]+=dp[("T",i-1,k)]*9
            if 0<x:
                dp[("T",i,k+1)]+=dp[("F",i-1,k)]*(x-1) 
                dp[("T",i,k)]+=dp[("F",i-1,k)]  
                dp[("F",i,k+1)]+=dp[("F",i-1,k)]*1 
            else: 
                dp[("F",i,k)]+=dp[("F",i-1,k)]*1
        
print dp[("T",l,K)]+dp[("F",l,K)]

Solution (Python):
from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)
def f(N, K):
    if K == 0: return 1
    if N < 10:
        if K == 1: return N
        return 0
    q, r = divmod(N, 10)
    ret = 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))

Solution (Python):
import math
n = int(input())
k = int(input())
ans = 0


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


def partical(L, K, M):  
    res = 0
    
    if L - K > 1:
        res += combinations_count(L - 1, K) * (9 ** K)
    
    if L > 1 and K > 1:
        res += (M - 1) * combinations_count(L - 1, K - 1) * (9 ** (K - 1))
    
    if K == 1:
        res += M
    return res


def calcLM(target):
    L = len(str(target))
    M = int(str(target)[0])
    return (L, M)


while k > 0:
    L, M = calcLM(n)
    ans += partical(L, k, M)
    n = n - int(str(n)[0]) * (10 ** (len(str(n))-1))
    k = k - 1

print(ans)

Solution (Python):
N = input()
lN = len(N)
n0 = int(N[0])
K = int(input())





dp = [[[0, 0] for k in range(K+1)] for i in range(lN)]

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

dp[0][1] = [n0-1, 1]

for i, n in enumerate(N[1:], 1):
  dp[i][0] = [1, 0] 
  if n == '0': 
    for k in range(1, K+1):
      dp[i][k][0] = dp[i-1][k][0] + dp[i-1][k-1][0]*9
      dp[i][k][1] = dp[i-1][k][1]
  
  else: 
    for k in range(1, K+1):
      dp[i][k][0] = sum(dp[i-1][k]) + dp[i-1][k-1][0]*9 + dp[i-1][k-1][1]*(int(n)-1)
      dp[i][k][1] = dp[i-1][k-1][1]


print(sum(dp[-1][K]))

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

ans = 0


def k1(n):
    str1_n = str(n)
    keta1 = len(str1_n)
    cnt = 9 * (keta1 - 1) + int(str1_n[0])
    return cnt


def k2(n):
    str2_n = str(n)
    keta2 = len(str2_n)
    cnt = 81 * (keta2 - 1) * (keta2 - 2) // 2
    cnt += (int(str2_n[0]) - 1) * k1(10 ** (keta2 - 1) - 1)
    cnt += k1(n - (int(str2_n[0]) * 10 ** (keta2 - 1)))
    return cnt


def k3(n):
    str3_n = str(n)
    keta3 = len(str3_n)
    t = 0
    for i in range(keta3-2):
        t += (i+1)*i//2
    cnt = 729 * t
    cnt += (int(str3_n[0]) - 1) * k2(10 ** (keta3 - 1) - 1)
    cnt += k2(n - (int(str3_n[0]) * 10 ** (keta3 - 1)))
    return cnt


if k == 1:
    ans = k1(n)

if k == 2:
    ans = k2(n)

if k == 3:
    ans = k3(n)

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K):
    N = int(N)
    @lru_cache(maxsize=None)
    def f(n, k):
        if k == 0:
            return 1
        m = n % 10
        l = n // 10
        if l == 0 and k == 1:
            return m
        elif l == 0:
            return 0
        return f(l, k-1)*m + f(l-1, k-1)*(9-m) + f(l, k)


    return f(N, K)


def f(N, K):
    M = len(N)
    N = int(N)
    ans = 0
    for i in range(N+1):
        n = str(i).count('0')
        if len(str(i)) - n == K:
            ans += 1
            
    return ans

def main():
    N = read_str()
    K = read_int()
    print(slv(N, K))

    

    
    
    
    
    
    
    
    
    
    
    
    



if __name__ == '__main__':
    main()