output_description: Print the count.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      K
attempt: ## ABC154E
  
  import sys
  
  input = lambda: sys.stdin.readline().rstrip()
  sys.setrecursionlimit(max(1000, 10**9))
  write = lambda x: sys.stdout.write(x + "\n")
  
  
  M = 10**9 + 7  # 出力の制限
  N = 100  # 必要なテーブルサイズ
  
  
  def cmb(n, r, M):
      if r < 0 or r > n:
          return 0
      r = min(r, n - r)
      return (g1[n] * g2[r] * g2[n - r]) % M
  
  
  g1 = [None] * (N + 1)  # 元テーブル
  g2 = [None] * (N + 1)  # 逆元テーブル
  inverse = [None] * (N + 1)  # 逆元テーブル計算用テーブル
  g1[0] = g1[1] = g2[0] = g2[1] = 1
  inverse[0], inverse[1] = [0, 1]
  
  for i in range(2, N + 1):
      g1[i] = (g1[i - 1] * i) % M
      inverse[i] = (
          -inverse[M % i] * (M // i)
      ) % M  # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
      g2[i] = (g2[i - 1] * inverse[i]) % M
  
  
  n = input()
  k = int(input())
  l = len(n)
  
  dp0 = [[0] * (k + 1) for _ in range(l + 1)]  # i桁目まででNより小さく、非零がjの個数
  dp1 = [[0] * (k + 1) for _ in range(l + 1)]  # i桁目でNと同じで、非零がjの個数
  dp1[0][0] = 1
  
  if k > l:
      ans = 0
  else:
      for i in range(1, l + 1):
          for j in range(k + 1):
              c = int(n[i - 1])
              if j >= 1:
                  dp0[i][j] += 9 * dp0[i - 1][j - 1]
              dp0[i][j] += dp0[i - 1][j]
              if c >= 1:
                  dp0[i][j] += dp1[i - 1][j]
                  if j >= 1:
                      dp0[i][j] += (c - 1) * dp1[i - 1][j - 1]
  
              if c == 0:
                  dp1[i][j] += dp1[i - 1][j]
              elif j >= 1:
                  dp1[i][j] += dp1[i - 1][j - 1]
  
  ans = dp0[l][k] + dp1[l][k]
  print(ans)
  
problem_description: Statement
  
  Find the number of integers between 1 and N (inclusive) that contains exactly
  K non-zero digits when written in base ten.
samples: [{"input": "100\n    1", "output": "19\n    \n\nThe following 19 integers satisfy the condition:\n\n  * 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90,100\n\n* * *"}, {"input": "25\n    2", "output": "14\n    \n\nThe following 14 integers satisfy the condition:\n\n  * 11,12,13,14,15,16,17,18,19,21,22,23,24,25\n\n* * *"}, {"input": "314159\n    2", "output": "937\n    \n\n* * *"}, {"input": "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999\n    3", "output": "117879300"}]