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):
def main():

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

    if K == 1:
        v = (len(S) - 1) * 9
        v += int(S[0])
        return v
    if K == 2:
        v = (len(S)-1) * (len(S)-2) * 9 * 9 // 2
        v += (int(S[0]) - 1) * 9 * (len(S)-1)
        u = int(S[0]) * pow(10, len(S)-1)
        for j in range(len(S)-1):
            for k in range(1, 10):
                if u + k * pow(10, j) <= N:
                    v += 1
        return v
    if K == 3:
        v = (len(S)-1) * (len(S)-2) * (len(S)-3) * 9 * 9 * 9 // 6
        v += (int(S[0]) - 1) * 9 *9 * (len(S)-1) * (len(S)-2) // 2
        u = int(S[0]) * pow(10 ,len(S)-1)
        ps = [1]
        for i in range(len(S)+1):
            ps.append(ps[-1] * 10)
        for j1 in range(len(S)-1):
            for j2 in range(j1):
                for k1 in range(1, 10):
                    for k2 in range(1, 10):
                        if u + k1 * ps[j1] + k2 * ps[j2] <= N:
                            v += 1
        return v


if __name__ == '__main__':
    print(main())

Solution (Python):
def countInRangeUtil(pos, cnt, tight, num): 
  
    
    if pos == len(num): 
  
        
        
        if cnt <= K: 
            return 1
        return 0
  
    
    
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    
    
    
    
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        
        
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        
        
        if dig < num[pos]: 
            currTight = 1
  
        
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  



def countInRange(x): 
    global dp, K, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num) 
  

a = int(input())
b = int(input())
dp = [] 

M = 100
R = a
K = b
m = countInRange(R)

dp = [] 
M = 100
R = a
K = b - 1
n = countInRange(R)

print(m - n)

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


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

Solution (Python):

from functools import reduce
import operator
product = lambda it: reduce(operator.mul,it,1)

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

comb = lambda n, k: product(range(n-k+1,n+1))//product(range(1,k+1))

def rec(i, k):
    if k == 0:
        return 1
    if len(N) < k + i:
        return 0
    return (max(0,int(N[i])-1)*(9**(k-1))*comb(len(N)-i-1, k-1) +
            (rec(i+1,k) if N[i] == '0' else rec(i+1,k-1) + (9**k)*comb(len(N)-i-1, k)))

print(rec(0,K))

Solution (Python):

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

def solve(num, k_):
    
    
    n = len(str(num)) + 1
    dp = [[[0 for _ in range(k_+2)] for _ in range(2)] for _ in range(n)]
    dp[0][0][0] = 1

    for i in range(n-1):
        D = int(str(num)[i])
        for j in range(2):
            for k in range(k_+1):
                for d in range(10 if j else D+1):
                    if d == 0:
                        dp[i+1][j or (d < D)][k] += dp[i][j][k]
                    else:
                        dp[i+1][j or (d < D)][k+1] += dp[i][j][k]
    return dp[-1][0][k_] + dp[-1][1][k_]

print(solve(n, k))

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

memo = [
    collections.defaultdict(int),
    collections.defaultdict(int),
    collections.defaultdict(int),
    collections.defaultdict(int)
]


