open System
open System.Collections.Generic 
 
let recip =
  let cache = Dictionary<_, _>()
  fun n m ->
      if cache.ContainsKey( (n, m) ) then cache.[ (n, m) ]
      else 
        let res = List.find (fun a -> n * a % m = 1) [1..n]
        cache.[ (n, m) ] <- res
        res
 
let rec binomialMod n k m =
  if k = 1 then n % m
  else 
    let prev = binomialMod (n - 1) (k - 1) m
    prev * n * (recip k m) % m
 
System.Console.WriteLine (recip 5 1007)
 

b3BlbiBTeXN0ZW0Kb3BlbiBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYyAKIApsZXQgcmVjaXAgPQogIGxldCBjYWNoZSA9IERpY3Rpb25hcnk8XywgXz4oKQogIGZ1biBuIG0gLT4KICAgICAgaWYgY2FjaGUuQ29udGFpbnNLZXkoIChuLCBtKSApIHRoZW4gY2FjaGUuWyAobiwgbSkgXQogICAgICBlbHNlIAogICAgICAgIGxldCByZXMgPSBMaXN0LmZpbmQgKGZ1biBhIC0+IG4gKiBhICUgbSA9IDEpIFsxLi5uXQogICAgICAgIGNhY2hlLlsgKG4sIG0pIF0gPC0gcmVzCiAgICAgICAgcmVzCiAgICAgICAgCmxldCByZWMgYmlub21pYWxNb2QgbiBrIG0gPQogIGlmIGsgPSAxIHRoZW4gbiAlIG0KICBlbHNlIAogICAgbGV0IHByZXYgPSBiaW5vbWlhbE1vZCAobiAtIDEpIChrIC0gMSkgbQogICAgcHJldiAqIG4gKiAocmVjaXAgayBtKSAlIG0KICAgIApTeXN0ZW0uQ29uc29sZS5Xcml0ZUxpbmUgKHJlY2lwIDUgMTAwNykK

MQoyCjEwCjQyCjExCg==

1
2
10
42
11