output_description: Print the count.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      K
attempt: n = input()
  k = int(input())
  # nより小さいことが確定しているdp
  # dp_0[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数
  dp_0 = [[0 for i in range(k + 1)] for j in range(len(n))]
  # nより小さいことが確定していないdp
  # dp_1[i][j] := i桁目まで決めて、0でない数字をj個使った時の数字の個数。
  dp_1 = [[0 for i in range(k + 1)] for j in range(len(n))]
  dp_0[0][0] = 1
  dp_0[0][1] = int(n[0]) - 1
  dp_1[0][1] = 1
  for i in range(1, len(n)):
      dp_0[i][0] = 1
      for j in range(1, k + 1):
          # 今回の桁が0でないことを想定
          if n[i] != "0":
              # 0を使う場合と使わない場合両方考える
              # まずは使わない場合
              dp_0[i][j] = (
                  dp_0[i - 1][j - 1] * 9
                  + dp_1[i - 1][j - 1] * (int(n[i]) - 1)
                  + dp_0[i - 1][j]
                  + dp_1[i - 1][j]
              )
              dp_1[i][j] = dp_1[i - 1][j - 1]
              # 0を使う場合。この時はjが変化しない。なぜなら0を使うか
              # dp_1の更新は無し。
              # なぜなら、今回の桁が0でないことを想定しているため、もうnを超えることはないから
          else:
              # 今回の桁が0の場合
              # dp_1を遷移式に入れない理由は、今回の桁が0だった時は、どんな数字の選び方をしても
              # さっきの桁まででnより小さいことが確定しないものが
              # 今回の桁の決め方で確定することはないから。
              dp_0[i][j] = dp_0[i - 1][j - 1] * 9 + dp_0[i - 1][j]
              dp_1[i][j] = dp_1[i - 1][j]
  # print(dp_0)
  # print(dp_1)
  print(dp_0[-1][k] + dp_1[-1][k])
  
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"}]