def rec(n, k):
    if k == 0:
        return 1
    elif n < 10:
        if k == 1:
            return n
        else:
            return 0
    elif n in memo[k]:
        return memo[k][n]
    digit = len(str(n))
    top = (n // (10**(digit - 1))) * 10**(digit - 1)
    residue = n - top
    hoge = rec(top - 1, k) + rec(residue, k - 1)
    memo[k][n] = hoge
    return hoge


print(rec(N, K))

Solution (Python):
n = input()
k = int(input())
l = len(n)
dp = [[[0 for i in range(2)] for t in range(3+1)] for j in range(l+1)]
dp[0][0][0] = 1
for i in range(1,l+1):
  for j in range(k+1):
    x = int(n[i-1])
    if x != 0:
      for m in range(1,3+1):
        dp[i][m][0] = dp[i-1][m-1][0]
    else:
      for m in range(3+1):
        dp[i][m][0] = dp[i-1][m][0]
    dp[i][0][1] = dp[i-1][0][0]+dp[i-1][0][1]
    dp[i][1][1] = dp[i-1][0][1]*9+dp[i-1][1][1]+dp[i-1][0][0]*(max(0,x-1))+dp[i-1][1][0]*(x>0)
    dp[i][2][1] = dp[i-1][1][1]*9+dp[i-1][2][1]+dp[i-1][1][0]*(max(0,x-1))+dp[i-1][2][0]*(x>0)
    dp[i][3][1] = dp[i-1][2][1]*9+dp[i-1][3][1]+dp[i-1][2][0]*(max(0,x-1))+dp[i-1][3][0]*(x>0)
print(dp[l][k][0]+dp[l][k][1])

Solution (Python):

N = input()

K = int(input())

lis =  [ [ [0,0] for i in range(K+1) ] for j in range(len(N) + 1) ]



lis[0][0][0] = 1

for i in range(len(N)):

    nketa = int(N[i])

    for num in range(K):

        for flag in range(2):


            if num == 0 and flag == 0:

                lis[i+1][num+1][0] += lis[i][num][flag]
                lis[i+1][num+1][1] += (nketa - 1) * lis[i][num][flag]
                lis[i+1][num][1] += lis[i][num][flag]

            if num != K and flag == 0:

                if nketa == 0:
                    lis[i+1][num][0] += lis[i][num][flag]
                else:
                    lis[i+1][num+1][0] += lis[i][num][flag]
                    lis[i+1][num][1] += lis[i][num][flag]
                    lis[i+1][num+1][1] += lis[i][num][flag] * (nketa - 1)
                

            if num != K and flag == 1:

                lis[i+1][num+1][1] += 9 * lis[i][num][flag]
                lis[i+1][num][1] += lis[i][num][flag]

ans = 0



for i in range(len(N) + 1):

    for j in range(2):

        ans += lis[i][K][j]

print (ans //2 )

Solution (Python):
class S:
    def solve(self, n, k):
        self.n = n
        return self.dfs(0, k, False)
    def dfs(self, x, y, free=False):
        if y == 0:
            return 1
        if x >= len(self.n):
            return 0
        if free:
            return 9 * self.dfs(x + 1, y - 1, free) + self.dfs(x + 1, y, free)
        else:
            t = int(self.n[x])
            r = 0
            if t > 0:
                r += 1 * self.dfs(x + 1, y - 1, False)
                r += (t - 1) * self.dfs(x + 1, y - 1, True)
            r += self.dfs(x + 1, y, t > 0)
            return r


n = raw_input()
k = input()
print S().solve(n, k)

Solution (Python):
n = input()
km = int(input())
dp1 = [[0] * (4) for _ in range(len(n) + 1)]
dp2 = [[0] * (4) for _ in range(len(n) + 1)]
dp1[0][0] = 1
for i in range(len(n)):
    for j in range(4):
        if n[i] == '0':
            dp1[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        else:
            dp2[i + 1][j] += dp1[i][j]
            dp2[i + 1][j] += dp2[i][j]
        if j < 3:
            for k in range(1, ord(n[i]) - ord('0')):
                dp2[i + 1][j + 1] += dp1[i][j]
            if n[i] != '0':
                dp1[i + 1][j + 1] += dp1[i][j]
            for k in range(1, 10):
                dp2[i + 1][j + 1] += dp2[i][j]
print(dp1[len(n)][km] + dp2[len(n)][km])

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

def comb(n,k):
    if k==0:
        return 1
    if k==1:
        return n
    if k==2:
        return (n*(n-1))//2
    if k==3:
        return (n*(n-1)*(n-2))//6

def rec(n,k):
    res = 0
    if k < 0:
        return res
    if k==0:
        res = 1
        return res
    if len(n)<k:
        return res
    if n[0] != '0':
        res += rec(n[1:],k-1)
        res += (int(n[0])-1)*comb(len(n)-1,k-1)*9**(k-1)
        res += comb(len(n)-1,k)*9**k
    else:
        res += rec(n[1:],k)
    return res

print(rec(N,K))

Solution (Python):
from itertools import combinations

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


if k == 1:
	print(9 * (len(s)-1) + int(s[0]))

elif k == 2:
	if len(s) == 1:
		print(0)
	elif len(s) == 2:
		print(n - 9 - n//10)
	else:
		ans = 81 * (l-1) * (l-2) // 2
		for i in range(1, 10):
			for x in range(l-1):
				for j in range(1, 10):
					if i * (10**(l-1)) + j * (10**x) <= n:
						ans += 1
		print(ans)

else:
	if len(s) < 3:
		print(0)
	elif len(s) == 3:
		ans = 0
		for i in range(100, n+1):
			if "0" not in list(str(i)):
				ans += 1
		print(ans)
	else:
		ans = 729 * (l-1) * (l-2) * (l-3) // 6
		ans += (int(s[0])-1) * (l-1) * (l-2) * 81 // 2
		for x, y in combinations(range(l-1), 2):
			for z in range(81):
				j, k = (z//9) + 1, (z%9) + 1
				if int(s[0]) * (10**(l-1)) + j * (10**x) + k * (10**y) <= n:
					ans += 1
		print(ans)

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

def fact(x):
  r = 1
  while x>0:
    r *= x
    x -= 1
  return r

def comb(x, y):
  if y>x:
    return 0
  return fact(x)/fact(y)/fact(x-y)

N = str(N+1)
def f(d, k):
  if k==0:
    if d>=len(N) or int(N[d:])==0:
      return 0
    else:
      return 1
  while d<len(N) and N[d]=="0":
    d += 1
  if d>=len(N):
    return 0
  return (
    comb(len(N)-d-1, k)*9**k +
    (int(N[d])-1)*comb(len(N)-d-1, k-1)*9**(k-1) +
    f(d+1, k-1))

print f(0, K)

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

def f(N,K):
    if K==0: return 1
    if N=="": return 0
    N=str(int(N))
    if N==0 : return 0
    l = len(N)
    n0 = int(N[0])
    return f(N[1:],K-1) + f("9"*(l-1),K-1)*(n0-1) + f("9"*(l-1),K)

print(f(N,K))

Solution (Python):
import sys
sys.stdin.readline

def main():
    N, K = input(), int(input())
    S = "0"*(100-len(N))+N
    DP = [[[0] * 2 for _ in range(K+2)] for _ in range(101)]
    DP[0][0][0] = 1
    for i in range(100):
        for j in range(K+1):
            DP[i+1][j][0] += DP[i][j][0] * (S[i] == "0")
            DP[i+1][j+1][0] += DP[i][j][0] * (S[i] != "0")
            DP[i+1][j][1] += DP[i][j][1] + DP[i][j][0] * (int(S[i]) > 0)
            DP[i+1][j+1][1] += DP[i][j][1] * 9 + DP[i][j][0] * max(0, int(S[i])-1)
    print(sum(DP[-1][K]))

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    S = input()
    N = len(S)
    K = int(input())
    dp = [[[0]*(4) for j in range(2)] for i in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            for k in range(4):
                lim = (9 if j else int(S[i]))
                for d in range(lim + 1):
                    if k + (d != 0) > 3:
                        continue
                    dp[i+1][j or d < lim][k + (d != 0)] += dp[i][j][k]
    ans = 0
    for j in range(2):
        ans += dp[N][j][K]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from functools import lru_cache

N, K = map(int,read().split())

@lru_cache(None)
def F(N, K):
    """N以下で0でないものがちょうどK個。0を含める"""
    assert N >= 0
    if N < 10:
        if K == 0:
            return 1
        if K == 1:
            return N
        return 0
    q,r = divmod(N,10)
    ret = 0
    if K >= 1:
        
        ret += F(q, K-1) * r
        ret += F(q-1, K-1) * (9-r)
    
    ret += F(q, K)
    return ret



print(F(N, K))

Solution (Python):
N = input()
l = len(N)
K = int(input())
dp = [[[0]*2 for i in range(K+1)] for j in range(l)]
dp[0][0][0] = 1
dp[0][1][0] = int(N[0])-1
dp[0][1][1] = 1
for i in range(l-1):
    for j in range(K+1):
        for d in range(10):
            if d == 0:
                dp[i+1][j][0] += dp[i][j][0]
                if N[i+1] == '0':
                    dp[i+1][j][1] += dp[i][j][1]
                else:
                    dp[i+1][j][0] += dp[i][j][1]
            else:
                if j==K:
                    continue
                dp[i+1][j+1][0] += dp[i][j][0]
                if int(N[i+1])>d:
                    dp[i+1][j+1][0] += dp[i][j][1]
                elif int(N[i+1])==d:
                    dp[i+1][j+1][1] += dp[i][j][1]
print(dp[-1][-1][0]+dp[-1][-1][1])

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

mod = 10**9 + 7
l = 2*10**2

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  
    return pow(x, mod-2, mod)



MI = [0] * (l-1) +[inv(M[l-1], mod)]  
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  
    if y < 0 or y > x:
        return 0
    ans = M[x]
    ans = (ans * MI[y]) % mod
    return (ans * MI[x-y]) % mod

ans = 0
k = kk
for i in range(len(n)):
    s = int(n[i])
    z = len(n)-i-1
    
    if s >= 1 and k >= 0:
        ans += C(z, k) * (9**k) + C(z, k-1) * (9**(k-1)) * (s-1)
        k -= 1
    
if n.count("0") == len(n)-kk:
    ans += 1
print(int(ans))

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

Solution (Python):
def main():
    N=[int(x) for x in list(input())]
    k=int(input())
    digit=len(N)
    if k>digit:
        return 0
    DP=[[[0]*(digit+1) for _ in range(2)] for _ in range(digit+1)] 
    DP[0][0][0]=1
    for d in range(digit):
        for less in range(2):
            for num in range(digit):
                limit=9 if less else N[d]
                for l in range(limit+1):
                    DP[d+1][less or l<limit][num+(l==0)]+=DP[d][less][num]
    return DP[-1][0][digit-k]+DP[-1][1][digit-k]
    
    
if __name__=='__main__':
    print(main())

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


dp = [[[0] * 2 for i in range(4)] for i in range(keta + 1)]
dp[0][0][0] = 1

for i in range(keta):
    
    if n[i] == "0":
        for j in range(4):
            dp[i + 1][j][0] += dp[i][j][0]
    else:
        for j in range(3):
            dp[i + 1][j + 1][0] += dp[i][j][0]
    
    
    for ii in range(int(n[i])):
        if ii == 0:
            for j in range(4):
                dp[i + 1][j][1] += dp[i][j][0]
        else:
            for j in range(3):
                dp[i + 1][j + 1][1] += dp[i][j][0]
    
    for ii in range(10):
        if ii == 0:
            for j in range(4):
                dp[i + 1][j][1] += dp[i][j][1]
        else:
            for j in range(3):
                dp[i + 1][j + 1][1] += dp[i][j][1]
print(sum(dp[keta][k]))

Solution (Python):
import sys

stdin = sys.stdin

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

n = str(ni() + 1)
m = len(n)
k = ni()


def C(n, k):
    if n < k or n < 0 or k < 0: return 0
    x = 1
    for i in range(k):
        x = x * (n-i)
        x = x // (i+1)
    return x

def p(x, k):
    y = 1
    for i in range(k):
        y *= x
    return y

e = 0
ans = 0
for i in range(m):
    d = ord(n[i]) - ord("0")
    if i == 0:
        if d > 1:
            ans += (d-1)*C(m-1, k-1)*p(9,k-1)
    else:
        ans += 9*C(m-1-i, k-1)*p(9,k-1)
        if d > 0:
            ans += (d-1)*C(m-1-i, k-1-e)*p(9,k-1-e)
            ans += C(m-1-i, k-e)*p(9,k-e)
    if d > 0:
        e += 1
print(ans)

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

strN = str(N)
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 isLeN in range(2):
        for m in range(K+1):
            x = 0
            if not isLeN and x > Nd: continue
            isLeN2 = isLeN or x < Nd
            dp[d+1][isLeN2][m] += dp[d][isLeN][m]
            for x in range(1, 10):
                if not isLeN and x > Nd: continue
                isLeN2 = isLeN or x < Nd
                m2 = m+1
                if m2 > K: continue
                dp[d+1][isLeN2][m2] += dp[d][isLeN][m]



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

Solution (Python):
import sys

stdin = sys.stdin

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

n = ns()
k = ni()
dp = [[[0]*2 for _ in range(k+1)] for _ in range(len(n)+1)]
dp[0][0][0] = 1
for i in range(len(n)):
    x = int(n[i])
    for j in range(k):
        dp[i+1][j+1][1] += dp[i][j][1]*9
        dp[i+1][j][1] += dp[i][j][1]
        if x > 0:
            dp[i+1][j][1] += dp[i][j][0]
            dp[i+1][j+1][1] += dp[i][j][0]*(x-1)
            dp[i+1][j+1][0] += dp[i][j][0]
        else:
            dp[i+1][j][0] += dp[i][j][0]
    dp[i+1][k][1] += dp[i][k][1]
    dp[i+1][k][x>0] += dp[i][k][0]
print(sum(dp[len(n)][k]))

Solution (Python):
from functools import lru_cache
n = list(map(int, list(input())))
k = int(input())

@lru_cache(10**9)
def rec(keta, cnt, tight):
    if cnt > k:
        return 0
    if keta==len(n):
        if cnt==k:
            return 1
        else:
            return 0
    ret = 0
    for i in range(10):
        if tight and i > n[keta]:
            break
        ret += rec(keta+1, cnt+int(i!=0), tight and i==n[keta])
    return ret

ans = rec(0,0, True)
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = list(map(int, input()))
    K = I()
    l = len(n)
    if l < K:
        print(0)
        return
    dp = [[[0 for k in range(l+1)] for j in range(2)] for i in range(l+1)]
    dp[0][0][0] = 1
    for i in range(l):
        ni = i+1
        for j in range(2):
            for k in range(l):
                x = 9 if j else n[i]
                for d in range(x+1):
                    nk = k+(d!=0)
                    nj = j or d < n[i]
                    if nk <= l:
                        dp[ni][nj][nk] += dp[i][j][k]
    
    print(dp[l][0][K]+dp[l][1][K])
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def examA():
    S, T = LSI()
    A, B = LI()
    U = SI()
    if S==U:
        print(A-1,B)
    else:
        print(A,B-1)
    return

def examB():
    S = SI()
    N = len(S)
    ans = ""
    for i in range(N):
        ans += "x"
    print(ans)
    return

def examC():
    N = I()
    A = LI()
    d = defaultdict(int)
    for a in A:
        d[a] += 1
        if d[a]>=2:
            print("NO")
            return
    print("YES")
    return

def examD():
    N, K = LI()
    P = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = S[i]+(P[i]+1)/2
    ans = 0
    for i in range(N-K+1):
        cur = S[i+K]-S[i]
        ans = max(ans,cur)
    print(ans)
    return

def examE():
    def ketadp(a,K):
        n = len(a)
        C = [i for i in range(K+1)]
        dp = defaultdict(int)
        dp[0, 0, 0] = 1
        for i, less, k in itertools.product(range(n), (0, 1), C):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                if d==0:
                    dp[i + 1, less_, k] += dp[i, less, k]
                elif k<K:
                    dp[i + 1, less_, k+1] += dp[i, less, k]

        ans = sum(dp[n, less, K] for less in (0, 1))
        return ans
    N = SI()
    K = I()
    ans = ketadp(N,K)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Solution (Python):
def solve(i, k, lesser, zero):
	global s, dp

	if k < 0:
		return 0

	if i == len(s):
		return 1 if k == 0 and not zero else 0

	if dp[i][k][lesser][zero] != -1:
		return dp[i][k][lesser][zero]

	if lesser:
		dp[i][k][lesser][zero] = solve(i + 1, k, True, zero)

		for d in range(1, 10):
			dp[i][k][lesser][zero] += solve(i + 1, k - 1, True, False)
	else:
		dp[i][k][lesser][zero] = solve(i + 1, k, 0 < s[i], zero)
		
		for d in range(1, s[i] + 1):
			dp[i][k][lesser][zero] += solve(i + 1, k - 1, d < s[i], False)

	return dp[i][k][lesser][zero]

def main():
	global s, dp

	s = list(input())
	k = int(input())

	for i in range(len(s)):
		s[i] = ord(s[i]) - ord('0')

	dp = [[[[-1, -1], [-1, -1]] for j in range(k + 1)] for i in range(len(s) + 1)]

	print(solve(0, k, False, True))

if __name__ == "__main__":
	main()

Solution (Python):



import sys
readline = sys.stdin.readline
read = sys.stdin.read




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

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

for c in n:
    ndp = [[0]*k for _ in range(2)]
    ni = int(c)
    for is_less in range(2):
        for num in range(k):
            for d in range(10 if is_less else ni+1):
                if d == 0:
                    ndp[is_less or d < ni][num] += dp[is_less][num]
                elif num < k-1:
                    ndp[is_less or d < ni][num+1] += dp[is_less][num]

    dp = ndp



print(sum(i[-1] for i in dp))

Solution (Python):
N = input()
K = int(input())
L = len(N)
dp = [[[0]*4 for _ in range(2)] for _ 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 in range(10 if j else D+1):
            for k in range(4):
                if d==0:
                    dp[i+1][j|(d<D)][k] += dp[i][j][k]
                else:
                    if k+1<=3:
                        dp[i+1][j|(d<D)][k+1] += dp[i][j][k]
    
print(dp[L][0][K]+dp[L][1][K])