output_description: Print the count.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      K
attempt: from collections import defaultdict as dd
  
  N = int(input())
  K = int(input())
  
  s = str(N)
  
  dp = dd(int)
  dp[(True, 1)] = 1
  dp[(False, 1)] = int(s[0]) - 1
  dp[(False, 0)] = 1
  
  for c in s[1:]:
      i = int(c)
      ndp = {}
      if i != 0:
          ndp[(True, 0)] = 0
          ndp[(True, 1)] = dp[(True, 0)]
          ndp[(True, 2)] = dp[(True, 1)]
          ndp[(True, 3)] = dp[(True, 2)]
          ndp[(False, 0)] = dp[(False, 0)] + dp[(True, 0)]
          ndp[(False, 1)] = (
              dp[(False, 1)]
              + dp[(False, 0)] * 9
              + dp[(True, 0)] * (i - 1)
              + dp[(True, 1)]
          )
          ndp[(False, 2)] = (
              dp[(False, 2)]
              + dp[(False, 1)] * 9
              + dp[(True, 1)] * (i - 1)
              + dp[(True, 2)]
          )
          ndp[(False, 3)] = (
              dp[(False, 3)]
              + dp[(False, 2)] * 9
              + dp[(True, 2)] * (i - 1)
              + dp[(True, 3)]
          )
      else:
          ndp[(True, 0)] = dp[(True, 0)]
          ndp[(True, 1)] = dp[(True, 1)]
          ndp[(True, 2)] = dp[(True, 2)]
          ndp[(True, 3)] = dp[(True, 3)]
          ndp[(False, 0)] = dp[(False, 0)]
          ndp[(False, 1)] = dp[(False, 1)] + dp[(False, 0)] * 9
          ndp[(False, 2)] = dp[(False, 2)] + dp[(False, 1)] * 9
          ndp[(False, 3)] = dp[(False, 3)] + dp[(False, 2)] * 9
      dp = ndp
  print(dp[True, K] + dp[False, 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"}]