title: How to calculate (n!)%1000000009
body: <p>I need to find n!%1000000009.
  n is of type 2^k for k in range 1 to 20.
  The function I'm using is:</p>
  
  <pre><code>#define llu unsigned long long
  #define MOD 1000000009
  
  llu mulmod(llu a,llu b) // This function calculates (a*b)%MOD caring about overflows
  {
      llu x=0,y=a%MOD;
      while(b &gt; 0)
      {
          if(b%2 == 1)
          {
              x = (x+y)%MOD;
          }
          y = (y*2)%MOD;
          b /= 2;
      }
      return (x%MOD);
  }
  
  llu fun(int n)   // This function returns answer to my query ie. n!%MOD
  {
      llu ans=1;
      for(int j=1; j&lt;=n; j++)
      {
          ans=mulmod(ans,j);
      }
      return ans;
  }
  </code></pre>
  
  <p>My demand is such that I need to call the function 'fun', n/2 times. My code runs too slow for values of k around 15. Is there a way to go faster?</p>
  
  <p>EDIT:
  In actual I'm calculating 2*[(i-1)C(2^(k-1)-1)]*[((2^(k-1))!)^2] for all i in range 2^(k-1) to 2^k. My program demands (nCr)%MOD caring about overflows. </p>
  
  <p>EDIT: I need an efficient way to find nCr%MOD for large n.</p>