title: Calculating nCr mod p efficiently when n is very large
body: <p>I need to calculate <code>nCr mod p</code> efficiently. Right now, I have written this piece of code, but it exceeds the time limit. Please suggest a more optimal solution.</p>
  
  <p>For my case, <code>p = 10^9 + 7 and 1 ≤ n ≤ 100000000</code></p>
  
  <p>I have to also make sure that there is no overflow as <code>nCr mod p</code> is guaranteed to fit in 32 bit integer, however <code>n!</code> may exceed the limit.</p>
  
  <pre><code>def nCr(n,k):
      r = min(n-k,k)
      k = max(n-k,k)
      res = 1
      mod = 10**9 + 7
  
      for i in range(k+1,n+1):
          res = res * i
          if res &gt; mod:
              res = res % mod
  
      res = res % mod
      for i in range(1,r+1):
          res = res/i
      return res
  </code></pre>
  
  <p>PS : Also I think my code may not be completely correct. However, it seems to work for small <code>n</code> correctly. If its wrong, please point it out !</p>