{-# LANGUAGE BangPatterns #-}

module Main
  ( main
  )
where

import           Control.Applicative
import           Control.Monad
import           Data.Bits
import qualified Data.ByteString.Char8         as BS
import           Data.Char
import           Data.List
import           Data.Maybe
import qualified Data.Vector                   as V
import qualified Data.Vector.Mutable           as MV
import           Control.Monad.ST
import           Data.Ord
import qualified Data.Vector.Unboxed           as UV

parse = fst . fromJust
parseInt = parse . BS.readInt
parseInteger = parse . BS.readInteger
readInt = parseInt <$> BS.getLine
readInteger = parseInteger <$> BS.getLine
readIntList = map parseInt . BS.words <$> BS.getLine
readIntegerList = map parseInteger . BS.words <$> BS.getLine

main = do
  digits <- UV.fromList . map digitToInt <$> getLine
  k      <- readInt
  let d      = UV.length digits
      cumsum = UV.tail
        $ UV.scanl' (\acc val -> if val /= 0 then acc + 1 else acc) 0 digits
      matched = if (UV.length . UV.filter (/= 0) $ digits) == k then 1 else 0
      lowerDigit =
        sum . map (\val -> combi (val - 1) (k - 1) * (9 ^ k)) $ [1 .. (d - 1)]
      topDigit = (UV.head digits - 1) * combi (d - 1) (k - 1) * 9 ^ (k - 1)
      zeroDigit =
        sum
          . map
              (\i ->
                combi (d - i - 1) (k - cumsum UV.! (i - 1))
                  * 9
                  ^ (k - cumsum UV.! (i - 1))
              )
          . filter
              (\i -> (digits UV.! i /= 0) && (k - cumsum UV.! (i - 1) >= 0))
          $ [1 .. (d - 1)]
      equalDigit =
        sum
          . map
              (\i ->
                max (digits UV.! i - 1) 0
                  * combi (d - i - 1) (k - cumsum UV.! i)
                  * 9
                  ^ (k - cumsum UV.! i)
              )
          . filter (\i -> (digits UV.! i /= 0) && (k - cumsum UV.! i >= 0))
          $ [1 .. (d - 1)]
  print $ matched + lowerDigit + topDigit + zeroDigit + equalDigit

combi n k
  | n < 0 || k < 0   = 0
  | n < k            = 0
  | n == 0 || k == 0 = 1
  | otherwise = foldl' (*) 1 [(n - k + 1) .. n] `div` foldl' (*) 1 [1 .. k]
