open System
open System.Collections.Generic 
 
let recip =
  let cache = Dictionary<_, _>()
  fun n m ->
      assert (isPrime n)
      if cache.ContainsKey( (n, m) ) then cache.[ (n, m) ]
      else 
        let res = List.find (fun a -> n * a % m = 1) [1..(m - 1)]
        cache.[ (n, m) ] <- res
        res
 
let rec binomialMod n k m  =
  let rec recBinomialMod n k m result =
    if k = 1 then n * result % m 
    else 
      let k_1 = recip k m
      recBinomialMod (n - 1) (k - 1) m (result * n * k_1 % m)      
  recBinomialMod n k m 1
 
let isPrime n =
  List.exists (fun i -> n % i = 0) [2..(n - 1)]
 
let primes = List.filter isPrime [1000..5000]
let binomials = List.map (fun m -> binomialMod (int (1000000000000L % (int64 m))) 1000000000 m) primes
 
let solution =
  let rec recSolution (binomials:(int list)) product chosen =
    seq {      
      if chosen = 3 then yield product
      else if binomials.IsEmpty then yield 0 
      else
        yield! recSolution binomials.Tail product chosen
        yield! recSolution binomials.Tail (product * binomials.Head) (chosen + 1)
    }
  (Seq.sum (recSolution binomials 1 0))
 
Console.WriteLine solution

b3BlbiBTeXN0ZW0Kb3BlbiBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYyAKIApsZXQgcmVjaXAgPQogIGxldCBjYWNoZSA9IERpY3Rpb25hcnk8XywgXz4oKQogIGZ1biBuIG0gLT4KICAgICAgYXNzZXJ0IChpc1ByaW1lIG4pCiAgICAgIGlmIGNhY2hlLkNvbnRhaW5zS2V5KCAobiwgbSkgKSB0aGVuIGNhY2hlLlsgKG4sIG0pIF0KICAgICAgZWxzZSAKICAgICAgICBsZXQgcmVzID0gTGlzdC5maW5kIChmdW4gYSAtPiBuICogYSAlIG0gPSAxKSBbMS4uKG0gLSAxKV0KICAgICAgICBjYWNoZS5bIChuLCBtKSBdIDwtIHJlcwogICAgICAgIHJlcwogICAgICAgIApsZXQgcmVjIGJpbm9taWFsTW9kIG4gayBtICA9CiAgbGV0IHJlYyByZWNCaW5vbWlhbE1vZCBuIGsgbSByZXN1bHQgPQogICAgaWYgayA9IDEgdGhlbiBuICogcmVzdWx0ICUgbSAKICAgIGVsc2UgCiAgICAgIGxldCBrXzEgPSByZWNpcCBrIG0KICAgICAgcmVjQmlub21pYWxNb2QgKG4gLSAxKSAoayAtIDEpIG0gKHJlc3VsdCAqIG4gKiBrXzEgJSBtKSAgICAgIAogIHJlY0Jpbm9taWFsTW9kIG4gayBtIDEKICAKbGV0IGlzUHJpbWUgbiA9CiAgTGlzdC5leGlzdHMgKGZ1biBpIC0+IG4gJSBpID0gMCkgWzIuLihuIC0gMSldCiAgICAKbGV0IHByaW1lcyA9IExpc3QuZmlsdGVyIGlzUHJpbWUgWzEwMDAuLjUwMDBdCmxldCBiaW5vbWlhbHMgPSBMaXN0Lm1hcCAoZnVuIG0gLT4gYmlub21pYWxNb2QgKGludCAoMTAwMDAwMDAwMDAwMEwgJSAoaW50NjQgbSkpKSAxMDAwMDAwMDAwIG0pIHByaW1lcwoKbGV0IHNvbHV0aW9uID0KICBsZXQgcmVjIHJlY1NvbHV0aW9uIChiaW5vbWlhbHM6KGludCBsaXN0KSkgcHJvZHVjdCBjaG9zZW4gPQogICAgc2VxIHsgICAgICAKICAgICAgaWYgY2hvc2VuID0gMyB0aGVuIHlpZWxkIHByb2R1Y3QKICAgICAgZWxzZSBpZiBiaW5vbWlhbHMuSXNFbXB0eSB0aGVuIHlpZWxkIDAgCiAgICAgIGVsc2UKICAgICAgICB5aWVsZCEgcmVjU29sdXRpb24gYmlub21pYWxzLlRhaWwgcHJvZHVjdCBjaG9zZW4KICAgICAgICB5aWVsZCEgcmVjU29sdXRpb24gYmlub21pYWxzLlRhaWwgKHByb2R1Y3QgKiBiaW5vbWlhbHMuSGVhZCkgKGNob3NlbiArIDEpCiAgICB9CiAgKFNlcS5zdW0gKHJlY1NvbHV0aW9uIGJpbm9taWFscyAxIDApKQogIApDb25zb2xlLldyaXRlTGluZSBzb2x1dGlvbg==

MQoyCjEwCjQyCjExCg==

1
2
10
42
11