title: Fast n choose k mod p for large n?
body: <p>What I mean by "large n" is something in the millions. p is prime.</p>
  
  <p>I've tried
  <a href="http://apps.topcoder.com/wiki/display/tc/SRM+467">http://apps.topcoder.com/wiki/display/tc/SRM+467</a>
  But the function seems to be incorrect (I tested it with 144 choose 6 mod 5 and it gives me 0 when it should give me 2)</p>
  
  <p>I've tried
  <a href="http://online-judge.uva.es/board/viewtopic.php?f=22&amp;t=42690">http://online-judge.uva.es/board/viewtopic.php?f=22&amp;t=42690</a>
  But I don't understand it fully</p>
  
  <p>I've also made a memoized recursive function that uses the logic (combinations(n-1, k-1, p)%p + combinations(n-1, k, p)%p) but it gives me stack overflow problems because n is large</p>
  
  <p>I've tried Lucas Theorem but it appears to be either slow or inaccurate.</p>
  
  <p>All I'm trying to do is create a fast/accurate n choose k mod p for large n. If anyone could help show me a good implementation for this I'd be very grateful. Thanks.</p>
  
  <p>As requested, the memoized version that hits stack overflows for large n:</p>
  
  <pre><code>std::map&lt;std::pair&lt;long long, long long&gt;, long long&gt; memo;
  
  long long combinations(long long n, long long k, long long p){
     if (n  &lt; k) return 0;
     if (0 == n) return 0;
     if (0 == k) return 1;
     if (n == k) return 1;
     if (1 == k) return n;
  
     map&lt;std::pair&lt;long long, long long&gt;, long long&gt;::iterator it;
  
     if((it = memo.find(std::make_pair(n, k))) != memo.end()) {
          return it-&gt;second;
     }
     else
     {
          long long value = (combinations(n-1, k-1,p)%p + combinations(n-1, k,p)%p)%p;
          memo.insert(std::make_pair(std::make_pair(n, k), value));
          return value;
     }  
  }
  </code></pre>