AtCoder Beginner Contest 154 - Almost Everywhere Zero

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-----
100
1

-----Sample Output-----
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

Difficulty: MEDIUM

Starter code:

Solutions:
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal

class Scanner:

	@staticmethod
	def int():
		return int(sys.stdin.readline().rstrip())

	@staticmethod
	def string():
		return sys.stdin.readline().rstrip()

	@staticmethod
	def map_int():
		return [int(x) for x in Scanner.string().split()]

	@staticmethod
	def string_list(n):
		return [Scanner.string() for i in range(n)]

	@staticmethod
	def int_list_list(n):
		return [Scanner.map_int() for i in range(n)]

	@staticmethod
	def int_cols_list(n):
		return [Scanner.int() for i in range(n)]

def pop_count(x):
	x = x - (x >> 1 & 6148914691236517205)
	x = (x & 3689348814741910323) + (x >> 2 & 3689348814741910323)
	x = x + (x >> 4) & 1085102592571150095
	x = x + (x >> 8)
	x = x + (x >> 16)
	x = x + (x >> 32)
	return x & 127

def solve():
	S = Scanner.string()
	N = len(S)
	K = Scanner.int()
	dp = [[[0 for _ in range(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(4):
			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]
	print(dp[N][K][0] + dp[N][K][1])

def main():
	solve()

def __starting_point():
	main()
__starting_point()


import numpy as np

def solve(S, N, K):
	dp = np.zeros((N + 1, 2, K + 1), dtype=np.int64)
	dp[0][0][0] = 1
	for i in range(N):
		for is_less in range(2):
			for k in range(K + 1):
				for l in range(10 if is_less else S[i] + 1):
					k_ = k + (l > 0)
					if k_ > K:
						continue
					is_less_ = is_less or l < S[i]
					dp[i + 1][int(is_less_)][k_] += dp[i][is_less][k]
	return dp[N][0][K] + dp[N][1][K]
S = np.array([c for c in input()], dtype=np.int64)
N = len(S)
K = int(input())
print(solve(S, N, K))


N = input()
K = int(input())
if len(N) < K:
	print(0)
	return
keta = []
for k in range(len(N)):
	keta.append(int(N[-k - 1]))
ans = [1, keta[0], 0, 0]

def combination(N, K):
	if N < K:
		return 0
	else:
		p = 1
		for k in range(K):
			p *= N
			N -= 1
		for k in range(1, K + 1):
			p //= k
		return p
for k in range(1, len(N) - 1):
	if keta[k] > 0:
		a = [1, 0, 0, 0]
		for j in range(1, 4):
			a[j] += 9 ** j * combination(k, j)
			a[j] += (keta[k] - 1) * combination(k, j - 1) * 9 ** (j - 1) + ans[j - 1]
		ans = [] + a
answer = 9 ** K * combination(len(N) - 1, K)
answer += (keta[-1] - 1) * 9 ** (K - 1) * combination(len(N) - 1, K - 1)
answer += ans[K - 1]
print(answer)


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


import sys
sys.setrecursionlimit(10 ** 4)
from math import factorial

def comb(n, r):
	if r == 0:
		return 1
	if n == 0 or r > n:
		return 0
	return factorial(n) // factorial(n - r) // factorial(r)

def f(S, i, k):
	if k == 0:
		return 1
	if len(S) <= i:
		return 0
	n = int(S[i])
	if n == 0:
		return f(S, i + 1, k)
	ret = (n - 1) * comb(len(S) - i - 1, k - 1) * pow(9, k - 1)
	ret += comb(len(S) - i - 1, k) * pow(9, k)
	ret += f(S, i + 1, k - 1)
	return ret

def solve(S: str, K: int):
	return f(S, 0, K)

def main():

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

def test():
	import doctest
	doctest.testmod()

def __starting_point():
	test()
	main()
__starting_point()


n = [int(x) for x in list(input())]
l = len(n)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(l + 1)]
dp[1][0][0] = 1
dp[1][1][0] = n[0] - 1
dp[1][1][1] = 1
for i in range(2, l + 1):
	for j in range(0, min(i, k) + 1):
		if j > 0:
			dp[i][j][1] += dp[i - 1][j - 1][1] * (n[i - 1] > 0)
			dp[i][j][0] += dp[i - 1][j - 1][0] * 9 + dp[i - 1][j - 1][1] * max(0, n[i - 1] - 1)
		dp[i][j][1] += dp[i - 1][j][1] * (n[i - 1] == 0)
		dp[i][j][0] += dp[i - 1][j][0] + dp[i - 1][j][1] * (n[i - 1] > 0)
print(sum(dp[l][k]))


N = list(map(int, input()))
K = int(input())
L = len(N)
dp = [[[0] * (L + 1) for _ in range(4)] for _ in range(2)]
dp[0][0][0] = 1
for i in range(2):
	for j in range(4):
		for k in range(L):
			for d in range(10 if i else N[k] + 1):
				fl = 1 if i == 1 or d < N[k] else 0
				cnt = j + 1 if d != 0 else j
				if cnt > K:
					continue
				dp[fl][cnt][k + 1] += dp[i][j][k]
print(dp[0][K][L] + dp[1][K][L])


import math

def comb(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
K = int(input())
keta = len(str(N))
dp = [[0] * keta for i in range(4)]
ans = 0
for k in range(1, 4):
	for i in range(1, keta):
		if i < k:
			continue
		else:
			dp[k][i] = comb(i - 1, i - k) * 9 ** k
ans += sum(dp[K])
count = 0
for j in range(keta):
	t = int(str(N)[j])
	if j == 0:
		count += 1
		ans += sum(dp[K - count]) * (t - 1)
		if count == K:
			ans += t
			break
		continue
	elif j == keta - 1:
		if t != 0:
			count += 1
		if count == K:
			ans += t
		break
	if t != 0:
		count += 1
		if count == K:
			ans += sum(dp[K - count + 1][:keta - j])
			ans += t
			break
		ans += sum(dp[K - count][:keta - j]) * (t - 1)
		ans += sum(dp[K - count + 1][:keta - j])
print(ans)


(n, k) = open(0)
k = int(k)
d = [1] + [0] * 7
for n in map(int, n[:-1]):
	p = [0] * 8
	for i in range(n):
		if i < 1:
			for j in range(4):
				p[j + 4] += d[j]
		else:
			for j in range(3):
				p[j + 5] += d[j]
	for i in range(10):
		if i < 1:
			for j in range(4):
				p[j + 4] += d[j + 4]
		else:
			for j in range(3):
				p[j + 5] += d[j + 4]
	if n < 1:
		for i in range(4):
			p[i] += d[i]
	else:
		for i in range(3):
			p[i + 1] += d[i]
	d = p
print(sum(d[k::4]))


N = input()
K = int(input())
L = len(N)
dp = [[[0 for _ in range(2)] for _ in range(5)] for _ in range(len(N) + 1)]
dp[0][1][1] = int(N[0]) - 1
dp[0][1][0] = 1
for i in range(1, L):
	for j in range(4):
		b = i - 1
		now = int(N[i])
		if now == 0:
			dp[i][j][0] += dp[b][j][0]
		else:
			dp[i][j][1] += dp[b][j][0]
			dp[i][j + 1][1] += dp[b][j][0] * (now - 1)
			dp[i][j + 1][0] += dp[b][j][0]
		dp[i][j][1] += dp[b][j][1]
		dp[i][j + 1][1] += dp[b][j][1] * 9
	dp[i][1][1] += 9
print(dp[L - 1][K][0] + dp[L - 1][K][1])


N = input()
n = len(N)
k = int(input())
dp = [[[0] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][1] = 1
for i in range(1, n + 1):
	d = int(N[i - 1])
	for j in range(k + 1):
		if 0 <= j - 1:
			dp[i][j][0] += dp[i - 1][j - 1][0] * 9
		dp[i][j][0] += dp[i - 1][j][0]
		if d:
			if 0 <= j - 1:
				dp[i][j][1] += dp[i - 1][j - 1][1]
				dp[i][j][0] += dp[i - 1][j - 1][1] * (d - 1)
			dp[i][j][0] += dp[i - 1][j][1]
		else:
			dp[i][j][1] += dp[i - 1][j][1]
ans = dp[-1][-1][0] + dp[-1][-1][1]
print(ans)


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


N = input()
K = int(input())
L = len(N)
dp = [[[0] * 2 for _ in range(5)] for _ in range(110)]
dp[0][0][0] = 1
for i in range(L):
	S = int(N[i])
	for j in range(K + 1):
		for k in range(2):
			for d in range((9 if k else S) + 1):
				dp[i + 1][j + (d != 0)][k | (d < S)] += dp[i][j][k]
ans = dp[L][K][0] + dp[L][K][1]
print(ans)


n = input()
ln = len(n)
nn = [-1, -1, -1]
nnn = [0, 0, 0]
j = 0
for i in range(ln):
	if n[i] != '0':
		nn[j] = i
		nnn[j] = int(n[i])
		j += 1
		if j == 3:
			break
s = [9 * (ln - 1), 81 * (ln - 1) * (ln - 2) // 2, 729 * (ln - 1) * (ln - 2) * (ln - 3) // 6]
s[0] += nnn[0]
s[1] += (nnn[0] - 1) * 9 * (ln - 1) + (0 if nn[1] == -1 else nnn[1] + 9 * (ln - nn[1] - 1))
s[2] += (nnn[0] - 1) * 81 * (ln - 1) * (ln - 2) // 2
s[2] += (0 if nn[1] == -1 else (nnn[1] - 1) * 9 * (ln - nn[1] - 1) + 81 * (ln - nn[1] - 1) * (ln - nn[1] - 2) // 2) + (0 if nn[2] == -1 else nnn[2] + 9 * (ln - nn[2] - 1))
k = int(input())
print(s[k - 1])


def main():
	S = input()
	N = len(S)
	K = int(input())
	dp = [[[0] * (K + 2) 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(K + 1):
				lim = 9 if j else int(S[i])
				for d in range(lim + 1):
					dp[i + 1][j or d < lim][k + (d != 0)] += dp[i][j][k]
	print(dp[N][0][K] + dp[N][1][K])
main()


import math
n = int(input())
k = int(input())

def f(n, k):
	l = len(str(n))
	if l < k:
		ans = 0
	elif k == 1:
		ans = 9 * (l - 1)
		ans += n // 10 ** (l - 1)
	elif l == k:
		t = 10 ** (k - 1)
		ans = (n // t - 1) * f(t - 1, k - 1) + f(n % t, k - 1)
	else:
		ans = math.factorial(l - 1) // math.factorial(k) // math.factorial(l - 1 - k) * 9 ** k
		t = n % 10 ** (l - 1)
		ans += f(t, k - 1) + f(10 ** (l - 1) - 1, k - 1) * (n // 10 ** (l - 1) - 1)
	return ans
ans = f(n, k)
print(ans)


def solve(n, k):
	if n <= 9 and k == 1:
		return n
	elif n <= 9 and k >= 2:
		return 0
	elif k == 0:
		return 1
	else:
		m = n // 10
		r = n % 10
		return r * solve(m, k - 1) + (9 - r) * solve(m - 1, k - 1) + solve(m, k)
n = int(input())
k = int(input())
print(solve(n, k))


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


import sys
input = sys.stdin.readline

def solve(N, K, L):
	dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(L + 1)]
	dp[0][0][0] = 1
	for i in range(L):
		D = N[i]
		for j in range(2):
			d_max = 9 if j == 1 else D
			for k in range(K + 1):
				if k < K:
					for d in range(d_max + 1):
						dp[i + 1][int(j or d < D)][k + int(d > 0)] += dp[i][j][k]
				else:
					dp[i + 1][j][k] += dp[i][j][k]
	return dp[L][0][K] + dp[L][1][K]

def main():
	N = list(map(int, input().rstrip()))
	K = int(input())
	L = len(N)
	ans = solve(N, K, L)
	print(ans)

def __starting_point():
	main()
__starting_point()


n = input()
k = int(input())
dp = [[[0] * (k + 2) for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0][0] = 1
for (i, c) in enumerate(n):
	c = int(c)
	for f in range(2):
		for j in range(k + 1):
			for l in range(10 * f or c + 1):
				dp[i + 1][f or l < c][j + (l > 0)] += dp[i][f][j]
print(dp[-1][0][k] + dp[-1][1][k])


S = input()
N = len(S)
K = int(input())
dp = [[[0, 0] for i in range(4)] for j in range(N + 1)]
dp[0][0][0] = 1
for i in range(N):
	for j in range(4):
		for k in range(2):
			nd = int(S[i])
			for d in range(10):
				nj = j
				nk = k
				if d != 0:
					nj += 1
				if nj > K:
					continue
				if k == 0:
					if d > nd:
						continue
					if d < nd:
						nk = 1
				dp[i + 1][nj][nk] += dp[i][j][k]
print(sum(dp[N][K]))


n = int(input())
k = int(input())
l = len(str(n))
a = (l - 1) * (l - 2) * (l - 3) // 6 * 9 ** 3
if k == 2:
	a = (l - 1) * (l - 2) // 2 * 9 * 9
elif k == 1:
	a = (l - 1) * 9
sn = list(str(n))
c = 0
for i in range(l):
	p = sn[i]
	if p != '0':
		if k - c == 3:
			a += (l - i - 1) * (l - i - 2) // 2 * (int(p) - 1) * 9 * 9
		elif k - c == 2:
			a += (l - i - 1) * (int(p) - 1) * 9
			if not k == 2:
				a += (l - i - 1) * (l - i - 2) // 2 * 9 * 9
		elif k - c == 1:
			a += int(p)
			if not k == 1:
				a += (l - i - 1) * 9
		c += 1
		if c == k:
			break
print(a)


from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)
def f(n, k):
	if k < 0:
		return 0
	if n < 10:
		if k == 0:
			return 1
		elif k == 1:
			return n
		else:
			return 0
	(a, b) = divmod(n, 10)
	return f(a, k) + f(a, k - 1) * b + f(a - 1, k - 1) * (9 - b)
print(f(N, K))


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

def solve(n, k):
	if k == 0:
		return 1
	if n < 10:
		return n if k == 1 else 0
	if n < 100 and k == 3:
		return 0
	(m, d) = divmod(n, 10)
	ret = d * solve(m, k - 1)
	ret += (9 - d) * solve(m - 1, k - 1)
	ret += solve(m, k)
	return ret
print(solve(N, K))


N = input()
K = int(input())
l = len(N)
dp0 = [[1, 0, 0, 0] for _ in range(l + 1)]
dp1 = [[0, 0, 0, 0] for _ in range(l + 1)]
d = int(N) // 10 ** (l - 1)
(dp0[0][1], dp1[0][1]) = (d - 1, 1)
for (i, c) in enumerate(list(N)[1:]):
	d = int(c)
	for j in range(1, 4):
		dp0[i + 1][j] = dp0[i][j] + 9 * dp0[i][j - 1] + (dp1[i][j] if d > 0 else 0) + ((d - 1) * dp1[i][j - 1] if d > 1 else 0)
		dp1[i + 1][j] = dp1[i][j - 1] if d > 0 else dp1[i][j]
print(dp0[l - 1][K] + dp1[l - 1][K])


s = input()
m = int(input())
n = len(s)
if n == 1:
	print([0, int(s)][m == 1])
	exit()
dp = [[[0] * 2 for _ in range(m + 1)] for _ in range(n)]
dp[0][0][1] = 1
dp[0][1][1] = int(s[0]) - 1
dp[0][1][0] = 1
for i in range(1, n):
	for j in range(m + 1):
		if j:
			dp[i][j][1] += 9 * dp[i - 1][j - 1][1]
			if s[i] != '0':
				dp[i][j][0] += dp[i - 1][j - 1][0]
				dp[i][j][1] += (int(s[i]) - 1) * dp[i - 1][j - 1][0]
		if s[i] == '0':
			dp[i][j][0] += dp[i - 1][j][0]
		dp[i][j][1] += dp[i - 1][j][1]
		if s[i] != '0':
			dp[i][j][1] += dp[i - 1][j][0]
print(sum(dp[-1][-1]))


from functools import lru_cache
n = int(input())
k = int(input())

@lru_cache(None)
def f(n, k):
	assert n >= 0
	if n < 10:
		if k == 0:
			return 1
		elif k == 1:
			return n
		return 0
	(q, r) = divmod(n, 10)
	res = 0
	if k >= 1:
		res += f(q, k - 1) * r
		res += f(q - 1, k - 1) * (9 - r)
	res += f(q, k)
	return res
print(f(n, k))


a = int(input())
b = int(input())

def aez(n, k):
	s = str(n)
	ln = len(s) - 1
	n1 = int(s[0])
	if len(s) < k:
		return 0
	elif k == 1:
		return 9 * ln + n1
	elif k == 2:
		return 81 * ln * (ln - 1) // 2 + aez(int('9' * ln), 1) * (n1 - 1) + aez(int(s[1:]), 1)
	else:
		return 729 * ln * (ln - 1) * (ln - 2) // 6 + aez(int('9' * ln), 2) * (n1 - 1) + aez(int(s[1:]), 2)
print(aez(a, b))


def ans(n, k):
	s = str(n)
	a = len(s)
	b = int(s[0])
	if n == 0:
		return 0
	elif k == 1:
		return 9 * (a - 1) + b
	elif k == 2:
		return int(81 * (a - 1) * (a - 2) / 2) + 9 * (b - 1) * (a - 1) + ans(n - b * 10 ** (a - 1), 1)
	else:
		return int(729 * (a - 1) * (a - 2) * (a - 3) / 6) + int(81 * (b - 1) * (a - 1) * (a - 2) / 2) + ans(n - b * 10 ** (a - 1), 2)
N = int(input())
K = int(input())
print(ans(N, K))


strN = input().rstrip()
K = int(input())
maxD = len(strN)
dp = [[[0] * (K + 1) for j in range(2)] for i in range(maxD + 1)]
dp[0][0][0] = 1
for (d, Nd) in enumerate(strN):
	Nd = int(Nd)
	for isLtN in range(2):
		for numNot0 in range(K + 1):
			for x in range(10):
				if not isLtN and x > Nd:
					continue
				isLtN2 = isLtN or x < Nd
				numNot02 = numNot0 + (x != 0)
				if numNot02 > K:
					continue
				dp[d + 1][isLtN2][numNot02] += dp[d][isLtN][numNot0]
ans = dp[-1][0][K] + dp[-1][1][K]
print(ans)


N = input()
K = int(input())
m = len(N)
dp0 = [[0] * (m + 1) for _ in range(m + 1)]
dp1 = [[0] * (m + 1) for _ in range(m + 1)]
dp1[0][0] = 1
for i in range(1, m + 1):
	dp0[i][0] = 1
for i in range(m):
	for j in range(m):
		if N[i] == '0':
			dp0[i + 1][j + 1] = dp0[i][j] * 9 + dp0[i][j + 1]
			dp1[i + 1][j + 1] = dp1[i][j + 1]
		else:
			dp0[i + 1][j + 1] = dp0[i][j] * 9 + dp0[i][j + 1] + dp1[i][j] * (int(N[i]) - 1) + dp1[i][j + 1]
			dp1[i + 1][j + 1] = dp1[i][j]
if m < K:
	print(0)
else:
	print(dp0[-1][K] + dp1[-1][K])


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

def d_sum(digit, k):
	if k == 1:
		return 9 * digit
	elif k == 2:
		return 9 ** 2 * digit * (digit - 1) // 2
	else:
		return 9 ** 3 * digit * (digit - 1) * (digit - 2) // 6
s = str(n)
ans = 0
for (ind, i) in enumerate(s):
	if int(i) == 0:
		continue
	digit = len(s) - ind - 1
	ans += d_sum(digit, k)
	k -= 1
	if k == 0:
		ans += int(i)
		break
	ans += (int(i) - 1) * d_sum(digit, k)
print(ans)


N = input()
K = int(input())
ng = [0] * (K + 1)
ok = [0] * (K + 1)
ng[0] = 1
ng_count = 0
for n in N:
	n = int(n)
	if n == 0:
		for k in range(K, 0, -1):
			ok[k] = ok[k] + ok[k - 1] * 9
	else:
		ng_count += 1
		for k in range(K, 0, -1):
			ok[k] = ok[k] + ok[k - 1] * 9 + ng[k - 1] * (n - 1) + ng[k]
		ok[0] = 1
		for k in range(K + 1):
			ng[k] = int(k == ng_count)
print(ng[-1] + ok[-1])


s = input()
n = len(s)

def f(i, t, k):
	if k > n - i:
		return 0
	a = max(t, int(s[i]))
	i += 1
	if a == 0:
		z = f(i, t, k)
	elif k == 1:
		z = a + (n - i) * 9
	else:
		z = f(i, 9, k) + (a - 1) * f(i, 9, k - 1) + f(i, t, k - 1)
	return z
print(f(0, 0, int(input())))


n = list(map(int, list(input())))
k = int(input())
dp0 = [0] * 3
dp1 = [[0] * 3] * len(n)
dp0[0] = 1
dp1[0][0] = max(0, n[0] - 1)
for i in range(1, len(n)):
	dp1[i] = [dp1[i - 1][0] + dp0[0] * (n[i] != 0) + 9, dp1[i - 1][1] + dp0[1] * (n[i] != 0) + dp0[0] * max(0, n[i] - 1) + dp1[i - 1][0] * 9, dp1[i - 1][2] + dp0[2] * (n[i] != 0) + dp0[1] * max(0, n[i] - 1) + dp1[i - 1][1] * 9]
	if n[i] != 0:
		dp0 = [0] + dp0[:2]
print(dp0[k - 1] + dp1[-1][k - 1])


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


def calc(n, k):
	while n[0] == '0' and len(n) > 1:
		n = n[1:]
	digit = len(n)
	if digit < k:
		return 0
	comb = [1] * (k + 1)
	for i in range(1, k + 1):
		comb[i] = comb[i - 1] * (digit - i) // i
	if k == 1:
		return 9 * comb[1] + int(n[0])
	elif k == 2:
		return 9 ** 2 * comb[2] + (int(n[0]) - 1) * 9 * comb[1] + calc(n[1:], 1)
	elif k == 3:
		return 9 ** 3 * comb[3] + (int(n[0]) - 1) * 9 ** 2 * comb[2] + calc(n[1:], 2)
n = input()
k = int(input())
print(calc(n, k))


N = input()
K = int(input())
m = len(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(m + 1)]
dp[0][0][0] = 1
for i in range(1, m + 1):
	l = int(N[i - 1])
	for k in range(K + 1):
		if k - 1 >= 0:
			if l != 0:
				dp[i][0][k] = dp[i - 1][0][k - 1]
				dp[i][1][k] = dp[i - 1][1][k] + 9 * dp[i - 1][1][k - 1] + dp[i - 1][0][k] + (l - 1) * dp[i - 1][0][k - 1]
			else:
				dp[i][0][k] = dp[i - 1][0][k]
				dp[i][1][k] = dp[i - 1][1][k] + 9 * dp[i - 1][1][k - 1]
		else:
			dp[i][0][k] = 0
			dp[i][1][k] = 1
print(dp[m][0][K] + dp[m][1][K])


(N, K) = map(int, open(0).read().split())
X = str(N + 1)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(X) + 1)]
dp[0][0][0] = 1
for i in range(len(X)):
	D = int(X[i])
	for j in range(2):
		for k in range(K + 1):
			for d in range((9 if j == 1 else D) + 1):
				if k + int(d != 0) <= K:
					dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k]
print(dp[-1][-1][-1])


digits = [int(c) for c in input()]
n = len(digits)
m = int(input())
dp = [[[0 for _ in range(2)] for _ in range(m + 2)] for _ in range(n + 1)]
dp[0][0][0] = 1
for (i, digit) in enumerate(digits):
	for j in range(m + 1):
		for k in range(2):
			for d in range(10 if k else digit + 1):
				dp[i + 1][j + (d > 0)][k or d < digit] += dp[i][j][k]
print(sum(dp[n][m]))


N = input()
k = int(input())
length = len(N)
dp = [[[0 for _ in range(k + 1)] for _ in range(2)] for _ in range(length + 1)]
dp[0][0][0] = 1
for i in range(length):
	max_digit = int(N[i])
	for k_num in range(k + 1):
		for flag_less in range(2):
			range_digit = 9 if flag_less else max_digit
			for d in range(range_digit + 1):
				flag_less_next = 0
				if flag_less == 1 or d < max_digit:
					flag_less_next = 1
				k_num_next = k_num
				if d != 0:
					k_num_next = k_num + 1
					if k_num_next > k:
						continue
				dp[i + 1][flag_less_next][k_num_next] += dp[i][flag_less][k_num]
print(dp[length][0][k] + dp[length][1][k])


from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)
def F(N, K):
	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))


N = int(input())
K = int(input())
n = list(map(int, str(N)))
dp = [[[0] * 5 for __ in range(2)] for _ in range(101)]
l = len(n)
dp[0][0][0] = 1
for i in range(l):
	for smaller in range(2):
		for j in range(4):
			for x in range((9 if smaller else n[i]) + 1):
				dp[i + 1][smaller or x < n[i]][j + 1 if x != 0 else j] += dp[i][smaller][j]
print(dp[l][0][K] + dp[l][1][K])


N = list(map(int, list(input())))
L = len(N)
K = int(input())
dp = [[[0] * (K + 1) for j in range(2)] for i in range(L + 1)]
dp[0][0][0] = 1
for i in range(L):
	ni = N[i]
	if ni == 0:
		for j in range(K):
			dp[i + 1][1][j + 1] += dp[i][1][j] * 9
		for j in range(K + 1):
			dp[i + 1][0][j] += dp[i][0][j]
	else:
		for j in range(K + 1):
			dp[i + 1][1][j] += dp[i][0][j]
		for j in range(K):
			dp[i + 1][1][j + 1] += dp[i][0][j] * (ni - 1) + dp[i][1][j] * 9
			dp[i + 1][0][j + 1] += dp[i][0][j]
	for j in range(K + 1):
		dp[i + 1][1][j] += dp[i][1][j]
print(dp[L][0][K] + dp[L][1][K])


n = input()
K = int(input())
m = len(n)
DP = [[[0] * (K + 2) for _ in range(2)] for _ in range(m + 1)]
DP[0][0][0] = 1
for i in range(1, m + 1):
	for flag in range(2):
		num = 9 if flag else int(n[i - 1])
		for j in range(K + 1):
			for k in range(num + 1):
				if k == 0:
					DP[i][flag or k < num][j] += DP[i - 1][flag][j]
				else:
					DP[i][flag or k < num][j] += DP[i - 1][flag][j - 1]
print(DP[m][0][K] + DP[m][1][K])


n = int(input())
m = len(str(n))
k = int(input())
N = [int(i) for i in str(n)]
dp0 = [[0] * (k + 1) for _ in range(m + 1)]
dp1 = [[0] * (k + 1) for _ in range(m + 1)]
dp1[0][0] = 1
for (i, e) in enumerate(str(n)):
	e = int(e)
	for j in range(k + 1):
		dp1[i + 1][j] += dp1[i][j] * (e == 0)
		dp0[i + 1][j] += dp0[i][j] + dp1[i][j] * (e > 0)
		if j < k:
			dp1[i + 1][j + 1] += dp1[i][j] * (e > 0)
			dp0[i + 1][j + 1] += dp0[i][j] * 9 + dp1[i][j] * max(0, e - 1)
print(dp1[m][k] + dp0[m][k])


import numpy as np
N = input()
K = int(input())
n = len(N)
dp0 = np.zeros((n, K + 1), np.int64)
dp1 = np.zeros((n, K + 1), np.int64)
dp0[0, 0] = 1
dp0[0, 1] = int(N[0]) - 1
dp1[0, 1] = 1
for (i, d) in enumerate(N[1:]):
	dp0[i + 1] += dp0[i]
	dp0[i + 1, 1:] += dp0[i, :-1] * 9
	if int(d) == 0:
		dp1[i + 1] = dp1[i]
	elif int(d) == 1:
		dp0[i + 1] += dp1[i]
		dp1[i + 1, 1:] = dp1[i, :-1]
	elif int(d) >= 2:
		dp0[i + 1] += dp1[i]
		dp0[i + 1, 1:] += dp1[i, :-1] * (int(d) - 1)
		dp1[i + 1, 1:] = dp1[i, :-1]
print(dp0[-1, K] + dp1[-1, K])


N = list(input())
K = int(input())
OK = [[0 for k in range(5)] for i in range(len(N))]
OK[0][0] = 1
OK[0][1] = int(N[0]) - 1
D = 1
for i in range(1, len(N)):
	OK[i][0] = OK[i - 1][0]
	OK[i][1] += OK[i - 1][0] * 9 + OK[i - 1][1]
	OK[i][2] += OK[i - 1][1] * 9 + OK[i - 1][2]
	OK[i][3] += OK[i - 1][2] * 9 + OK[i - 1][3]
	if D <= K and int(N[i]) != 0:
		OK[i][D] += 1
		OK[i][D + 1] += int(N[i]) - 1
		D += 1
if D == K:
	print(OK[-1][K] + 1)
else:
	print(OK[-1][K])


from itertools import combinations
N = list(map(int, input()))
K = int(input())
nlen = len(N)
ans = 0
if K <= nlen:
	cmb = [9] * nlen
	for n in N:
		if n != 0:
			cmb[0] = n - 1
			for x in combinations(cmb, K):
				y = x[0]
				for z in x[1:]:
					y *= z
				ans += y
			if K == 1:
				ans += 1
				break
			K -= 1
		cmb.pop()
print(ans)


N = input()
K = int(input())
nSize = len(N)
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(nSize + 1)]
dp[0][0][0] = 1
for i in range(nSize):
	for j in range(K + 1):
		for k in range(2):
			for l in range(10):
				ni = i + 1
				nj = j
				nk = k
				if l != 0:
					nj += 1
				if nj > K:
					continue
				if k == 0:
					if l > int(N[i]):
						continue
					if l < int(N[i]):
						nk = 1
				dp[ni][nj][nk] += dp[i][j][k]
print(dp[nSize][K][0] + dp[nSize][K][1])


N = input()
K = int(input())
a = [0] * (K + 1)
b = [0] * (K + 1)
t = int(N[0])
a = 1
b[0] = 1
b[1] = t - 1
for c in N[1:]:
	t = int(c)
	for i in range(K - 1, -1, -1):
		b[i + 1] += b[i] * 9
	if t != 0:
		if t != 1 and a + 1 <= K:
			b[a + 1] += t - 1
		if a <= K:
			b[a] += 1
		a += 1
if a == K:
	print(b[K] + 1)
else:
	print(b[K])


def DP(n, k):
	if k == 0:
		return 1
	elif n < 10 and k == 1:
		return n
	elif n < 10 and k != 0:
		return 0
	else:
		(q, r) = (n // 10, n % 10)
		return DP(q, k) + r * DP(q, k - 1) + (9 - r) * DP(q - 1, k - 1)
n = int(input())
k = int(input())
print(DP(n, k))


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

def f(dig, under, num):
	if num > l - dig:
		return 0
	if num == 0:
		return 1
	if dig == l - 1:
		if under:
			return int(n[dig])
		else:
			return 9
	if under:
		if n[dig] == '0':
			res = f(dig + 1, True, num)
			return res
		else:
			res = f(dig + 1, False, num)
			if int(n[dig]) > 1:
				res += (int(n[dig]) - 1) * f(dig + 1, False, num - 1)
			res += f(dig + 1, True, num - 1)
			return res
	else:
		res = f(dig + 1, False, num)
		res += 9 * f(dig + 1, False, num - 1)
		return res
ans = f(0, True, k)
print(ans)


N = input()
K = int(input())
dp = [[[0 for _ in range(K + 2)] for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	for smaller in range(2):
		for k in range(K + 1):
			for x in range(10 if smaller == 1 else int(N[i]) + 1):
				dp[i + 1][smaller == 1 or x < int(N[i])][k + 1 if x != 0 else k] += dp[i][smaller][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])


N = input()
K = int(input())
dp = [[[0] * 2 for i in range(len(N) + 1)] for _ in range(len(N) + 1)]
if len(N) < K:
	print(0)
	exit()
dp[0][0][0] = 1
for i in range(len(N)):
	for j in range(len(N)):
		if int(N[i]) != 0:
			dp[i + 1][j + 1][1] += dp[i][j][1] * 9 + dp[i][j][0] * (int(N[i]) - 1)
			dp[i + 1][j][1] += dp[i][j][1] + dp[i][j][0]
			dp[i + 1][j + 1][0] += dp[i][j][0]
		if int(N[i]) == 0:
			dp[i + 1][j + 1][1] += dp[i][j][1] * 9
			dp[i + 1][j][1] += dp[i][j][1]
			dp[i + 1][j][0] += dp[i][j][0]
print(dp[len(N)][K][0] + dp[len(N)][K][1])


from functools import lru_cache
N = input()
K = int(input())

@lru_cache(maxsize=None)
def search(d, cnt, isLess):
	if d == len(N):
		return cnt == K
	a = int(N[d])
	if isLess:
		return search(d + 1, cnt + 1, isLess) * 9 + search(d + 1, cnt, isLess)
	ret = 0
	for i in range(a + 1):
		ret += search(d + 1, cnt + (i != 0), i < a)
	return ret
print(search(0, 0, False))


n = input()
k = int(input())
l = len(n)
dp = [[[0] * 2 for j in range(k + 1)] for i in range(l + 1)]
dp[0][0][0] = 1
for i in range(l):
	ni = int(n[i])
	for j in range(k + 1):
		for st in range(2):
			for x in range(10):
				i_ = i + 1
				j_ = j
				st_ = st
				if x != 0:
					j_ += 1
				if j_ > k:
					continue
				if st_ == 0 and x > ni:
					continue
				if st_ == 0 and x < ni:
					st_ = 1
				dp[i_][j_][st_] += dp[i][j][st]
print(sum(dp[l][k]))


def comb(n, k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n * (n - 1) / 2
n = input()
k = int(input())
ans = 0
for dgt in range(1, len(n)):
	if dgt < len(n):
		ans += 9 ** k * comb(dgt - 1, k - 1)
dgt = len(n)
cnt = 0
for i in range(len(n)):
	if n[i] != '0' and cnt < k:
		cnt += 1
		ans += (int(n[i]) - 1) * 9 ** (k - cnt) * comb(dgt - i - 1, k - cnt)
		if i:
			ans += 9 ** (k - cnt + 1) * comb(dgt - i - 1, k - cnt + 1)
if cnt == k:
	ans += 1
print(int(ans))


from functools import lru_cache
n = int(input())
k = int(input())

@lru_cache(None)
def cal(n, k):
	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 += cal(q, k - 1) * r
		ret += cal(q - 1, k - 1) * (9 - r)
	ret += cal(q, k)
	return ret
print(cal(n, k))


import numpy as np
s = input()
n = int(s)
k = int(input())
m = len(s)
dp = np.zeros((m + 1, 2, k + 2), dtype=np.int64)
dp[0][1][0] = 1
for cs in range(m):
	cn = int(s[cs])
	for ck in range(k + 2):
		if ck == k + 1:
			nk = ck
		else:
			nk = ck + 1
		dp[cs + 1][0][nk] += 9 * dp[cs][0][ck]
		dp[cs + 1][0][ck] += dp[cs][0][ck]
		if cn == 0:
			dp[cs + 1][1][ck] += dp[cs][1][ck]
		else:
			dp[cs + 1][1][nk] += dp[cs][1][ck]
			dp[cs + 1][0][nk] += (cn - 1) * dp[cs][1][ck]
			dp[cs + 1][0][ck] += dp[cs][1][ck]
print(dp[m][0][k] + dp[m][1][k])


N = input()
cnt = int(input())
L = len(N)
dp = [[[0] * (cnt + 1) for j in range(2)] for i in range(L + 1)]
dp[0][0][0] = 1
for i in range(L):
	for j in range(2):
		for k in range(cnt + 1):
			D = int(N[i])
			for d in range(10 if j else D + 1):
				K = k + int(d != 0)
				if K > cnt:
					continue
				dp[i + 1][int(j or d < D)][K] += dp[i][j][k]
print(dp[-1][0][-1] + dp[-1][1][-1])


import sys
from collections import deque

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

def per(n, r, mod=10 ** 9 + 7):
	per = 1
	for i in range(r):
		per = per * (n - i) % mod
	return per

def com(n, r, mod=10 ** 9 + 7):
	bunshi = per(n, r, mod)
	bunbo = 1
	for i in range(1, r + 1):
		bunbo = bunbo * i % mod
	return bunshi * pow(bunbo, -1, mod) % mod

def main():
	n = list(map(int, list(input())))
	k = int(input())
	keta = len(n)
	count = [n[0] - 1 + com(keta - 1, 1) * 9, (n[0] - 1) * com(keta - 1, 1) * 9 + com(keta - 1, 2) * 9 ** 2, (n[0] - 1) * com(keta - 1, 2) * 9 ** 2 + com(keta - 1, 3) * 9 ** 3]
	nonzero = 1
	for i in range(1, keta):
		if n[i] != 0:
			nonzero += 1
			if nonzero == 2:
				count[1] += n[i] - 1 + com(keta - i - 1, 1) * 9
				count[2] += (keta - i - 1) * (n[i] - 1) * 9 + com(keta - i - 1, 2) * 9 ** 2
			elif nonzero == 3:
				count[2] += n[i] - 1 + com(keta - i - 1, 1) * 9
	print(count[k - 1] + (nonzero >= k))

def __starting_point():
	main()
__starting_point()


n = input()
k = int(input())
ln = len(n) + 1
dp = [[[0] * ln for _ in range(2)] for i in range(ln)]
dp[0][0][0] = 1
for i in range(len(n)):
	for smaller in range(2):
		x = int(n[i])
		t = 9 if smaller else x
		for j in range(t + 1):
			for knum in range(ln - 1):
				if j == 0:
					dp[i + 1][int(smaller or j < x)][knum] += dp[i][smaller][knum]
				else:
					dp[i + 1][int(smaller or j < x)][knum + 1] += dp[i][smaller][knum]
try:
	print(dp[-1][0][k] + dp[-1][1][k])
except:
	print(0)


from functools import lru_cache

@lru_cache(None)
def solve(n, k):
	if n <= 9:
		if k == 0:
			return 1
		if k == 1:
			return n
		return 0
	m = n // 10
	r = n % 10
	return r * solve(m, k - 1) + (9 - r) * solve(m - 1, k - 1) + solve(m, k)
N = int(input())
K = int(input())
print(solve(N, K))


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

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

def k2(n):
	n_l = len(str(n))
	if n_l <= 1:
		return 0
	n_0 = int(str(n)[0])
	return 81 * ((n_l - 1) * (n_l - 2) // 2) + (n_0 - 1) * 9 * (n_l - 1) + k1(n % 10 ** (n_l - 1))

def k3(n):
	n_l = len(str(n))
	if n_l <= 2:
		return 0
	n_0 = int(str(n)[0])
	return 729 * ((n_l - 1) * (n_l - 2) * (n_l - 3) // 6) + (n_0 - 1) * 81 * ((n_l - 1) * (n_l - 2) // 2) + k2(n % 10 ** (n_l - 1))
if k == 1:
	print(k1(n))
if k == 2:
	print(k2(n))
if k == 3:
	print(k3(n))


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

def k2(l, n):
	ans = 81 * (l - 1) * (l - 2) // 2
	ans += (int(n[0]) - 1) * 9 * (l - 1)
	for (i, s) in enumerate(n[1:]):
		if s == '0':
			continue
		ans += int(s)
		ans += max(l - i - 2, 0) * 9
		break
	return ans
if k == 1:
	ans = (l - 1) * 9 + int(n[0])
elif k == 2:
	if l == 1:
		print(0)
		return
	ans = k2(l, n)
else:
	if l < 3:
		print(0)
		return
	ans = 9 ** 3 * (l - 1) * (l - 2) * (l - 3) // 6
	ans += (int(n[0]) - 1) * 81 * (l - 1) * (l - 2) // 2
	n = n[1:]
	n = str(int(n))
	ans += k2(len(n), n)
print(ans)


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf, comb
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)

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

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def MAP1():
	return map(lambda x: int(x) - 1, input().split())

def LIST():
	return list(MAP())

def LIST1():
	return list(MAP1())
n = INT()
k = INT()

@lru_cache(None)
def F(n, k):
	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))


def f(N, K):
	(M, R) = (N // 10, N % 10)
	if K == 0:
		return 1
	elif M == 0 and K == 1:
		return R
	elif M == 0 and K != 1:
		return 0
	else:
		return R * f(M, K - 1) + (9 - R) * f(M - 1, K - 1) + f(M, K)
N = int(input())
K = int(input())
print(f(N, K))


N = int(input())
K = int(input())
from functools import lru_cache

@lru_cache(None)
def f(n, K):
	if n <= 10:
		if K == 0:
			return 1
		if K == 1:
			return n
		return 0
	div_n = n // 10
	mod_n = n % 10
	ans = 0
	ans += f(div_n, K - 1) * mod_n
	ans += f(div_n - 1, K - 1) * (9 - mod_n)
	ans += f(div_n, K)
	return ans
print(f(N, K))


s = input() * 2
n = len(s) // 2
X = [(0, 0)] * 4
for j in range(n + 1):
	for k in range(3, -1, -1):
		a = int(s[n - j])
		X[k] = (X[k][0] + 9 * X[k - 1][0] if k else 1, (X[k][0] + (a - 1) * X[k - 1][0] + X[k - 1][1] if k else 1) if a else X[k][1])
print(X[int(input())][1])


x = int(input())
X = [int(i) for i in str(x)]
y = int(input())
dp = [[[0] * 2 for i in range(4)] for j in range(len(str(x)) + 1)]
dp[0][0][0] = 1
for i in range(len(str(x))):
	for j in range(4):
		for m in range(2):
			for n in range(10):
				nj = j + 1 if n != 0 else j
				if nj == 4:
					continue
				nm = m
				if X[i] > n and m == 0:
					nm = 1
				if X[i] < n and m == 0:
					continue
				dp[i + 1][nj][nm] += dp[i][j][m]
print(dp[len(X)][y][0] + dp[len(X)][y][1])


import sys
sys.setrecursionlimit(303)

def doit(n, k, m):
	if len(n) == 0 or k < 0:
		return k == 0
	if (n, k) not in m:
		d = int(n[0])
		m[n, k] = sum((doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k, m) for i in range(d + 1)))
	return m[n, k]
print(doit(input(), int(input()), {}))


def comb(n, k):
	(nu, de) = (1, 1)
	for i in range(k):
		de *= n - i
		nu *= i + 1
	return de // nu

def ans(N, K):
	if K == 0:
		return 1
	N = str(int(N))
	if len(N) < K or int(N) == 0:
		return 0
	ret = sum([9 ** K * comb(max(dig - 1, 1), K - 1) for dig in range(K, len(N))])
	ret += (int(N[0]) - 1) * 9 ** (K - 1) * comb(len(N) - 1, K - 1)
	return ret + ans(N[1:], K - 1)
N = input()
K = int(input())
print(ans(N, K))


n = '0' + input()
k = int(input())
dp = [[[0] * 5, [0] * 5] for _ in range(len(n))]
dp[0][1][0] = 1
for i in range(1, len(n)):
	x = int(n[i])
	for j in range(4):
		if dp[i - 1][1][j]:
			dp[i][1][j + (x != 0)] = 1
			if x > 1:
				dp[i][0][j + 1] += x - 1
				dp[i][0][j] += 1
			elif x == 1:
				dp[i][0][j] += 1
		if dp[i - 1][0][j]:
			dp[i][0][j] += dp[i - 1][0][j]
			dp[i][0][j + 1] += dp[i - 1][0][j] * 9
	dp[i][0][0] = 1
print(dp[-1][0][k] + dp[-1][1][k])


from sys import stdin
from functools import lru_cache

@lru_cache(None)
def solver(N, K):
	if N < 10:
		if K == 0:
			return 1
		if K == 1:
			return N
		return 0
	(m, r) = divmod(N, 10)
	ans = 0
	if K >= 1:
		ans += solver(m, K - 1) * r
		ans += solver(m - 1, K - 1) * (9 - r)
	ans += solver(m, K)
	return ans
n = int(input())
k = int(input())
print(solver(n, k))


def resolve():
	S = input()
	K = int(input())
	N = len(S)
	dp = [[[0] * 2 for _ in range(4)] for _ in range(N + 1)]
	dp[0][0][0] = 1
	for i in range(N):
		for j in range(4):
			for smaller in range(2):
				now = int(S[i])
				for d in range(10):
					ni = i + 1
					nj = j
					n_smaller = smaller
					if d != 0:
						nj += 1
					if nj > K:
						continue
					if smaller == 0:
						if d > now:
							continue
						if d < now:
							n_smaller = 1
					dp[ni][nj][n_smaller] += dp[i][j][smaller]
	ans = dp[N][K][0] + dp[N][K][1]
	print(ans)

def __starting_point():
	resolve()
__starting_point()


N = input()
K = int(input())
keta = len(N)
dp = [[[0] * (keta + 1) for _ in range(K + 1)] for _ in range(2)]
for i in range(keta - 1):
	dp[0][0][i] = 1
dp[0][1][0] = int(N[0]) - 1
dp[1][1][0] = 1
for i in range(1, K + 1):
	for j in range(i - 1, keta):
		x = int(N[j])
		dp[0][i][j] += dp[0][i][j - 1] + dp[0][i - 1][j - 1] * 9
		dp[0][i][j] += dp[1][i][j - 1] if N[j] != '0' else 0
		dp[0][i][j] += dp[1][i - 1][j - 1] * max(int(N[j]) - 1, 0)
		dp[1][i][j] += dp[1][i][j - 1] * int(N[j] == '0')
		dp[1][i][j] += dp[1][i - 1][j - 1] * int(N[j] != '0')
print(dp[0][-1][-2] + dp[1][-1][-2])


import sys
read = sys.stdin.read

def main():
	(N, K) = map(int, read().split())
	dp1 = [0] * (K + 1)
	dp2 = [0] * (K + 1)
	dp1[0] = 1
	for x in map(int, str(N)):
		for j in range(K, -1, -1):
			if j > 0:
				dp2[j] += dp2[j - 1] * 9
				if x != 0:
					dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
					dp1[j] = dp1[j - 1]
			else:
				dp1[j] = 0
				dp2[j] = 1
	print(dp1[K] + dp2[K])
	return

def __starting_point():
	main()
__starting_point()


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

def pow(a, n):
	ans = 1
	while n > 1:
		if bin(a & 1) == bin(1):
			ans = ans * a
		a = a * a
		n = n >> 1
	return ans

def com(N, k):
	if k < 0 or k > N:
		return 0
	if k == 1:
		return N
	elif k == 2:
		return N * (N - 1) // 2
	else:
		return N * (N - 1) * (N - 2) // 6
S = len(str(N))
N = str(N)

def helper(i, k, smaller):
	if i == S:
		if k == 0:
			return 1
		else:
			return 0
	if k == 0:
		return 1
	if smaller:
		return com(S - i, k) * 9 ** k
	elif N[i] == '0':
		return helper(i + 1, k, False)
	else:
		zero = helper(i + 1, k, True)
		a = helper(i + 1, k - 1, True) * (int(N[i]) - 1)
		b = helper(i + 1, k - 1, False)
		return zero + a + b
print(helper(0, K, False))


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(int(input()), int(input())))


N = input()
K = int(input())
if len(N) < K:
	print(0)
	return
ans = [1, int(N[-1]), 0, 0]
nine = [1, 9, 81, 729]

def combination(N, K):
	if N < K:
		return 0
	elif K == 0:
		return 1
	elif K == 1:
		return N
	elif K == 2:
		return N * (N - 1) // 2
	else:
		return N * (N - 1) * (N - 2) // 6
for k in range(1, len(N)):
	if int(N[-k - 1]) > 0:
		a = [1, 0, 0, 0]
		for j in range(1, K + 1):
			a[j] += nine[j] * combination(k, j)
			a[j] += (int(N[-k - 1]) - 1) * combination(k, j - 1) * nine[j - 1] + ans[j - 1]
		ans = a
print(ans[K])


import bisect, collections, copy, functools, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	N = I()
	K = I()

	@functools.lru_cache
	def f(N, K):
		if N == K == 0:
			ret = 1
		elif N > 0 and K >= 0:
			ret = f(N // 10, K) + N % 10 * f(N // 10, K - 1) + (9 - N % 10) * f(N // 10 - 1, K - 1)
		else:
			ret = 0
		return ret
	ans = f(N, K)
	print(ans)

def __starting_point():
	resolve()
__starting_point()


import math
N = list(input())
K = int(input())
ans = 0
not_zero = 0

def cmb(n, r):
	if n - r >= 1 and n >= 1 and (r >= 1):
		return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
	elif n == r or n == r:
		return 1
	elif r == 0:
		return 1
	else:
		return 0
for i in range(len(N)):
	if N[i] != '0':
		ans += cmb(len(N[i + 1:]), K - not_zero) * 9 ** (K - not_zero)
		ans += cmb(len(N[i + 1:]), K - not_zero - 1) * (int(N[i]) - 1) * 9 ** (K - not_zero - 1)
		not_zero += 1
		if not_zero == K:
			ans += 1
			break
print(ans)


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

def f(n, k):
	l = len(n)
	if l < k:
		return 0
	if n[0] == '0':
		return f(n[1:], k)
	if k == 1:
		ans = (l - 1) * 9 + int(n[0])
	if k == 2:
		ans = (l - 1) * (l - 2) // 2 * 81 + (int(n[0]) - 1) * ((l - 1) * 9)
		ans += f(n[1:], k - 1)
	if k == 3:
		ans = (int(n[0]) - 1) * ((l - 1) * (l - 2) // 2) * 81 + (l - 1) * (l - 2) * (l - 3) // 6 * 9 * 9 * 9
		ans += f(n[1:], k - 1)
	return ans
print(f(n, k))


N = input()
K = int(input())
DP = [[[0 for i in range(K + 1)] for i in range(2)] for i in range(len(N))]
for d in range(int(N[0]) + 1):
	DP[0][d < int(N[0])][d != 0] += 1
for i in range(len(N) - 1):
	for j in range(2):
		for k in range(K + 1):
			for d in range(10 if j else int(N[i + 1]) + 1):
				if k + (d != 0) <= K:
					DP[i + 1][j | (d < int(N[i + 1]))][k + (d != 0)] += DP[i][j][k]
print(DP[len(N) - 1][0][K] + DP[len(N) - 1][1][K])


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


n = input()
num_list = list(map(int, n))
k = int(input())
dp = [[[0] * (k + 2) for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0][0] = 1
for (i, v) in enumerate(num_list):
	for j in range(k + 1):
		dp[i + 1][1][j] += dp[i][1][j]
		dp[i + 1][1][j + 1] += dp[i][1][j] * 9
		if v == 0:
			dp[i + 1][0][j] += dp[i][0][j]
		else:
			dp[i + 1][1][j + 1] += dp[i][0][j] * (v - 1)
			dp[i + 1][1][j] += dp[i][0][j]
			dp[i + 1][0][j + 1] += dp[i][0][j]
print(dp[len(n)][0][k] + dp[len(n)][1][k])


N = input()
L = len(N)
K = int(input())
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(L + 1)]
dp[0][0][0] = 1
for (i, c) in enumerate(N):
	c = int(c)
	for k in range(K + 1):
		for less in range(2):
			for d in range(10):
				nk = k + (d > 0)
				if nk > K:
					continue
				if less == 0 and d > c:
					continue
				nxless = not (less == 0 and d == c)
				dp[i + 1][nk][nxless] += dp[i][k][less]
print(sum(dp[-1][-1]))


import sys
sys.setrecursionlimit(10000)
n = input()
k = int(input())
m = {}

def doit(n, k):
	if len(n) == 0:
		return k == 0
	d = int(n[0])
	if (n, k) not in m:
		ret = 0
		for i in range(d + 1):
			if i == d:
				ret += doit(n[1:], k - 1 if i > 0 else k)
			else:
				ret += doit('9' * (len(n) - 1), k - 1 if i > 0 else k)
		m[n, k] = ret
	return m[n, k]
print(doit(n, k))


from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)
n = int(input())
k = int(input())

@lru_cache(maxsize=None)
def f(n, k):
	if k == 0:
		return 1
	if len(str(n)) == 1:
		if k >= 2:
			return 0
		if k == 1:
			return n
	r = n % 10
	m = (n - r) // 10
	return r * f(m, k - 1) + (9 - r) * f(m - 1, k - 1) + f(m, k)
print(f(n, k))


def main():
	N = input()
	L = len(N)
	K = int(input())
	dp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
	dpp = [[0 for _ in range(L + 1)] for _ in range(K + 1)]
	dpp[0][0] = 1
	for i in range(1, L + 1):
		n = int(N[i - 1])
		for k in range(K + 1):
			kk = k + (1 if n > 0 else 0)
			if kk <= K:
				dpp[kk][i] = dpp[k][i - 1]
			if n > 0:
				dp[k][i] += dpp[k][i - 1]
				if k + 1 <= K:
					dp[k + 1][i] += (n - 1) * dpp[k][i - 1]
			dp[k][i] += dp[k][i - 1]
			if k + 1 <= K:
				dp[k + 1][i] += 9 * dp[k][i - 1]
	print(dp[K][L] + dpp[K][L])

def __starting_point():
	main()
__starting_point()


n = int(input())
k = int(input())
s = str(n)
l = len(s)
dp0 = [[0] * (k + 1) for _ in range(l + 1)]
dp1 = [[0] * (k + 1) for _ in range(l + 1)]
dp1[0][0] = 1
for i in range(l):
	for j in range(k + 1):
		dp1[i + 1][j] += dp1[i][j] * (int(s[i]) == 0)
		dp0[i + 1][j] += dp0[i][j] + dp1[i][j] * (int(s[i]) > 0)
		if j < k:
			dp1[i + 1][j + 1] += dp1[i][j] * (int(s[i]) > 0)
			dp0[i + 1][j + 1] += dp0[i][j] * 9 + dp1[i][j] * max(0, int(s[i]) - 1)
print(dp1[l][k] + dp0[l][k])


def run():
	N = list(map(int, list(input())))
	K = int(input())
	Nlen = len(N)
	dp = [[[0] * (K + 2) for _ in range(2)] for n in range(Nlen + 1)]
	dp[0][0][0] = 1
	for nlen in range(Nlen):
		dN = N[nlen]
		for d in range(10):
			for j in range(2):
				for k in range(K + 2):
					flagj = j or d < dN
					if flagj == 0 and d > dN:
						continue
					flagk = min(K + 1, k + (d != 0))
					dp[nlen + 1][flagj][flagk] += dp[nlen][j][k]
	print(dp[-1][0][K] + dp[-1][1][K])
run()


from functools import lru_cache
N = int(input())
K = int(input())

@lru_cache(None)
def rec(n, k):
	if k == 0:
		return 1
	if n < 10:
		if k == 1:
			return n
		else:
			return 0
	(m, d) = divmod(n, 10)
	ret = 0
	ret += d * rec(m, k - 1)
	ret += (9 - d) * rec(m - 1, k - 1)
	ret += rec(m, k)
	return ret
print(rec(N, K))


from itertools import product
n = input()
k = int(input())
dp = [[[0] * (k + 2) for _ in range(2)] for _ in range(len(n) + 1)]
dp[0][0][0] = 1
for (i, j, l) in product(range(len(n)), range(2), range(k + 1)):
	for x in range(10):
		if j == 0 and x > int(n[i]):
			continue
		dp[i + 1][0 if j == 0 and x == int(n[i]) else 1][l + 1 if x != 0 else l] += dp[i][j][l]
print(dp[len(n)][0][k] + dp[len(n)][1][k])


x = input()
L = len(x)
N = []
for l in range(L):
	N.append(int(x[l]))
N.insert(0, 0)
K = int(input())
dp0 = []
dp1 = []
for l in range(L + 1):
	dp0.append([0] * (K + 1))
	dp1.append([0] * (K + 1))
dp1[0][0] = 1
for l in range(1, L + 1):
	dp0[l][0] = 1
for i in range(1, L + 1):
	for j in range(1, K + 1):
		if N[i] == 0:
			dp0[i][j] = dp0[i - 1][j] + 9 * dp0[i - 1][j - 1]
			dp1[i][j] = dp1[i - 1][j]
		else:
			dp0[i][j] = dp0[i - 1][j] + 9 * dp0[i - 1][j - 1] + (N[i] - 1) * dp1[i - 1][j - 1] + dp1[i - 1][j]
			dp1[i][j] = dp1[i - 1][j - 1]
print(dp0[L][K] + dp1[L][K])


N = [0] + list(map(int, input()))
K = int(input())
n = len(N)
DP = [[[0] * 5 for _ in range(2)] for _ in range(n)]
DP[0][0][0] = 1
for i in range(1, n):
	for k in range(4):
		if N[i] != 0:
			DP[i][0][k + 1] += DP[i - 1][0][k]
			DP[i][1][k] += DP[i - 1][0][k]
			DP[i][1][k + 1] += DP[i - 1][0][k] * (N[i] - 1)
		else:
			DP[i][0][k] += DP[i - 1][0][k]
		DP[i][1][k] += DP[i - 1][1][k]
		DP[i][1][k + 1] += DP[i - 1][1][k] * 9
print(DP[n - 1][1][K] + DP[n - 1][0][K])


import math
n = input()
k = int(input())
t = 0

def com(a, b):
	if b > a:
		return 0
	else:
		return math.factorial(a) // (math.factorial(b) * math.factorial(a - b))

def su(n, k, i, s):
	if s == 0:
		return 1
	if len(n) - i < s:
		return 0
	if n[i] == '0':
		return su(n, k, i + 1, s)
	else:
		return 9 ** s * com(len(n) - i - 1, s) + (int(n[i]) - 1) * 9 ** (s - 1) * com(len(n) - i - 1, s - 1) + su(n, k, i + 1, s - 1)
print(su(n, k, 0, k))


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

def K1(num):
	return int(num[0]) + (len(num) - 1) * 9

def K2(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K1(tmp)
	out1 = (int(num[0]) - 1) * (L - 1) * 9
	out2 = (L - 1) * (L - 2) // 2 * 9 * 9
	return out + out1 + out2

def K3(num):
	L = len(num)
	tmp = str(int(num[1:]))
	out = K2(tmp)
	out1 = (int(num[0]) - 1) * ((L - 1) * (L - 2) // 2) * 9 * 9
	out2 = (L - 1) * (L - 2) * (L - 3) // 6 * 9 * 9 * 9
	return out + out1 + out2
if len(N) < K:
	ans = 0
elif K == 1:
	ans = K1(N)
elif K == 2:
	ans = K2(N)
else:
	ans = K3(N)
print(ans)


import sys
input = sys.stdin.readline

def solve_K_1(N):
	S = str(N)
	d = len(S)
	return 9 * (d - 1) + int(S[0])

def solve_K_2(N):
	if N <= 99:
		return N - solve_K_1(N)
	S = str(N)
	d = len(S)
	res = 0
	res += 81 * (d - 1) * (d - 2) // 2
	res += 9 * (d - 1) * (int(S[0]) - 1)
	x = 0
	for i in range(1, d):
		if S[i] != '0':
			x = int(S[i])
			break
	i += 1
	res += x + 9 * (d - i)
	return res

def solve_K_3(N):
	if N <= 999:
		return N - solve_K_1(N) - solve_K_2(N)
	S = str(N)
	d = len(S)
	res = 0
	for n in range(3, d):
		res += 729 * (n - 1) * (n - 2) // 2
	res += 81 * (d - 1) * (d - 2) // 2 * (int(S[0]) - 1)
	res += solve_K_2(int(S[1:]))
	return res

def main():
	N = int(input())
	K = int(input())
	if K == 1:
		ans = solve_K_1(N)
	elif K == 2:
		ans = solve_K_2(N)
	elif K == 3:
		ans = solve_K_3(N)
	print(ans)

def __starting_point():
	main()
__starting_point()


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]
				elif k + 1 <= 3:
					dp[i + 1][j | (d < D)][k + 1] += dp[i][j][k]
print(dp[L][0][K] + dp[L][1][K])


from functools import lru_cache
from sys import setrecursionlimit
setrecursionlimit(10000)
N = input()
K = int(input())

@lru_cache()
def f(n, k):
	if k == 0:
		return 1
	if len(n) == 1:
		if k == 1:
			return int(n)
		else:
			return 0
	m = int(n[-1])
	return f(n[:-1], k) + f(n[:-1], k - 1) * m + f(str(int(n[:-1]) - 1), k - 1) * (9 - m)
print(f(N, K))


n = list(map(int, list(input())))
k = int(input())
dp = [[0, 0, 0] for _ in range(len(n))]
counter = 0
for i in range(len(n)):
	dp[i][0] += dp[i - 1][0] + 9 * (counter > 0)
	dp[i][1] += dp[i - 1][0] * 9 + dp[i - 1][1]
	dp[i][2] += dp[i - 1][1] * 9 + dp[i - 1][2]
	if n[i] > 0:
		if counter >= 1 and counter <= 3:
			dp[i][counter - 1] += 1
		counter += 1
		if counter <= 3:
			dp[i][counter - 1] += n[i] - 1
print(dp[len(n) - 1][k - 1] + (counter == k))


s = input()
n = len(s)
K = int(input())
dp = [[[0] * 5 for _ in range(2)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
	ni = int(s[i])
	for k in range(4):
		dp[i + 1][1][k + 1] += dp[i][1][k] * 9
		dp[i + 1][1][k] += dp[i][1][k]
		if ni > 0:
			dp[i + 1][1][k + 1] += dp[i][0][k] * (ni - 1)
			dp[i + 1][1][k] += dp[i][0][k]
		if ni > 0:
			dp[i + 1][0][k + 1] = dp[i][0][k]
		else:
			dp[i + 1][0][k] = dp[i][0][k]
ans = dp[n][0][K] + dp[n][1][K]
print(ans)


import functools
import sys

@functools.lru_cache(None)
def doit(n, k):
	if len(n) == 0 or k < 0:
		return k == 0
	d = int(n[0])
	return sum((doit(n[1:] if i == d else '9' * (len(n) - 1), k - 1 if i > 0 else k) for i in range(d + 1)))
sys.setrecursionlimit(404)
print(doit(input(), int(input())))


import sys
from functools import lru_cache
N = int(sys.stdin.readline().rstrip())
K = int(sys.stdin.readline().rstrip())

@lru_cache(None)
def F(N, K):
	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))


import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
dp1 = [0] * (k + 1)
dp2 = [0] * (k + 1)
dp1[0] = 1
for x in map(int, str(n)):
	for j in range(k, -1, -1):
		if j > 0:
			dp2[j] += dp2[j - 1] * 9
			if x != 0:
				dp2[j] += dp1[j - 1] * (x - 1) + dp1[j]
				dp1[j] = dp1[j - 1]
		else:
			dp2[j] = 1
			dp1[j] = 0
print(dp1[k] + dp2[k])


n = [int(c) for c in input()]
k = int(input())
dp0 = [1, n[0] - 1] + [0 for j in range(2, k + 1)]
dp1 = [0, 1] + [0 for j in range(2, k + 1)]
for i in range(2, len(n) + 1):
	for j in range(k, 0, -1):
		dp0[j] = dp0[j - 1] * 9 + dp0[j] + dp1[j - 1] * max(n[i - 1] - 1, 0) + dp1[j] * int(n[i - 1] != 0)
	if n[i - 1] != 0:
		dp1 = [0] + dp1[:-1]
print(dp0[-1] + dp1[-1])


N = input()
L = len(N)
K = int(input())
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(K + 1):
		for k in range(2):
			nd = int(N[i])
			for d in range(10):
				ni = i + 1
				nj = j
				nk = k
				if d != 0:
					nj += 1
				if nj > K:
					continue
				if k == 0:
					if d > nd:
						continue
					if d < nd:
						nk = 1
				dp[ni][nj][nk] += dp[i][j][k]
print(dp[L][K][0] + dp[L][K][1])


from sys import stdin
from functools import lru_cache
N = int(stdin.readline().rstrip())
K = int(stdin.readline().rstrip())

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


n = input()
k = int(input())
dp = [[0] * (k + 2) for _ in range(2)]
dp[0][0] = 1
for d in n:
	ndp = [[0] * (k + 2) for _ in range(2)]
	for i in range(k + 1):
		ndp[1][i] += dp[1][i]
		ndp[1][i + 1] += dp[1][i] * 9
		if d == '0':
			ndp[0][i] += dp[0][i]
		else:
			ndp[1][i] += dp[0][i]
			ndp[1][i + 1] += dp[0][i] * (int(d) - 1)
			ndp[0][i + 1] += dp[0][i]
	dp = ndp
print(dp[0][k] + dp[1][k])


import math

def f(m, k):
	if k > m:
		return 0
	return math.factorial(m) // (math.factorial(m - k) * math.factorial(k)) * 9 ** k

def g(N, k, i):
	if k == 0:
		return 1
	M = len(N) - i
	if M < k:
		return 0
	n = int(N[i])
	s = 0
	if n > 0:
		s += f(M - 1, k) + (n - 1) * f(M - 1, k - 1) + g(N, k - 1, i + 1)
	else:
		s += g(N, k, i + 1)
	return s
N = input()
K = int(input())
print(g(N, K, 0))


n = input()
k = int(input())
DP = [[0] * (k + 3), [0] * (k + 3)]
DP[0][0] = 1
for num in n:
	num = int(num)
	for num_count in range(k + 1, -1, -1):
		DP[1][num_count] += DP[1][num_count - 1] * 9 + DP[0][num_count - 1] * max(0, num - 1)
		if num != 0:
			DP[0][num_count] = DP[0][num_count - 1] * 1
			DP[1][num_count - 1] += DP[0][num_count - 1]
			DP[0][num_count - 1] = 0
		else:
			continue
ans = DP[1][k] + DP[0][k]
print(ans)


N = int(input())
K = int(input())
n = str(N)
dp = [[0] * (K + 1) for i in range(len(n))]
dp[0][0] = 1
dp[0][1] = int(n[0])
count = 1
for i in range(len(n) - 1):
	dp[i + 1][0] += dp[i][0]
	dp[i + 1][1] += dp[i][0] * 9
	for j in range(1, K):
		dp[i + 1][j] += dp[i][j]
		dp[i + 1][j + 1] += max((dp[i][j] - 1) * 9 + int(n[i + 1]), 0) if j == count else dp[i][j] * 9
	if int(n[i + 1]) != 0:
		count += 1
	dp[i + 1][K] += dp[i][K]
print(dp[-1][-1])


n = input()
k = int(input())
dp = [[[0] * 2 for i in range(k + 2)] for j 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 + 1):
		if x == 0:
			dp[i + 1][j][0] += dp[i][j][0]
		else:
			dp[i + 1][j + 1][0] += dp[i][j][0]
		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][1] * 9
		if x != 0:
			dp[i + 1][j + 1][1] += dp[i][j][0] * max(x - 1, 0)
print(dp[-1][k][0] + dp[-1][k][1])


import sys
sys.setrecursionlimit(10 ** 8)
ini = lambda : int(sys.stdin.readline())
inm = lambda : map(int, sys.stdin.readline().split())
inl = lambda : list(inm())
ins = lambda : sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print('\x1b[33m', *a, '\x1b[0m', **dict(file=sys.stderr, **kw))
N = ins()
K = ini()

def solve():
	M = len(N)
	dp_eq = [[0 for _ in range(K + 1)] for _ in range(M)]
	dp_less = [[0 for _ in range(K + 1)] for _ in range(M)]
	dp_eq[0][K - 1] = 1
	dp_less[0][K] = 1
	dp_less[0][K - 1] = ord(N[0]) - ord('0') - 1
	for i in range(1, M):
		is_zero = N[i] == '0'
		for k in range(K + 1):
			if is_zero:
				dp_eq[i][k] = dp_eq[i - 1][k]
			elif k < K:
				dp_eq[i][k] = dp_eq[i - 1][k + 1]
			dp_less[i][k] = dp_less[i - 1][k]
			if k < K:
				dp_less[i][k] += dp_less[i - 1][k + 1] * 9
			if not is_zero:
				dp_less[i][k] += dp_eq[i - 1][k]
				if k < K:
					dp_less[i][k] += dp_eq[i - 1][k + 1] * (ord(N[i]) - ord('0') - 1)
	return dp_eq[M - 1][0] + dp_less[M - 1][0]
print(solve())


import sys
readline = sys.stdin.readline
L = list(map(int, readline().strip()))
LN = len(L)
K = int(readline())
dpp = [0] * (K + 1)
dpp[1] = 1
dpn = [0] * (K + 1)
dpn[0] = 1
dpn[1] = L[0] - 1
for l in L[1:]:
	dpp2 = [0] * (K + 1)
	dpn2 = dpn[:]
	for i in range(1, K + 1):
		dpn2[i] += 9 * dpn[i - 1]
		if l:
			dpn2[i] += (l - 1) * dpp[i - 1] + dpp[i]
	if not l:
		dpp2 = dpp[:]
	else:
		for i in range(1, K + 1):
			dpp2[i] = dpp[i - 1]
	dpp = dpp2[:]
	dpn = dpn2[:]
print(dpp[K] + dpn[K])


from functools import lru_cache

@lru_cache(None)
def f(n, k):
	if n < 10:
		if k < 1:
			return 1
		if k < 2:
			return n
		return 0
	(d, m) = divmod(n, 10)
	c = 0
	if k:
		c += f(d, k - 1) * m
		c += f(d - 1, k - 1) * (9 - m)
	c += f(d, k)
	return c
print(f(int(input()), int(input())))


N = int(input())
K = int(input())
memo_d = dict()

def key_check(n, k):
	if k == 0:
		return 1
	elif n < 10 ** (k - 1):
		return 0
	elif n < 10:
		return n
	x = memo_d.get((n, k))
	if x is None:
		x = aez(n, k)
	return x

def aez(n, k):
	nq = n // 10
	nr = n % 10
	return nr * key_check(nq, k - 1) + (9 - nr) * key_check(nq - 1, k - 1) + key_check(nq, k)
if N < 10 ** (K - 1):
	ans = 0
elif N < 10:
	ans = N
else:
	ans = aez(N, K)
print(ans)


n = input()
K = int(input())
len_n = len(n)
dp = [[[0] * 2 for _ in range(K + 2)] for _ in range(len_n + 1)]
dp[0][0][1] = 1
for i in range(1, len_n + 1):
	d = int(n[i - 1])
	for j in range(K + 1):
		dp[i][j][0] += dp[i - 1][j][0]
		dp[i][j + 1][0] += dp[i - 1][j][0] * 9
		if 0 < d:
			dp[i][j + 1][0] += dp[i - 1][j][1] * (d - 1)
			dp[i][j][0] += dp[i - 1][j][1]
			dp[i][j + 1][1] += dp[i - 1][j][1]
		else:
			dp[i][j][1] += dp[i - 1][j][1]
ans = dp[-1][K][0] + dp[-1][K][1]
print(ans)


n = input()
k = int(input())
l = len(n)
dp = [[[0 for _ in range(2)] for _ in range(5)] for _ in range(l + 1)]
dp[0][1][1] = int(n[0]) - 1
dp[0][1][0] = 1
dp[0][0][1] = 1
for i in range(1, l):
	for j in range(4):
		b = i - 1
		now = int(n[i])
		if now == 0:
			dp[i][j][0] += dp[b][j][0]
		else:
			dp[i][j][1] += dp[b][j][0]
			dp[i][j + 1][1] += dp[b][j][0] * (now - 1)
			dp[i][j + 1][0] += dp[b][j][0]
		dp[i][j][1] += dp[b][j][1]
		dp[i][j + 1][1] += 9 * dp[b][j][1]
print(dp[l - 1][k][0] + dp[l - 1][k][1])


N = int(input())
K = int(input())
ans = 0
if K == 3:
	for a in range(1, 10):
		for b in range(1, 10):
			for c in range(1, 10):
				ap = 0
				bp = 0
				cp = 0
				while a * 10 ** ap <= N:
					ap += 1
				ap -= 1
				while a * 10 ** ap + b * 10 ** bp <= N and bp < ap:
					bp += 1
				bp -= 1
				while a * 10 ** ap + b * 10 ** bp + c * 10 ** cp <= N and cp < bp:
					cp += 1
				cp -= 1
				ans += 1 + cp + bp * (bp - 1) // 2 + ap * (ap - 1) * (ap - 2) // 6
	print(ans)
elif K == 2:
	ans = 0
	for i in range(100):
		for j in range(100):
			if i > j:
				for a in range(1, 10):
					for b in range(1, 10):
						if a * 10 ** i + b * 10 ** j <= N:
							ans += 1
	print(ans)
else:
	ans = 0
	for i in range(100):
		for a in range(1, 10):
			if a * 10 ** i <= N:
				ans += 1
	print(ans)


S = input()
L = len(S)
K = int(input())
dp = [[[0, 0] for _ in range(K + 1)] for _ in range(L + 1)]
dp[0][0][0] = 1
for (i, c) in enumerate(S):
	c = int(c)
	for k in reversed(range(K + 1)):
		for d in range(10):
			nk = k + (d > 0)
			if nk > K:
				continue
			dp[i + 1][nk][1] += dp[i][k][1]
			if d > c:
				continue
			less = int(d < c)
			dp[i + 1][nk][less] += dp[i][k][0]
print(sum(dp[-1][-1]))


def f(N, K):
	n = len(str(N))
	if n == 1:
		if K == 1:
			return N
		else:
			return 0
	elif n == 2:
		if K == 1:
			return 9 + N // 10
		elif K == 2:
			return N - 9 - N // 10
		else:
			return 0
	elif n == 3:
		if K == 1:
			return 18 + N // 100
		elif K == 2:
			return 81 + 18 * (N // 100 - 1) + f(N % 100, 1)
		else:
			return 81 * (N // 100 - 1) + f(N % 100, 2)
	elif K == 1:
		return 9 * (n - 1) + N // 10 ** (n - 1)
	elif K == 2:
		return 81 * (n - 1) * (n - 2) / 2 + 9 * (n - 1) * (N // 10 ** (n - 1) - 1) + f(N % 10 ** (n - 1), 1)
	else:
		return 243 * (n ** 3 - 6 * n ** 2 + 11 * n - 6) / 2 + 81 * (n - 1) * (n - 2) * (N // 10 ** (n - 1) - 1) / 2 + f(N % 10 ** (n - 1), 2)
N = int(input())
K = int(input())
print(int(f(N, K)))


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf, comb
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)

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

def INT():
	return int(input())

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

def MAP1():
	return [int(x) - 1 for x in input().split()]

def LIST():
	return list(MAP())

def LIST1():
	return list(MAP1())

def solve(n, k, m):
	ans = 0
	for i in range(k, m):
		if k == 1:
			ans += 9
		else:
			ans += pow(9, k) * comb(i - 1, k - 1)
	if k == 1:
		ans += int(n[0])
	elif k == 2:
		ans += (int(n[0]) - 1) * pow(9, k - 1) * comb(m - 1, k - 1)
		j = 1
		while j < m and n[j] == '0':
			j += 1
		if j < m:
			ans += int(n[j]) + pow(9, k - 1) * comb(m - 1 - j, k - 1)
	else:
		while m >= k and n.count('0') > m - k:
			n = str(int(n) - 1)
		if m > len(n):
			print(ans)
			return ans
		m = len(n)
		a = []
		for i in range(m):
			if len(a) < 3 and n[i] != '0':
				a.append(i)
		if len(a) == 3:
			ans += 1 + int(n[a[2]]) - 1 + 9 * comb(m - 1 - a[2], 1)
			ans += (int(n[a[1]]) - 1) * 9 * comb(m - 1 - a[1], 1) + 9 * 9 * comb(m - 1 - a[1], 2)
			ans += (int(n[a[0]]) - 1) * 9 * 9 * comb(m - 1 - a[0], 2)
	print(ans)
	return ans

def solve2(n, k, m):
	ans = 0
	for i in range(1, int(n) + 1):
		if len(str(i)) - str(i).count('0') == k:
			ans += 1
	print(ans)
	return ans

def __starting_point():
	n = input()
	k = INT()
	m = len(n)
	solve(n, k, m)
__starting_point()


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

def rec(N, K):
	if K == 0:
		return 1
	if len(N) < K:
		return 0
	lsb = int(N[-1])
	if len(N) == 1:
		return lsb
	return rec(N[:-1], K - 1) * lsb + rec(str(int(N[:-1]) - 1), K - 1) * (9 - lsb) + rec(N[:-1], K)
print(rec(N, K))


from math import factorial as f
from functools import reduce

def C(n, k):
	(a, b) = sorted((k, n - k))
	return reduce(int.__mul__, range(b + 1, n + 1), 1) // f(a)

def almost_everywhere_zero(v, k):
	if not v or not k:
		return 0
	s = str(v)
	(n, d) = (len(s), int(s[0]))
	if k > n:
		return 0
	below = 9 ** k * C(n - 1, k) if n > k else 0
	return below + (d if k == 1 else (d - 1) * 9 ** (k - 1) * C(n - 1, k - 1) + almost_everywhere_zero(int(s[1:]), k - 1))
N = input()
K = int(input())
print(almost_everywhere_zero(N, K))


from itertools import combinations

def c(N, K):
	for (i, n) in enumerate(N):
		if n != 0:
			break
	N = N[i:]
	a = len(N)
	if a < K:
		return 0
	if K == 1:
		return N[0] + 9 * (a - 1)
	return (N[0] - 1) * c([9] * (a - 1), K - 1) + c(N[1:], K - 1) + c([9] * (a - 1), K)

def main():
	N = list(map(int, input()))
	K = int(input())
	return c(N, K)
print(main())


import functools
N = int(input())
K = int(input())

@functools.lru_cache()
def func(num, counter):
	remain = num % 10
	quotient = num // 10
	if counter == 0:
		return 1
	if num < 10:
		if counter == 1:
			return num
		else:
			return 0
	return func(quotient, counter - 1) * remain + func(quotient - 1, counter - 1) * (9 - remain) + func(quotient, counter)
print(func(N, K))


N = input()
K = int(input())
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	n = int(N[i])
	for j in range(2):
		for k in range(K + 1):
			for d in range((9 if j == 1 else n) + 1):
				if k + int(d != 0) <= K:
					dp[i + 1][j | (d < n)][k + int(d != 0)] += dp[i][j][k]
n_self = int(len(N) - N.count('0') == K)
print(dp[-1][-1][-1] + n_self)


n = input()
k = int(input())
m = len(n)
dp = [[[0] * 2 for _ in range(4)] for _ in range(m + 1)]
dp[0][0][0] = 1
for i in range(m):
	keta = int(n[i])
	for j in range(3):
		dp[i + 1][j + 1][1] += 9 * dp[i][j][1]
		dp[i + 1][j][1] += dp[i][j][1]
		if keta > 0:
			dp[i + 1][j + 1][1] += dp[i][j][0] * (keta - 1)
			dp[i + 1][j][1] += dp[i][j][0]
			dp[i + 1][j + 1][0] += dp[i][j][0]
		else:
			dp[i + 1][j][0] += dp[i][j][0]
	dp[i + 1][3][1] += dp[i][3][1]
	dp[i + 1][3][keta > 0] += dp[i][3][0]
print(dp[m][k][0] + dp[m][k][1])


s = input()
K = int(input())
n = len(s)
dp = [[[0] * 5 for _ in range(2)] for _ in range(10001)]
dp[0][0][0] = 1
for i in range(n):
	for k in range(K + 1):
		x = int(s[i])
		dp[i + 1][1][k + 1] += dp[i][1][k] * 9
		dp[i + 1][1][k] += dp[i][1][k]
		if x > 0:
			dp[i + 1][1][k + 1] += dp[i][0][k] * (x - 1)
			dp[i + 1][1][k] += dp[i][0][k]
			dp[i + 1][0][k + 1] = dp[i][0][k]
		else:
			dp[i + 1][0][k] = dp[i][0][k]
print(dp[n][0][k] + dp[n][1][k])


K = input()
N = len(K)
KK = int(input())
dp = [[[0] * 5 for _ in range(2)] for _ in range(N + 1)]
dp[0][0][0] = 1
for (i, s) in enumerate(K):
	a = ord(s) - 48
	for j in range(4):
		for k in range(10):
			p = j + 1 if k else j
			dp[i + 1][1][p] += dp[i][1][j]
			if k < a:
				dp[i + 1][1][p] += dp[i][0][j]
	for j in range(4):
		p = j + 1 if a else j
		dp[i + 1][0][p] += dp[i][0][j]
print(dp[N][0][KK] + dp[N][1][KK])


N = input()
k = int(input())
ln = len(N)
DP = [[[0] * 2 for _ in range(k + 1)] for _ in range(len(N) + 1)]
DP[0][0][0] = 1
for i in range(1, len(N) + 1):
	DP[i][0][1] = 1
for i in range(len(N)):
	ni = int(N[i])
	for j in range(1, k + 1):
		DP[i + 1][j][1] = DP[i][j][1] + max(0, ni - 1) * DP[i][j - 1][0] + 9 * DP[i][j - 1][1]
		if ni == 0:
			DP[i + 1][j][0] = DP[i][j][0]
		else:
			DP[i + 1][j][0] = DP[i][j - 1][0]
			DP[i + 1][j][1] += DP[i][j][0]
print(DP[ln][k][0] + DP[ln][k][1])


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
	return None

def cnt(n, k):
	if k == 0:
		return 1
	if k > len(n):
		return 0
	return comb(len(n) - 1, k) * 9 ** k + (int(n[0]) - 1) * comb(len(n) - 1, k - 1) * 9 ** (k - 1) + cnt(n[1:].lstrip('0'), k - 1)

def main():
	n = input()
	k = int(input())
	print(cnt(n, k))
main()


import numpy as np
N = input()
K = int(input())
dp = np.zeros((len(N) + 1, K + 1), np.int64)
dp[1, 1] = 1
for d in range(1, len(N)):
	dp[d + 1] = dp[d]
	dp[d + 1, 1:] += dp[d, :-1]
ans = 0
for (i, c) in enumerate(N):
	n = len(N) - i
	if c != '0':
		ans += np.sum(dp[:n, K]) * 9 ** K
		ans += dp[n, K] * (int(c) - 1) * 9 ** (K - 1)
		K -= 1
		if K == 0:
			ans += 1
			break
print(ans)


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

def c(n, k):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k == 2:
		return n * (n - 1) // 2
	else:
		return n * (n - 1) * (n - 2) // 6

def f(N, K):
	if N == 0 and K > 0:
		return 0
	if K == 0:
		return 1
	digit = len(str(N))
	ret = 0
	if digit > K:
		ret += c(digit - 1, K) * 9 ** K
	a = 10 ** (digit - 1)
	d = N // a
	ret += (d - 1) * c(digit - 1, K - 1) * 9 ** (K - 1)
	ret += f(N - d * a, K - 1)
	return ret
print(f(N, K))


def comb(n, k):
	c = 1
	for i in range(k):
		c *= n - i
		c //= i + 1
	return c
n = [int(i) for i in input()]
l = len(n)
k = int(input())
count = 0
for i in range(l):
	if n[i] > 0:
		count += 9 ** k * comb(l - i - 1, k)
		if k >= 1:
			count += 9 ** (k - 1) * comb(l - i - 1, k - 1) * (n[i] - 1)
		else:
			break
		k -= 1
	if i == l - 1 and k == 0:
		count += 1
print(count)


def zeroTrim(s):
	while s[0] == '0':
		if len(s) == 1:
			break
		s = s[1:]
	return s
N = input()
K = int(input())

def calc(N, K):
	digit = len(N)
	res = 0
	if K == 1:
		if digit > 1:
			res += (digit - 1) * 9
		res += int(N[0])
	elif K == 2:
		if digit <= 1:
			return 0
		if digit > 2:
			res += 9 * 9 * (digit - 1) * (digit - 2) // 2
		for i in range(int(N[0]) - 1):
			res += calc('9' * (digit - 1), 1)
		res += calc(zeroTrim(N[1:]), 1)
	else:
		if digit <= 2:
			return 0
		if digit > 3:
			res += 9 * 9 * 9 * (digit - 1) * (digit - 2) * (digit - 3) // 6
		for i in range(int(N[0]) - 1):
			res += calc('9' * (digit - 1), 2)
		res += calc(zeroTrim(N[1:]), 2)
	return res
print(calc(N, K))


import sys
input = lambda : sys.stdin.readline().rstrip()

def solve():
	N = list(map(int, input()))
	K = int(input())
	if K == 1:
		ans = (len(N) - 1) * 9 + N[0]
	elif K == 2:
		if len(N) < 2:
			print(0)
			return
		ans = 9 ** 2 * (len(N) - 1) * (len(N) - 2) // 2
		ans += (N[0] - 1) * (len(N) - 1) * 9
		for i in range(1, len(N)):
			if N[i] != 0:
				ans += N[i] + (len(N) - i - 1) * 9
				break
	elif K == 3:
		if len(N) < 3:
			print(0)
			return
		ans = 9 ** 3 * (len(N) - 1) * (len(N) - 2) * (len(N) - 3) // 6
		ans += (N[0] - 1) * 9 ** 2 * (len(N) - 1) * (len(N) - 2) // 2
		for i in range(1, len(N) - 1):
			if N[i] != 0:
				ans += 9 ** 2 * (len(N) - i - 1) * (len(N) - i - 2) // 2
				ans += (N[i] - 1) * (len(N) - i - 1) * 9
				for j in range(i + 1, len(N)):
					if N[j] != 0:
						ans += N[j] + (len(N) - j - 1) * 9
						break
				break
	print(ans)

def __starting_point():
	solve()
__starting_point()


N = list(map(int, input()))
K = int(input())

def f(n, k):
	if len(n) == 1:
		if k == 1:
			return n[0]
		else:
			return 0
	else:
		r = n[-1]
		m = n[:-1]
		m2 = m.copy()
		m2[-1] = m2[-1] - 1
		for i in range(len(m)):
			if m2[-i] < 0:
				m2[-i] += 10
				m2[-i - 1] = m2[-i - 1] - 1
		if k == 1:
			m = n[:-1]
			return f(m, 1) + 9
		else:
			return f(m, k) + f(m, k - 1) * r + f(m2, k - 1) * (9 - r)
print(f(N, K))


N = input()
K = int(input())
if len(N) < K:
	print(0)
	return
ans = [1, int(N[-1]), 0, 0]

def combination(N, K):
	if N < K:
		return 0
	else:
		p = 1
		for k in range(K):
			p *= N
			N -= 1
		for k in range(1, K + 1):
			p //= k
		return p
for k in range(1, len(N)):
	if int(N[-k - 1]) > 0:
		a = [1, 0, 0, 0]
		for j in range(1, K + 1):
			a[j] += 9 ** j * combination(k, j)
			a[j] += (int(N[-k - 1]) - 1) * combination(k, j - 1) * 9 ** (j - 1) + ans[j - 1]
		ans = a
print(ans[K])


N = list(map(int, input()))
K = int(input())
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	for j in range(K + 1):
		for is_smaller in range(2):
			for l in range(10):
				if not is_smaller and l > N[i] or (l != 0 and j + 1 > K):
					continue
				i_ = i + 1
				j_ = j
				is_smaller_ = is_smaller
				if l != 0:
					j_ += 1
				if not is_smaller and l < N[i]:
					is_smaller_ = 1
				dp[i_][j_][is_smaller_] += dp[i][j][is_smaller]
print(dp[len(N)][K][0] + dp[len(N)][K][1])


s = input() + '9'
n = len(s)
X = [0] * 4
Y = [0] * 4
while n:
	n -= 1
	k = 4
	while k:
		k -= 1
		a = int(s[n])
		(Y[k], X[k]) = (X[k] + (a - 1) * X[k - 1] + Y[k - 1] if a else Y[k], X[k] + 9 * X[k - 1]) if k else (1, 1)
print(Y[int(input())])


n = input()
k = int(input())
l = len(n)
dp = [[[0] * (k + 1) for j in range(2)] for i in range(l + 1)]
dp[0][0][0] = 1
for i in range(l):
	for j in range(2):
		for o in range(k + 1):
			for m in range(10):
				if not j and m > int(n[i]):
					continue
				f = j or m < int(n[i])
				o2 = o + (m != 0)
				if o2 > k:
					continue
				dp[i + 1][f][o2] += dp[i][j][o]
print(dp[-1][0][k] + dp[-1][1][k])


from functools import lru_cache

@lru_cache(None)
def solve(n, k):
	if n <= 9 and k == 1:
		return n
	elif n <= 9 and k >= 2:
		return 0
	elif k == 0:
		return 1
	else:
		m = n // 10
		r = n % 10
		return r * solve(m, k - 1) + (9 - r) * solve(m - 1, k - 1) + solve(m, k)
n = int(input())
k = int(input())
print(solve(n, k))


import math

def solve(sN):
	dp = [[[0] * 105 for _ in range(4)] for _ in range(2)]
	dp[0][0][0] = 1
	for i in range(len(sN)):
		for j in range(4):
			for k in range(2):
				nd = int(sN[i])
				for d in range(10):
					ni = i + 1
					nj = j
					nk = k
					if d != 0:
						nj += 1
					if nj > K:
						continue
					if k == 0:
						if d > nd:
							continue
						if d < nd:
							nk = 1
					dp[nk][nj][ni] += dp[k][j][i]
	ans = dp[0][K][len(sN)] + dp[1][K][len(sN)]
	return ans
sN = input()
K = int(input())
lenN = len(sN)
ans = solve(sN)
print(ans)


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

def solve(N, K):
	l = len(N)
	dp = [[[0] * 10 for i 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 k in range(K + 1):
				for d in range(10):
					if j == 0 and d > D:
						break
					dp[i + 1][j or d < D][k if d == 0 else k + 1] += dp[i][j][k]
	return dp[l][0][K] + dp[l][1][K]
print(solve(N, K))


def calc(a, D, K):
	if K == 1:
		return a + (D - 1) * 9
	elif K == 2:
		return (a - 1) * (D - 1) * 9 + (D - 1) * (D - 2) / 2 * 81
	else:
		return (a - 1) * (D - 1) * (D - 2) / 2 * 81 + (D - 1) * (D - 2) * (D - 3) / 6 * 729
N = str(input())
K = int(input())
D = len(N)
score = 0
for (i, a) in enumerate(N):
	if a != '0':
		score += calc(int(a), D - i, K)
		K -= 1
	if K == 0:
		break
print(int(score))


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()

def main():
	s = S()
	n = len(s)
	K = I()
	dp = [[[0] * 2 for _ in range(4)] for __ in range(n + 1)]
	dp[0][0][0] = 1
	for i in range(n):
		nd = int(s[i])
		for j in range(4):
			for k in range(2):
				for d in range(10):
					ni = i + 1
					nj = j
					nk = k
					if d != 0:
						nj += 1
					if K < nj:
						continue
					if nk == 0:
						if d < nd:
							nk = 1
						if nd < d:
							continue
					dp[ni][nj][nk] += dp[i][j][k]
	return dp[n][K][0] + dp[n][K][1]
print(main())


def comb(n, k):
	ans = 1
	for i in range(k):
		ans *= n - i
	for i in range(k):
		ans //= k - i
	return ans

def count(n, k):
	if len(n) < k:
		return 0
	if k == 0:
		return 1
	if int(n) == 0:
		return 0
	if n[0] == '0':
		return count(n[1:], k)
	return count(n[1:], k - 1) + comb(len(n) - 1, k) * 9 ** k + (int(n[0]) - 1) * comb(len(n) - 1, k - 1) * 9 ** (k - 1)
n = input()
k = int(input())
print(count(n, k))


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


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import decimal
import queue
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : list(map(int, sys.stdin.readline().split()))
na = lambda : list(map(int, sys.stdin.readline().split()))

def main():
	n = input()
	k = ni()
	l = len(n)
	dp_true = [[0 for _ in range(k + 2)] for i in range(l + 1)]
	dp_false = [[0 for i in range(k + 2)] for j in range(l + 1)]
	dp_false[0][0] = 1
	for i in range(l):
		num = int(n[i])
		for j in range(k + 1):
			dp_true[i + 1][j] += dp_true[i][j]
			dp_true[i + 1][j + 1] += dp_true[i][j] * 9
			if num > 0:
				dp_true[i + 1][j + 1] += dp_false[i][j] * (num - 1)
				dp_true[i + 1][j] += dp_false[i][j]
			if num > 0:
				dp_false[i + 1][j + 1] += dp_false[i][j]
			else:
				dp_false[i + 1][j] += dp_false[i][j]
	print(dp_true[l][k] + dp_false[l][k])

def __starting_point():
	main()
__starting_point()


def f(N, k):
	if not N:
		return 0
	N = str(int(N))
	a = len(N) - 1
	na = int(N[0])
	if k == 1:
		return str(9 * a + na)
	if k == 2:
		return str(9 ** 2 * a * (a - 1) // 2 + (na - 1) * int(f('9' * a, 1)) + int(f(N[1:], 1)))
	if k == 3:
		return str(9 ** 3 * a * (a - 1) * (a - 2) // 6 + (na - 1) * int(f('9' * a, 2)) + int(f(N[1:], 2)))

def solve():
	N = input()
	K = int(input())
	return f(N, K)
print(solve())


def resolve():
	S = input()
	K = int(input())
	n = len(S)
	dp = [[[0] * 2 for _ in range(4)] for _ in range(105)]
	dp[0][0][0] = 1
	for i in range(n):
		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
						if d < nd:
							nk += 1
					dp[ni][nj][nk] += dp[i][j][k]
	ans = dp[n][K][0] + dp[n][K][1]
	print(ans)

def __starting_point():
	resolve()
__starting_point()


import math

def isMore(N, K):
	if len(N) < K:
		return 0
	if K >= 1:
		tmp = (9 - int(N[0])) * fact[len(N) - 1] // (fact[len(N) - K] * fact[K - 1]) * 9 ** (K - 1)
		if len(N) == 1:
			return tmp
		elif len(N) > 1 and N[0] == '0':
			return tmp + isMore(N[1:], K)
		elif len(N) > 1 and N[0] != '0':
			return tmp + isMore(N[1:], K - 1)
	if K == 0:
		return 0
N = input()
K = int(input())
lenN = len(N)
fact = [1] * 101
for i in range(1, 101):
	fact[i] = fact[i - 1] * i
ans = fact[lenN] // (fact[lenN - K] * fact[K]) * 9 ** K
ans -= isMore(N, K)
print(ans)


N = int(input())
K = int(input())
X = str(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(X) + 1)]
dp[0][0][0] = 1
for i in range(len(X)):
	D = int(X[i])
	for j in range(2):
		for k in range(K + 1):
			for d in range((9 if j == 1 else D) + 1):
				if k + int(d != 0) <= K:
					dp[i + 1][j | (d < D)][k + int(d != 0)] += dp[i][j][k]
print(dp[-1][0][-1] + dp[-1][1][-1])


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

def f(n, k):
	m = len(str(n))
	if n < 10 ^ 4:
		s = 0
		for i in range(1, n + 1):
			if sum([1 for j in str(i) if j != '0']) == k:
				s += 1
	elif k == 1:
		s = n // 10 ** (m - 1) + 9 * (m - 1)
	elif k == 2:
		s = (n // 10 ** (m - 1) - 1) * 9 * (m - 1) + f(n % 10 ** (m - 1), 1) + 9 * 9 * (m - 1) * (m - 2) // 2
	elif k == 3:
		s = (n // 10 ** (m - 1) - 1) * 9 * 9 * (m - 1) * (m - 2) // 2 + f(n % 10 ** (m - 1), 2) + 9 * 9 * 9 * (m - 1) * (m - 2) * (m - 3) // 6
	return s
print(f(n, k))


n = input()
k = int(input())
(n1, n2, n3) = (int(n[-1]), 0, 0)
(a1, a2, a3) = (9, 0, 0)
for i in n[-2::-1]:
	i = int(i)
	if i != 0:
		(n1, n2, n3) = (i + a1, (i - 1) * a1 + n1 + a2, (i - 1) * a2 + n2 + a3)
	(a1, a2, a3) = (9 + a1, 9 * a1 + a2, 9 * a2 + a3)
print([n1, n2, n3][k - 1])


n = input()
k = int(input())
dp0 = [0] * 4
dp1 = [1, 0, 0, 0]
for i in n:
	i = int(i)
	(pdp0, pdp1, dp0) = (dp0, dp1, [0] * 4)
	if i != 0:
		dp1 = [0] + pdp1[:-1]
	else:
		dp1 = pdp1
	dp0[0] = pdp0[0] + (i != 0) * pdp1[0]
	for j in range(1, 4):
		dp0[j] = 9 * pdp0[j - 1] + pdp0[j] + (i != 0) * (i - 1) * pdp1[j - 1] + (i != 0) * pdp1[j]
print(dp0[k] + dp1[k])


from math import factorial
N = int(input())
K = int(input())
S = list(map(int, str(N)))

def C(n, r):
	if n >= r:
		return factorial(n) // factorial(r) // factorial(n - r)
	else:
		return 0

def D(i, j):
	return C(i, j) * 9 ** j
ans = 0
l = len(S)
for i in range(l):
	if S[i] != 0:
		ans += (S[i] - 1) * D(l - 1, K - 1) + D(l - 1, K)
		l -= 1
		K -= 1
	else:
		l -= 1
	if K == 0:
		ans += 1
		break
print(ans)


N = int(input())
K = int(input())
S = str(N)
L = len(S)
dp0 = [[0 for _ in range(5)] for _ in range(L + 1)]
dp1 = [[0 for _ in range(5)] for _ in range(L + 1)]
dp0[0][0] = 1
dp0[0][1] = 0
for i in range(L):
	D = int(S[i])
	for j in range(4):
		if D > 0:
			dp1[i + 1][j] += dp1[i][j] + dp0[i][j]
			dp0[i + 1][j + 1] += dp0[i][j]
			dp1[i + 1][j + 1] += dp1[i][j] * 9 + dp0[i][j] * (D - 1)
		else:
			dp0[i + 1][j] += dp0[i][j]
			dp1[i + 1][j] += dp1[i][j]
			dp1[i + 1][j + 1] += dp1[i][j] * 9
print(dp0[L][K] + dp1[L][K])


N = int(input())
K = int(input())
keta = len(str(N))
dp = [[[0] * 2 for _ in range(4)] for _ in range(keta + 1)]
dp[0][0][0] = 1
dp[0][1][0] = 0
dp[0][2][0] = 0
dp[0][3][0] = 0
dp[0][0][1] = 0
dp[0][1][1] = 0
dp[0][2][1] = 0
dp[0][3][1] = 0
for i in range(1, keta + 1):
	n = int(str(N)[i - 1])
	if n == 0:
		dp[i][0][0] = dp[i - 1][0][0]
		dp[i][1][0] = dp[i - 1][1][0]
		dp[i][2][0] = dp[i - 1][2][0]
		dp[i][3][0] = dp[i - 1][3][0]
		dp[i][0][1] = dp[i - 1][0][1]
		dp[i][1][1] = dp[i - 1][1][1] + dp[i - 1][0][1] * 9
		dp[i][2][1] = dp[i - 1][2][1] + dp[i - 1][1][1] * 9
		dp[i][3][1] = dp[i - 1][3][1] + dp[i - 1][2][1] * 9
	elif n != 0:
		dp[i][0][0] = 0
		dp[i][1][0] = dp[i - 1][0][0]
		dp[i][2][0] = dp[i - 1][1][0]
		dp[i][3][0] = dp[i - 1][2][0]
		dp[i][0][1] = dp[i - 1][0][0] + dp[i - 1][0][1]
		dp[i][1][1] = dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][0][0] * (n - 1) + dp[i - 1][0][1] * 9
		dp[i][2][1] = dp[i - 1][2][0] + dp[i - 1][2][1] + dp[i - 1][1][0] * (n - 1) + dp[i - 1][1][1] * 9
		dp[i][3][1] = dp[i - 1][3][0] + dp[i - 1][3][1] + dp[i - 1][2][0] * (n - 1) + dp[i - 1][2][1] * 9
print(sum(dp[keta][K]))


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


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


N = int(input())
K = int(input())
X = str(N)
dp = [[[0] * (K + 1) for _ in range(2)] for _ in range(len(X) + 1)]
dp[0][0][0] = 1
for i in range(len(X)):
	digit = int(X[i])
	for j in range(2):
		for k in range(K + 1):
			for d in range(10 if j == 1 else digit + 1):
				if k + int(d != 0) <= K:
					dp[i + 1][j | (d < digit)][k + (d != 0)] += dp[i][j][k]
print(dp[-1][0][-1] + dp[-1][1][-1])


N = input()
K = int(input())
dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	dgt = int(N[i])
	for k in range(K + 1):
		dp[i + 1][1][k + 1] += dp[i][1][k] * 9
		dp[i + 1][1][k] += dp[i][1][k]
		if dgt > 0:
			dp[i + 1][1][k + 1] += dp[i][0][k] * (dgt - 1)
			dp[i + 1][1][k] += dp[i][0][k]
			dp[i + 1][0][k + 1] = dp[i][0][k]
		else:
			dp[i + 1][0][k] = dp[i][0][k]
print(dp[len(N)][0][K] + dp[len(N)][1][K])


from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
MAXN = 100
n = input()
k = int(input())
dl = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]
de = [[None] * (MAXN + 1) for _ in range(MAXN + 1)]

def n_num_e(d, i):
	if d == 0:
		if i == 0:
			return 1
		else:
			return 0
	elif de[d][i] is not None:
		return de[d][i]
	else:
		if int(n[d - 1]) == 0:
			result = n_num_e(d - 1, i)
		else:
			result = n_num_e(d - 1, i - 1)
		de[d][i] = result
		return result

def n_num_l(d, i):
	if d == 0:
		return 0
	elif dl[d][i] is not None:
		return dl[d][i]
	else:
		if int(n[d - 1]) == 0:
			ne = 0
			nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
			result = ne + nl
		else:
			ne = (int(n[d - 1]) - 1) * n_num_e(d - 1, i - 1) + n_num_e(d - 1, i)
			nl = 9 * n_num_l(d - 1, i - 1) + n_num_l(d - 1, i)
			result = ne + nl
		dl[d][i] = result
		return result
answer = n_num_e(len(n), k) + n_num_l(len(n), k)
print(answer)


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


def main():
	n = input()
	non_zero = int(input())
	length = len(n)
	dp = [[[0, 0] for _ in range(non_zero + 1)] for _ in range(length + 1)]
	dp[0][0][0] = 1
	for i in range(length):
		for j in range(non_zero + 1):
			for k in range(2):
				now_digit = int(n[i])
				for next_d in range(10):
					new_i = i + 1
					new_j = j
					new_k = k
					if next_d > 0:
						new_j += 1
					if new_j > non_zero:
						continue
					if k == 0:
						if next_d > now_digit:
							continue
						elif next_d < now_digit:
							new_k = 1
					dp[new_i][new_j][new_k] += dp[i][j][k]
	print(sum(dp[length][non_zero]))

def __starting_point():
	main()
__starting_point()


def almost0(m, K):
	M = str(m)
	s = len(M)
	if s < K:
		return 0
	elif m == 0:
		return 0
	elif K == 0:
		return 0
	elif K == 1:
		return int(M[0]) + almost0(10 ** (len(M) - 1) - 1, K)
	elif K == 2:
		return (int(M[0]) - 1) * 9 * (len(M) - 1) + almost0(m % 10 ** (len(M) - 1), K - 1) + almost0(10 ** (len(M) - 1) - 1, K)
	else:
		return (int(M[0]) - 1) * 81 * (s - 1) * (s - 2) // 2 + almost0(m % 10 ** (s - 1), K - 1) + almost0(10 ** (s - 1) - 1, K)
N = int(input())
K = int(input())
print(almost0(N, K))


n = input()
K = int(input())
l = len(n)
dp = [[[0 for _ in range(5)] 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 k in range(4):
			for d in range((9 if j == 1 else D) + 1):
				J = j == 1 or d < D
				if d != 0:
					dp[i + 1][1 if J else 0][k + 1] += dp[i][j][k]
				else:
					dp[i + 1][1 if J else 0][k] += dp[i][j][k]
print(dp[l][0][K] + dp[l][1][K])


n = input()
k = int(input())
l = len(n)
dp = [[[0, 0] for j in range(5)] for i in range(l + 1)]
dp[0][0][1] = 1
for i in range(l):
	for j in range(k + 1):
		dp[i + 1][j + 1][0] += 9 * dp[i][j][0]
		dp[i + 1][j][0] += dp[i][j][0]
		if n[i] == '0':
			dp[i + 1][j][1] = dp[i][j][1]
		else:
			dp[i + 1][j][0] += dp[i][j][1]
			dp[i + 1][j + 1][0] += (int(n[i]) - 1) * dp[i][j][1]
			dp[i + 1][j + 1][1] += dp[i][j][1]
print(dp[l][k][1] + dp[l][k][0])


def nCkpow(n, k):
	if n < k:
		return 0
	y = 1
	for i in range(k):
		y *= n - i
		y //= i + 1
		y *= 9
	return y

def f(s, m, k):
	if len(s) - m < k:
		return 0
	if k == 0:
		return 1
	if s[m] == '0':
		return f(s, m + 1, k)
	l = len(s) - m
	y = nCkpow(l - 1, k)
	y += (int(s[m]) - 1) * nCkpow(l - 1, k - 1)
	return y + f(s, m + 1, k - 1)
N = input()
K = int(input())
print(f(N, 0, K))


n = int(input())
K = int(input())

def make_list(n):
	N = []
	while n > 0:
		N.append(n % 10)
		n = n // 10
	N.reverse()
	return N
N = make_list(n)
m = len(N)
dp = [[[0 for k in range(K + 1)] for j in range(2)] for i in range(m)]
dp[0][0][0] = 1
dp[0][0][1] = N[0] - 1
dp[0][1][0] = 0
dp[0][1][1] = 1
for i in range(1, m):
	dp[i][0][0] = 1
	for k in range(1, K + 1):
		if N[i] == 0:
			dp[i][0][k] = dp[i - 1][0][k - 1] * 9 + dp[i - 1][0][k]
			dp[i][1][k] = dp[i - 1][1][k]
		else:
			dp[i][0][k] = dp[i - 1][0][k - 1] * 9 + dp[i - 1][0][k] + dp[i - 1][1][k] + dp[i - 1][1][k - 1] * (N[i] - 1)
			dp[i][1][k] = dp[i - 1][1][k - 1]
print(dp[m - 1][1][K] + dp[m - 1][0][K])


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


import math
n = int(input())
k = int(input())

def comb(n, k):
	s = 1
	for i in range(k):
		s *= n - i
	for i in range(k):
		s //= i + 1
	return s

def ans(n, k):
	s = 0
	if int(str(n)[0]) == 0:
		return 0
	if len(str(n)) < k:
		return 0
	elif len(str(n)) == k:
		s += (int(str(n)[0]) - 1) * comb(len(str(n)) - 1, k - 1) * 9 ** (k - 1)
		if k - 1 == 0:
			s += 1
		else:
			s += ans(int(str(n)[1:]), k - 1)
		return s
	else:
		s += (int(str(n)[0]) - 1) * comb(len(str(n)) - 1, k - 1) * 9 ** (k - 1)
		if k - 1 == 0:
			s += 1
		else:
			s += ans(int(str(n)[1:]), k - 1)
		s += comb(len(str(n)) - 1, k) * 9 ** k
		return s
print(ans(n, k))


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


N = input()
K = int(input())
dp = [[[0] * 2 for j in range(K + 1)] for i in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	n = int(N[i])
	for j in range(K + 1):
		for ltn in range(2):
			for x in range(10 if ltn else n + 1):
				if j + (x > 0) > K:
					continue
				dp[i + 1][j + (x > 0)][ltn | (x < n)] += dp[i][j][ltn]
print(sum(dp[len(N)][K]))


import sys
import numpy as np
input = sys.stdin.readline

def solve(N, K, L):
	dp = np.zeros(shape=(L + 1, 2, K + 1), dtype=np.int64)
	dp[0][0][0] = 1
	for i in range(L):
		D = N[i]
		for j in range(2):
			d_max = 9 if j == 1 else D
			for k in range(K + 1):
				if k < K:
					for d in range(d_max + 1):
						dp[i + 1][int(j or d < D)][k + int(d > 0)] += dp[i][j][k]
				else:
					dp[i + 1][j][k] += dp[i][j][k]
	return dp[L][0][K] + dp[L][1][K]

def main():
	N = np.array(list(input().rstrip()), dtype=np.int64)
	K = int(input())
	L = N.shape[0]
	ans = solve(N, K, L)
	print(ans)

def __starting_point():
	main()
__starting_point()


n = str(input())
k = int(input())
m = len(n)
dp = [[[0, 0] for __ in range(k + 2)] for _ in range(m + 1)]
dp[0][0][0] = 1
for i in range(m):
	d = int(n[i])
	for j in range(k + 1):
		for s in range(2):
			for c in range(10):
				if not s and c > d:
					continue
				dp[i + 1][j + (c != 0)][s or c < d] += dp[i][j][s]
print(dp[m][k][0] + dp[m][k][1])


import math
n = int(input())
K = int(input())

def calk1(n):
	if n == 0:
		return 0
	m = int(math.log10(n))
	num = m * 9
	num += n // 10 ** m
	return num

def calk2(n):
	m = int(math.log10(n))
	num = m * (m - 1) // 2 * 9 ** 2
	num += (n // 10 ** m - 1) * m * 9
	num += calk1(n - n // 10 ** m * 10 ** m)
	return num

def calk3(n):
	m = int(math.log10(n))
	num = m * (m - 1) * (m - 2) // 6 * 9 ** 3
	num += (n // 10 ** m - 1) * (m * (m - 1) // 2 * 9 ** 2)
	num += calk2(n - n // 10 ** m * 10 ** m)
	return num
if n < 10 ** (K - 1):
	print(0)
elif K == 1:
	print(calk1(n))
elif K == 2:
	print(calk2(n))
else:
	print(calk3(n))


s = input()
n = len(s)
K = int(input())
dp = [[[0, 0] for _ in range(K + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
r = range
for i in r(n):
	nd = int(s[i])
	for j in r(K + 1):
		for k in r(2):
			for d in r(10):
				(ni, nj, nk) = (i + 1, j, k)
				if d:
					nj += 1
				if nj > K:
					continue
				if k < 1:
					if d > nd:
						continue
					if d < nd:
						nk = 1
				dp[ni][nj][nk] += dp[i][j][k]
print(dp[n][K][0] + dp[n][K][1])


from functools import lru_cache
n = int(input())
k = int(input())

@lru_cache(None)
def F(x, y):
	if x < 10:
		if y == 1:
			return x
		elif y == 0:
			return 1
		else:
			return 0
	else:
		res = 0
		(q, r) = divmod(x, 10)
		res += F(q, y)
		if y >= 1:
			res += r * F(q, y - 1)
			res += (9 - r) * F(q - 1, y - 1)
		return res
print(F(n, k))


N = input()
K = int(input())
l = len(N)
dp = [[[0] * (K + 2) for _ in range(2)] for _ in range(l + 1)]
dp[0][1][0] = 1
for (i, c) in enumerate(N):
	x = int(c)
	for j in range(2):
		for d in range(x + 1 if j == 1 else 10):
			for k in range(K + 1):
				dp[i + 1][x == d if j == 1 else 0][k + 1 if 0 < d else k] += dp[i][j][k]
print(dp[l][0][K] + dp[l][1][K])


import sys
import numpy as np
input = lambda : sys.stdin.readline().rstrip()
N = list(map(int, input()))
K = int(input())

def solve():
	dp_sm = np.zeros((len(N), K + 1), np.int64)
	dp_lg = np.zeros((len(N), K + 1), np.int64)
	dp_sm[0][0] = 1
	dp_sm[0][1] = N[0] - 1
	dp_lg[0][0] = 0
	dp_lg[0][1] = 1
	for i in range(len(N) - 1):
		for j in range(K + 1):
			dp_sm[i + 1][j] += dp_sm[i][j]
			if N[i + 1] != 0:
				dp_sm[i + 1][j] += dp_lg[i][j]
			if j < K:
				dp_sm[i + 1][j + 1] += dp_sm[i][j] * 9
			if j < K and N[i + 1] != 0:
				dp_sm[i + 1][j + 1] += dp_lg[i][j] * (N[i + 1] - 1)
				dp_lg[i + 1][j + 1] += dp_lg[i][j]
			if N[i + 1] == 0:
				dp_lg[i + 1][j] += dp_lg[i][j]
	print(dp_sm[len(N) - 1][K] + dp_lg[len(N) - 1][K])

def __starting_point():
	solve()
__starting_point()


N = input()
l = len(N)
K = int(input())
dp = [[[0 for i in range(4)] for i in range(2)] for i in range(l + 1)]
dp[0][0][0] = 1
for i in range(l):
	for smaller in range(2):
		for c in range(4):
			lim = 9 if smaller else int(N[i])
			for d in range(lim + 1):
				if c != 3:
					dp[i + 1][smaller or d < lim][c + (d != 0)] += dp[i][smaller][c]
				elif d == 0:
					dp[i + 1][smaller or d < lim][c] += dp[i][smaller][c]
print(dp[l][0][K] + dp[l][1][K])


import sys
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

@lru_cache(maxsize=None)
def solve(n, k):
	if n < 10:
		if k == 1:
			return n
		elif k == 0:
			return 1
		else:
			return 0
	(q, r) = divmod(n, 10)
	return solve(q, k) + solve(q, k - 1) * r + solve(q - 1, k - 1) * (9 - r)

def main():
	N = int(input())
	K = int(input())
	print(solve(N, K))
main()


from math import factorial
from itertools import product
S = input()
N = int(S)
m = len(S)
K = int(input())
product_K = product(['1', '2', '3', '4', '5', '6', '7', '8', '9'], repeat=K)
product_K = [int(''.join(x)) for x in product_K]
ans = len([x for x in product_K if x <= N])
if m > K:
	for i in range(1, m - K):
		ans += 9 ** K * factorial(i + K - 1) // factorial(i) // factorial(K - 1)
	zero_n = m - K
	non_zero_n = K
	for i in range(m):
		l = int(S[i])
		if l == 0:
			zero_n -= 1
			continue
		if i > 0 and zero_n > 0:
			ans += 9 ** non_zero_n * factorial(zero_n - 1 + non_zero_n) // factorial(zero_n - 1) // factorial(non_zero_n)
		non_zero_n -= 1
		ans += len([x for x in range(1, l)]) * 9 ** non_zero_n * factorial(zero_n + non_zero_n) // factorial(zero_n) // factorial(non_zero_n)
		if non_zero_n <= 0:
			ans += 1
			break
print(ans)


N = input()
K = int(input())
dp = [[[0] * 5 for _ in range(2)] for _ in range(len(N) + 1)]
dp[0][0][0] = 1
for i in range(len(N)):
	D = int(N[i])
	for j in range(2):
		for k in range(5):
			dMax = 9 if j else D
			for d in range(dMax + 1):
				dp[i + 1][j | (d < D)][min(4, k + (d != 0))] += dp[i][j][k]
ans1 = dp[len(N)][0][K]
ans2 = dp[len(N)][1][K]
print(ans1 + ans2)


n = input()
k = int(input())
len_n = len(n)
dp0 = [[0] * (k + 1) for _ in range(len_n + 1)]
dp1 = [[0] * (k + 1) for _ in range(len_n + 1)]
dp0[0][0] = 1
for (i, n_i) in enumerate(n):
	for k_i in range(k + 1):
		if n_i == '0':
			dp0[i + 1][k_i] += dp0[i][k_i]
			dp1[i + 1][k_i] += dp1[i][k_i]
			if k_i < k:
				dp1[i + 1][k_i + 1] += 9 * dp1[i][k_i]
		else:
			if k_i < k:
				dp0[i + 1][k_i + 1] += dp0[i][k_i]
				dp1[i + 1][k_i + 1] += (int(n_i) - 1) * dp0[i][k_i]
				dp1[i + 1][k_i + 1] += 9 * dp1[i][k_i]
			dp1[i + 1][k_i] += dp0[i][k_i]
			dp1[i + 1][k_i] += dp1[i][k_i]
print(dp0[-1][k] + dp1[-1][k])


(s, k) = (input(), int(input()))
n = [int(i) for i in s]
l = len(s)
dp = [[[0] * (k + 1), [0] * (k + 1)] for i in range(l + 1)]
dp[0][0][0] = 1
for i in range(l):
	for smaller in range(2):
		for x in range(10 if smaller else n[i] + 1):
			if x == 0:
				for y in range(k + 1):
					dp[i + 1][smaller or x < n[i]][y] += dp[i][smaller][y]
			else:
				for y in range(k):
					dp[i + 1][smaller or x < n[i]][y + 1] += dp[i][smaller][y]
print(dp[-1][0][-1] + dp[-1][1][-1])


import numpy as np
N = list(map(int, input()))
K = int(input())
l = len(N)
if l < K:
	print(0)
	return
dp_small = np.zeros((l + 1, K + 1), dtype=np.int64)
dp_large = np.zeros((l + 1, K + 1), dtype=np.int64)
dp_large[0, 0] = 1
for (d, digit) in enumerate(N, 1):
	for k in range(K + 1):
		dp_small[d, k] += dp_small[d - 1, k]
		if digit != 0:
			dp_small[d, k] += dp_large[d - 1, k]
			dp_large[d, k] = 0
		else:
			dp_large[d, k] = dp_large[d - 1, k]
		if k != 0:
			dp_small[d, k] += dp_small[d - 1, k - 1] * 9
			if digit >= 1:
				dp_small[d, k] += dp_large[d - 1, k - 1] * (digit - 1)
				dp_large[d, k] += dp_large[d - 1, k - 1]
print(dp_small[l, K] + dp_large[l, K])


n = input()
k = int(input())
m = len(n)
DP = [[[0] * (k + 1) for _ in range(2)] for _ in range(m + 1)]
DP[0][0][0] = 1
for i in range(1, m + 1):
	N = int(n[i - 1])
	for j in range(k + 1):
		DP[i][1][j] += DP[i - 1][1][j]
		if N != 0:
			DP[i][1][j] += DP[i - 1][0][j]
		else:
			DP[i][0][j] += DP[i - 1][0][j]
		if j != 0:
			DP[i][1][j] += 9 * DP[i - 1][1][j - 1]
			if N != 0:
				DP[i][0][j] += DP[i - 1][0][j - 1]
				DP[i][1][j] += (N - 1) * DP[i - 1][0][j - 1]
print(DP[m][0][k] + DP[m][1][k])


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)


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

def c(n, k):
	if n < k:
		return 0
	else:
		x = 1
		for i in range(k):
			x *= n - i
			x //= i + 1
		return x
ans = 0
for i in range(k):
	temp1 = len(str(n)) - 1
	temp2 = n // 10 ** temp1
	check = k - i
	if check == 1:
		ans += temp2 + temp1 * 9
	else:
		ans += c(temp1, check) * 9 ** check + (temp2 - 1) * c(temp1, check - 1) * 9 ** (check - 1)
	n %= 10 ** temp1
print(ans)


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

def f(n, d, k):
	if k == 0:
		return 1
	if d == 1:
		return int(n) if k == 1 else 0
	msb = int(n[0])
	if msb == 0:
		return f(n[1:], d - 1, k)
	return f(n[1:], d - 1, k - 1) + (msb - 1) * f('9' * (d - 1), d - 1, k - 1) + f('9' * (d - 1), d - 1, k)
print(f(N, len(N), K))


def main():
	n = list(input())
	k = int(input())
	N = len(n)
	for i in range(N):
		n[i] = int(n[i])
	dp1 = [[0 for _ in range(k + 1)] for _ in range(N + 1)]
	dp2 = [[0 for _ in range(k + 1)] for _ in range(N + 1)]
	dp1[0][0] = 1
	for i in range(N):
		for j in range(k + 1):
			dp2[i + 1][j] += dp2[i][j]
			if j < k:
				dp2[i + 1][j + 1] += dp2[i][j] * 9
			if n[i]:
				dp2[i + 1][j] += dp1[i][j]
				if j == k:
					continue
				dp1[i + 1][j + 1] += dp1[i][j]
				dp2[i + 1][j + 1] += dp1[i][j] * (n[i] - 1)
			else:
				dp1[i + 1][j] += dp1[i][j]
	print(dp1[N][k] + dp2[N][k])

def __starting_point():
	main()
__starting_point()


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

def run():
	dp = [[[0] * 4 for _ in range(2)] for _ in range(len(sN) + 1)]
	dp[0][0][0] = 1
	for i in range(len(sN)):
		for j in range(2):
			lim = 9 if j == 1 else ord(sN[i]) - ord('0')
			for k in range(lim + 1):
				for l in range(4):
					nl = l + int(k > 0)
					if nl >= 4:
						continue
					dp[i + 1][k < lim or j == 1][nl] += dp[i][j][l]
	print(dp[len(sN)][0][K] + dp[len(sN)][1][K])

def __starting_point():
	run()
__starting_point()


N = input()
K = int(input())
dp = [[[0] * len(N) for _ in range(K + 1)] for _ in range(2)]
dp[0][0][0] = 0
dp[1][0][0] = 1
dp[0][1][0] = 1
dp[1][1][0] = max(0, int(N[0]) - 1)
man_k = 1
for i in range(1, len(N)):
	n = N[i]
	is_nonzero = 1 if n != '0' else 0
	man_k += is_nonzero
	if man_k <= K:
		dp[0][man_k][i] = dp[0][man_k - is_nonzero][i - 1]
	dp[1][0][i] = dp[1][0][i - 1]
	for k in range(1, K + 1):
		dp[1][k][i] = dp[1][k][i - 1] + dp[1][k - 1][i - 1] * 9
		if n != '0':
			dp[1][k][i] += dp[0][k - 1][i - 1] * (int(n) - 1) + dp[0][k][i - 1]
print(dp[0][K][-1] + dp[1][K][-1])


s = input()
n = len(s)
k = int(input())
dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for a in range(n):
	for b in range(k + 1):
		for c in range(2):
			nd = int(s[a])
			for d in range(10):
				(na, nb, nc) = (a + 1, b, c)
				if d != 0:
					nb += 1
				if nb > k:
					break
				if 0 == nc:
					if d > nd:
						break
					if d < nd:
						nc += 1
				dp[na][nb][nc] += dp[a][b][c]
print(sum(dp[-1][-1]))


N = input()
K = int(input())
l = len(N)
dp = [[0] + [1] * l] + [[0] * (l + 1) for i in range(K)]
dp2 = [[1] + [0] * l] + [[0] * (l + 1) for i in range(K)]
for (i, n) in enumerate(N):
	n = int(n)
	for j in range(K):
		dp[j + 1][i + 1] = dp[j][i] * 9 + dp[j + 1][i] + (dp2[j][i] * (n - 1) + dp2[j + 1][i] if n > 0 else 0)
		dp2[j + 1][i + 1] = dp2[j][i] if n > 0 else dp2[j + 1][i]
print(dp[-1][-1] + dp2[-1][-1])


from sys import setrecursionlimit
setrecursionlimit(10 ** 7)
n = input()
k = int(input())
dp = {}

def rec(i, smaller, count):
	if (i, smaller, count) in dp:
		return dp[i, smaller, count]
	if i == len(n):
		if count == k:
			return 1
		else:
			return 0
	limit = 10
	if not smaller:
		limit = int(n[i]) + 1
	ret = 0
	for j in range(limit):
		if smaller or j < int(n[i]):
			if j == 0:
				ret += rec(i + 1, True, count)
			else:
				ret += rec(i + 1, True, count + 1)
		elif j == 0:
			ret += rec(i + 1, False, count)
		else:
			ret += rec(i + 1, False, count + 1)
	dp[i, smaller, count] = ret
	return ret
print(rec(0, False, 0))


from functools import lru_cache
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(N, K) = map(int, read().split())

@lru_cache(None)
def F(N, K):
	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))


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


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache

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

def INT():
	return int(input())

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

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

def TUPLE():
	return tuple(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
N = list(map(int, list(input())))
K = INT()
n = len(N)
if n < K:
	print(0)
	return
dp = [[[0, 0] for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
	for j in range(n):
		for k in range(2):
			for x in range(10):
				(ni, nj, nk) = (i + 1, j, k)
				if x != 0:
					nj += 1
				if k == 0:
					if N[i] < x:
						continue
					elif x < N[i]:
						nk = 1
				dp[ni][nj][nk] += dp[i][j][k]
ans = 0
print(dp[n][K][0] + dp[n][K][1])


N = str(input())
n = len(N)
K = int(input())
dp0 = [[0] * (K + 1) for _ in range(n + 1)]
dp1 = [[0] * (K + 1) for _ in range(n + 1)]
for l in range(1, n + 1):
	dp0[l][0] = 1
dp1[0][0] = 1
for i in range(n):
	for j in range(K):
		if N[i] == '0':
			dp0[i + 1][j + 1] = 9 * dp0[i][j] + dp0[i][j + 1]
			dp1[i + 1][j + 1] = dp1[i][j + 1]
		else:
			dp0[i + 1][j + 1] = dp0[i][j] * 9 + dp0[i][j + 1] + dp1[i][j] * (int(N[i]) - 1) + dp1[i][j + 1]
			dp1[i + 1][j + 1] = dp1[i][j]
print(dp0[n][K] + dp1[n][K])


n = input()
kk = int(input())
l = len(n)
dp = [[[0] * 2 for _ in range(101)] for _ in range(l + 1)]
dp[0][0][0] = 1
for (i, dig) in enumerate(n):
	dig = int(dig)
	for j in range(10):
		for k in range(100):
			nk = k if j == 0 else k + 1
			if j < dig:
				dp[i + 1][nk][1] += dp[i][k][0] + dp[i][k][1]
			elif j == dig:
				dp[i + 1][nk][1] += dp[i][k][1]
				dp[i + 1][nk][0] += dp[i][k][0]
			else:
				dp[i + 1][nk][1] += dp[i][k][1]
print(dp[l][kk][0] + dp[l][kk][1])


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

def dp(n, k):
	if k == 0:
		return 1
	elif n == 0:
		return 0
	else:
		n = int(n)
		s = str(n)
		digit = len(s)
		(m, fdigit) = divmod(n, 10)
		if m >= 1:
			return int(dp(m, k - 1) * fdigit + dp(m - 1, k - 1) * (9 - fdigit) + dp(m, k))
		elif k == 1:
			return n
		elif k == 2 or k == 3:
			return 0
		else:
			return 1
if K == 0:
	answer = dp(N, K) - 1
else:
	answer = dp(N, K)
print(int(answer))


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

def search(d, k, isLess):
	if k == K:
		return 1
	if d == len(N):
		return 0
	ret = search(d + 1, k, isLess or int(N[d]) > 0)
	if k < K:
		if isLess:
			ret += search(d + 1, k + 1, True) * 9
		elif int(N[d]) > 0:
			ret += search(d + 1, k + 1, True) * (int(N[d]) - 1) + search(d + 1, k + 1, False)
	return ret
ans = search(0, 0, False)
print(ans)


n = input()
k = int(input())
dp0 = [[0] * 5 for i in range(len(n) + 1)]
dp1 = [[0] * 5 for i in range(len(n) + 1)]
dp0[0][0] = 1
for i in range(1, len(n) + 1):
	nn = int(n[i - 1])
	for j in range(4):
		dp0[i][j] += dp0[i - 1][j] * (nn == 0)
		dp1[i][j] += dp1[i - 1][j] + dp0[i - 1][j] * (nn != 0)
		dp0[i][j + 1] += dp0[i - 1][j] * (nn != 0)
		dp1[i][j + 1] += dp1[i - 1][j] * 9 + dp0[i - 1][j] * (nn - 1) * (nn != 0)
print(dp0[len(n)][k] + dp1[len(n)][k])


S = input()
N = len(S)
K = int(input())
dp = [[[0 for _ in range(5)] for _ in range(2)] for _ in range(N + 5)]
dp[1][0][1] = 1
dp[1][1][0] = 1
dp[1][1][1] = int(S[0]) - 1
for i in range(1, N):
	n = int(S[i])
	ok = 0 if n == 0 else 1
	for j in range(4):
		dp[i + 1][0][j + ok] += dp[i][0][j]
		if n > 0:
			dp[i + 1][1][j] += dp[i][0][j]
			dp[i + 1][1][j + 1] += (n - 1) * dp[i][0][j]
		dp[i + 1][1][j] += dp[i][1][j]
		dp[i + 1][1][j + 1] += 9 * dp[i][1][j]
print(dp[N][0][K] + dp[N][1][K])