output_description: Print the count.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      K
attempt: import sys
  
  sr = lambda: sys.stdin.readline().rstrip()
  ir = lambda: int(sr())
  lr = lambda: list(map(int, sr().split()))
  
  N = sr()
  K = ir()
  length = len(N)
  top = int(N[0])
  dp_dec = [[0] * 4 for _ in range(length)]  # decided
  dp_pen = [[0] * 4 for _ in range(length)]  # pending
  dp_dec[0][1] = top - 1
  dp_dec[0][0] = 1
  dp_pen[0][1] = 1
  for i in range(1, length):
      cur = int(N[i])
      if cur == 0:
          dp_pen[i] = dp_pen[i - 1][:]  # 右端に0
      else:
          for k in range(1, 4):
              dp_pen[i][k] = dp_pen[i - 1][k - 1]  # 右端にcur
  
      dp_dec[i] = dp_dec[i - 1][:]  # 0が右端に加わった場合
      for j in range(1, 4):
          dp_dec[i][j] += dp_dec[i - 1][j - 1] * 9  # 1~9が右端に加わった場合
          if cur > 0:
              dp_dec[i][j] += (
                  dp_pen[i - 1][j - 1] * (cur - 1) + dp_pen[i - 1][j] * 1
              )  # 右端にcur以下の数が加わった場合と0が加わった場合
  
  answer = dp_dec[length - 1][K] + dp_pen[length - 1][K]
  print(answer)
  
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"}]