(*
 * We have a set S of numbers q.  Let s(q) be the sum of the digits of q.
 * We keep track of counts of triples of this form (i,j,k) where
 * s(q) = i and q mod k = j. 
 *)

let lucky n =
  let rec sdigits n = if n=0 then 0 else (n mod 10) + (sdigits (n/10)) in
  let rec list_of_int n accum = if n=0 then accum else list_of_int (n/10) ((n mod 10)::accum) in
  let digits = list_of_int n [] in
  let maxs = 9*(List.length digits) in  (* for simplicity make all the dimensions equal, maxs+1 *)

  let make_array () = 
    let c = Array.make (maxs+1) (Array.make 0 (Array.make 0 0 )) in
      for i=0 to maxs do 
	c.(i) <- Array.make (maxs+1) (Array.make 0 0 );
	for j=0 to maxs do
	  c.(i).(j) <- Array.make (maxs+1) 0
	done
      done;
      c
  in
    
  (* takes the array c, and augments it by adding the number d to the totals *)
  let add_d c d =
    let sum = sdigits d in
      for k=1 to maxs do
	c.(sum).(d mod k).(k) <- c.(sum).(d mod k).(k) + 1;
      done
  in

  (* takes the array c, augments it by adding in the contributions for numbers a ... b *)
  let add_a_to_b c a b = 
    for i=a to b do add_d c i done
  in

  (* takes an array c and computes and returns a new array representing 10 times the range of the old one *)
  let multiply_by_10 c = 
    (* c represents some interval [1,k-1] *)
    let nc = make_array () in
      for d=0 to 9 do
	for i=1 to maxs-d do for j=0 to maxs do for k=1 to maxs do
	  let a = nc.(i+d).((10*j+d) mod k) in
	    a.(k) <- a.(k) + c.(i).(j).(k)
	done done done;
      done;
      (* now nc represents some interval [10,10k-1] *)
      add_a_to_b nc 1 9;
      (* now nc represents some interval [1,10k-1] *)
      nc
  in
    
  let rec print_digits digits = 
    match digits with [] -> Printf.printf "\n" | d::tail -> Printf.printf "%d " d; print_digits tail
  in
   
  let rec loop c digits ub = 
    (* got 1 to ub-1 in the array, and the digits to process are in the list digits *)
    match digits with 
	[] -> 
	  add_d c n; 
	  let rec sum k accum = if k=maxs+1 then accum else sum (k+1) (accum + c.(k).(0).(k)) in
	    sum 1 0

      | d::tail ->
	  let nc = multiply_by_10 c in  (* now we have [1, 10ub-1] *)
	    add_a_to_b nc (10*ub) (10*ub+d-1);
	    loop nc tail (10*ub+d)
  in

  let first = List.hd digits in
  let rest = List.tl digits in
  let c = make_array () in
    add_a_to_b c 1 (first-1);     (*  [1, d-1]   *)
    loop c rest first

let read_int () = Scanf.bscanf Scanf.Scanning.stdib " %d " (fun x -> x)
;; 
Printf.printf "%d\n" (lucky (read_int()));