let f m n =
  let append x y = Big_int.(add_int_big_int y (mult_int_big_int 10 x)) in
  let zero = Big_int.zero_big_int in
  let one = Big_int.unit_big_int in
  let add = Big_int.add_big_int in
  let le = Big_int.le_big_int in
  let lt = Big_int.lt_big_int in
  let cc = Array.make_matrix (m + 1) (m + 1) zero in
  let rec count_permutations s w =
    if s < 1 || w < 1 || s < w || w * 5 < s then
      zero
    else if s <= 5 && w = 1 then
      one
    else if lt zero cc.(s).(w) then
      cc.(s).(w)
    else
      let f = fun c d -> add c (count_permutations (s - d) (w - 1)) in
      let () = cc.(s).(w) <- List.fold_left f zero [1; 2; 3; 4; 5] in cc.(s).(w)
  in
  let rec aux acc b s w =
    let rec loop b d =
      if 5 < d then
        zero
      else
        let c = count_permutations (s - d) (w - 1) in
        let bc = add b c in
        if le n bc then
          aux (append acc d) b (s - d) (w - 1)
        else
          loop bc (d + 1)
    in
    if s < 1 || w < 1 then
      acc
    else if w = 1 then
      append acc s
    else
      loop b 1
  in
  let rec loop b w =
    if m < w then
      zero
    else
      let c = count_permutations m w in
      let bc = add b c in
      if le n bc then
        aux zero b m w
      else
        loop bc (w + 1)
  in
  if m < 1 || lt n one then
    zero
  else
    loop zero 1
(*
let g m n =
  Printf.printf "(%d,%s) → %s\n" m n Big_int.(string_of_big_int (f m (big_int_of_string n)))
let () =
  g (-1) "1";
  g 1 "-1";
  g (-1) "-1";
  g 2 "1";
  g 2 "2";
  g 2 "3";
  g 20 "1";
  g 20 "2";
  g 20 "3";
  g 20 "400096";
  g 20 "400097";
  g 32 "1";
  g 32 "2";
  g 32 "3";
  g 32 "1000";
  g 32 "1000000";
  g 32 "1000000000";
  g 32 "1333610936";
  g 32 "1333610937"
*)
let g m n =
  Printf.printf "(%d,%s) → %s\n" m (Big_int.string_of_big_int n) Big_int.(string_of_big_int (f m n))
let () =
  g 2000 Big_int.(shift_left_big_int unit_big_int 1024)
 

