title: Optimising code for modular arithmetic
body: <p>I am trying to calculate below expression for large numbers.</p>
  
  <p><img src="https://i.stack.imgur.com/wrnVb.png" alt="N!/((N/2)!(N/2)!)"></p>
  
  <p>Since the value of this expression will be very large, I just need the value of this expression modulus some prime number.  Suppose the value of this expression is <code>x</code> and I choose the prime number <code>1000000007</code>; I'm looking for <code>x % 1000000007</code>.</p>
  
  <p>Here is my code.</p>
  
  <pre><code>#include&lt;iostream&gt;
  #define MOD 1000000007
  using namespace std;
  int main()
  {
      unsigned long long A[1001];
      A[2]=2;
      for(int i=4;i&lt;=1000;i+=2)
      {
          A[i]=((4*A[i-2])/i)%MOD;
          A[i]=(A[i]*(i-1))%MOD;
  
      while(1)
      {
          int N;
          cin&gt;&gt;N;
          cout&lt;&lt;A[N];
      }
  }
  </code></pre>
  
  <p>But even this much optimisation is failing for large values of N.  For example if N is 50, the correct output is <code>605552882</code>, but this gives me <code>132924730</code>. How can I optimise it further to get the correct output?</p>
  
  <p><strong>Note</strong> : I am only considering N as even.</p>