title: How to calculate EXTREMELY big binomial coefficients modulo by prime number?
body: <p><a href="http://acm.hdu.edu.cn/showproblem.php?pid=3037" rel="nofollow">This problem</a>'s answer turns out to be calculating large binomial coefficients modulo prime number using <a href="https://en.wikipedia.org/wiki/Lucas%27_theorem" rel="nofollow">Lucas' theorem</a>. Here's the solution to that problem using this technique: <a href="https://gist.github.com/anonymous/6f7b23ce23fe05c9772b" rel="nofollow">here</a>.</p>
  
  <p>Now my questions are:</p>
  
  <ul>
  <li>Seems like my code expires if the data increases due to overflow of variables. Any ways to handle this?</li>
  <li>Are there any ways to do this without using this <a href="https://en.wikipedia.org/wiki/Lucas%27_theorem" rel="nofollow">theorem</a>?</li>
  </ul>
  
  <p><strong>EDIT:</strong> note that as this is an <em>OI or ACM</em> problem, external libs other than original ones are not permitted.</p>
  
  <p>Code below: </p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string.h&gt;
  #include &lt;stdio.h&gt;
  using namespace std;
  
  #define N 100010
  
  long long mod_pow(int a,int n,int p)
  {
      long long ret=1;
      long long A=a;
      while(n)
      {
          if (n &amp; 1)
              ret=(ret*A)%p;
          A=(A*A)%p;
          n&gt;&gt;=1;
      }
      return ret;
  }
  
  long long factorial[N];
  
  void init(long long p)
  {
      factorial[0] = 1;
      for(int i = 1;i &lt;= p;i++)
          factorial[i] = factorial[i-1]*i%p;
      //for(int i = 0;i &lt; p;i++)
          //ni[i] = mod_pow(factorial[i],p-2,p);
  }
  
  long long Lucas(long long a,long long k,long long p) 
  {
      long long re = 1;
      while(a &amp;&amp; k)
      {
          long long aa = a%p;long long bb = k%p;
          if(aa &lt; bb) return 0; 
          re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;
          a /= p;
          k /= p;
      }
      return re;
  }
  
  int main()
  {
      int t;
      cin &gt;&gt; t;
      while(t--)
      {
          long long n,m,p;
          cin &gt;&gt; n &gt;&gt; m &gt;&gt; p;
          init(p);
          cout &lt;&lt; Lucas(n+m,m,p) &lt;&lt; "\n";
      }
      return 0;
  }
  </code></pre>