bGV0IGYgbSBuID0KICBsZXQgYXBwZW5kIHggeSA9IEJpZ19pbnQuKGFkZF9pbnRfYmlnX2ludCB5IChtdWx0X2ludF9iaWdfaW50IDEwIHgpKSBpbgogIGxldCB6ZXJvID0gQmlnX2ludC56ZXJvX2JpZ19pbnQgaW4KICBsZXQgb25lID0gQmlnX2ludC51bml0X2JpZ19pbnQgaW4KICBsZXQgYWRkID0gQmlnX2ludC5hZGRfYmlnX2ludCBpbgogIGxldCBsZSA9IEJpZ19pbnQubGVfYmlnX2ludCBpbgogIGxldCBsdCA9IEJpZ19pbnQubHRfYmlnX2ludCBpbgogIGxldCBjYyA9IEFycmF5Lm1ha2VfbWF0cml4IChtICsgMSkgKG0gKyAxKSB6ZXJvIGluCiAgbGV0IHJlYyBjb3VudF9wZXJtdXRhdGlvbnMgcyB3ID0KICAgIGlmIHMgPCAxIHx8IHcgPCAxIHx8IHMgPCB3IHx8IHcgKiA1IDwgcyB0aGVuCiAgICAgIHplcm8KICAgIGVsc2UgaWYgcyA8PSA1ICYmIHcgPSAxIHRoZW4KICAgICAgb25lCiAgICBlbHNlIGlmIGx0IHplcm8gY2MuKHMpLih3KSB0aGVuCiAgICAgIGNjLihzKS4odykKICAgIGVsc2UKICAgICAgbGV0IGYgPSBmdW4gYyBkIC0+IGFkZCBjIChjb3VudF9wZXJtdXRhdGlvbnMgKHMgLSBkKSAodyAtIDEpKSBpbgogICAgICBsZXQgKCkgPSBjYy4ocykuKHcpIDwtIExpc3QuZm9sZF9sZWZ0IGYgemVybyBbMTsgMjsgMzsgNDsgNV0gaW4gY2MuKHMpLih3KQogIGluCiAgbGV0IHJlYyBhdXggYWNjIGIgcyB3ID0KICAgIGxldCByZWMgbG9vcCBiIGQgPQogICAgICBpZiA1IDwgZCB0aGVuCiAgICAgICAgemVybwogICAgICBlbHNlCiAgICAgICAgbGV0IGMgPSBjb3VudF9wZXJtdXRhdGlvbnMgKHMgLSBkKSAodyAtIDEpIGluCiAgICAgICAgbGV0IGJjID0gYWRkIGIgYyBpbgogICAgICAgIGlmIGxlIG4gYmMgdGhlbgogICAgICAgICAgYXV4IChhcHBlbmQgYWNjIGQpIGIgKHMgLSBkKSAodyAtIDEpCiAgICAgICAgZWxzZQogICAgICAgICAgbG9vcCBiYyAoZCArIDEpCiAgICBpbgogICAgaWYgcyA8IDEgfHwgdyA8IDEgdGhlbgogICAgICBhY2MKICAgIGVsc2UgaWYgdyA9IDEgdGhlbgogICAgICBhcHBlbmQgYWNjIHMKICAgIGVsc2UKICAgICAgbG9vcCBiIDEKICBpbgogIGxldCByZWMgbG9vcCBiIHcgPQogICAgaWYgbSA8IHcgdGhlbgogICAgICB6ZXJvCiAgICBlbHNlCiAgICAgIGxldCBjID0gY291bnRfcGVybXV0YXRpb25zIG0gdyBpbgogICAgICBsZXQgYmMgPSBhZGQgYiBjIGluCiAgICAgIGlmIGxlIG4gYmMgdGhlbgogICAgICAgIGF1eCB6ZXJvIGIgbSB3CiAgICAgIGVsc2UKICAgICAgICBsb29wIGJjICh3ICsgMSkKICBpbgogIGlmIG0gPCAxIHx8IGx0IG4gb25lIHRoZW4KICAgIHplcm8KICBlbHNlCiAgICBsb29wIHplcm8gMQooKgpsZXQgZyBtIG4gPQogIFByaW50Zi5wcmludGYgIiglZCwlcykg4oaSICVzXG4iIG0gbiBCaWdfaW50LihzdHJpbmdfb2ZfYmlnX2ludCAoZiBtIChiaWdfaW50X29mX3N0cmluZyBuKSkpCmxldCAoKSA9CiAgZyAoLTEpICIxIjsKICBnIDEgIi0xIjsKICBnICgtMSkgIi0xIjsKICBnIDIgIjEiOwogIGcgMiAiMiI7CiAgZyAyICIzIjsKICBnIDIwICIxIjsKICBnIDIwICIyIjsKICBnIDIwICIzIjsKICBnIDIwICI0MDAwOTYiOwogIGcgMjAgIjQwMDA5NyI7CiAgZyAzMiAiMSI7CiAgZyAzMiAiMiI7CiAgZyAzMiAiMyI7CiAgZyAzMiAiMTAwMCI7CiAgZyAzMiAiMTAwMDAwMCI7CiAgZyAzMiAiMTAwMDAwMDAwMCI7CiAgZyAzMiAiMTMzMzYxMDkzNiI7CiAgZyAzMiAiMTMzMzYxMDkzNyIKKikKbGV0IGcgbSBuID0KICBQcmludGYucHJpbnRmICIoJWQsJXMpIOKGkiAlc1xuIiBtIChCaWdfaW50LnN0cmluZ19vZl9iaWdfaW50IG4pIEJpZ19pbnQuKHN0cmluZ19vZl9iaWdfaW50IChmIG0gbikpCmxldCAoKSA9CiAgZyAyMDAwIEJpZ19pbnQuKHNoaWZ0X2xlZnRfYmlnX2ludCB1bml0X2JpZ19pbnQgMTAyNCkK