title: Fast multiplication of large numbers modulo n
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions">Need help in mod 1000000007 questions</a>  </p>
  </blockquote>
  
  
  
  <p>I have a set of numbers for which i want to compute total product modulo 1000007. e.g if my array contains 1000 numbers then i need to compute the following. </p>
  
  <pre><code>int product = 1;
  for(int i=0;i&lt;Array_Max;i++)
    product = product * Array[i]
  </code></pre>
  
  <p>then product modulo 1000007 = ?</p>
  
  <p>Is there any algorithm to optimize the above pseudo code ? Right now i am unable to store the product because of overflow.</p>
  
  <p>Any suggestion appreciated. </p>