#!/usr/bin/env python3
import sys

# Python Program to find the count of 
# numbers in a range where the number 
# does not contain more than K non 
# zero digits 
  
# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num, K): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt == K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num, K) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x, K): 
    global dp, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num, K) 

def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
dp = []
M = 100

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


38f51e963a3c1719052f0f279d9d652f35e2dabb
<mask token>


def countInRangeUtil(pos, cnt, tight, num, K):
    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, K)
    dp[pos][cnt][tight] = ans
    return dp[pos][cnt][tight]


def countInRange(x, K):
    global dp, 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, K)


<mask token>

<mask token>


def countInRangeUtil(pos, cnt, tight, num, K):
    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, K)
    dp[pos][cnt][tight] = ans
    return dp[pos][cnt][tight]


def countInRange(x, K):
    global dp, 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, K)


def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


<mask token>


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    K = int(next(tokens))
    solve(N, K)


if __name__ == '__main__':
    main()

<mask token>


def countInRangeUtil(pos, cnt, tight, num, K):
    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, K)
    dp[pos][cnt][tight] = ans
    return dp[pos][cnt][tight]


def countInRange(x, K):
    global dp, 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, K)


def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


dp = []
M = 100


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    K = int(next(tokens))
    solve(N, K)


if __name__ == '__main__':
    main()

import sys


def countInRangeUtil(pos, cnt, tight, num, K):
    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, K)
    dp[pos][cnt][tight] = ans
    return dp[pos][cnt][tight]


def countInRange(x, K):
    global dp, 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, K)


def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


dp = []
M = 100


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    K = int(next(tokens))
    solve(N, K)


if __name__ == '__main__':
    main()

#!/usr/bin/env python3
import sys

# Python Program to find the count of 
# numbers in a range where the number 
# does not contain more than K non 
# zero digits 
  
# This function returns the count of 
# required numbers from 0 to num 
def countInRangeUtil(pos, cnt, tight, num, K): 
  
    # Last position 
    if pos == len(num): 
  
        # If count of non zero digits 
        # is less than or equal to K 
        if cnt == K: 
            return 1
        return 0
  
    # If this result is already computed 
    # simply return it 
    if dp[pos][cnt][tight] != -1: 
        return dp[pos][cnt][tight] 
  
    ans = 0
  
    # Maximum limit upto which we can place 
    # digit. If tight is 1, means number has 
    # already become smaller so we can place 
    # any digit, otherwise num[pos] 
    limit = 9 if tight else num[pos] 
  
    for dig in range(limit + 1): 
        currCnt = cnt 
  
        # If the current digit is nonzero 
        # increment currCnt 
        if dig != 0: 
            currCnt += 1
  
        currTight = tight 
  
        # At this position, number becomes 
        # smaller 
        if dig < num[pos]: 
            currTight = 1
  
        # Next recursive call 
        ans += countInRangeUtil(pos + 1, currCnt, currTight, num, K) 
  
    dp[pos][cnt][tight] = ans 
    return dp[pos][cnt][tight] 
  
# This function converts a number into its 
# digit vector and uses above function to compute 
# the answer 
def countInRange(x, K): 
    global dp, M 
  
    num = [] 
    while x: 
        num.append(x % 10) 
        x //= 10
  
    num.reverse() 
  
    # Initialize dp 
    dp = [[[-1, -1] for i in range(M)] for j in range(M)] 
    return countInRangeUtil(0, 0, 0, num, K) 

def solve(N: int, K: int):
    ans = countInRange(N, K) - countInRange(0, K)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
dp = []
M = 100

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

