let split_string ?(pattern="") = Str.split @@ Str.regexp pattern
let n = read_line () |> split_string |> List.map int_of_string |> Array.of_list
let k = Scanf.sscanf (read_line ()) "%d" @@ fun k -> k

let len = Array.length n

let m_1e9 = int_of_float 1e9 + 7
let ( +^ ) x y = (x + y) mod m_1e9
let ( -^ ) x y = x - y + if x < y then m_1e9 else 0
let ( *^ ) x y = ((x mod m_1e9) * (y mod m_1e9)) mod m_1e9

let rec mod_pow x n =
  if n = 0 then 1
  else let t = mod_pow x (n / 2) in t *^ t *^ if n mod 2 = 0 then 1 else x

let nPr n r = Array.(init r ((-) n) |> fold_left ( *^ ) 1)

let nCr n r = nPr n r *^ mod_pow (nPr r r) (m_1e9 - 2)

let rec loop i k smaller =
  if i = len then
    if k = 0 then 1 else 0
  else if k = 0 then 
    1
  else if smaller then
    nCr (len - i) k * mod_pow 9 k
  else if n.(i) = 0 then
    loop (i + 1) k false
  else
    (loop (i + 1) k true) + 
    (loop (i + 1) (k - 1) true * (n.(i) - 1)) +
    (loop (i + 1) (k - 1) false)

let () = Printf.printf "%d\n" @@ loop 0 k false