title: Calculating 1^X + 2^X + ... + N^X mod 1000000007
body: <p>Is there any algorithm to calculate <code>(1^x + 2^x + 3^x + ... + n^x) mod 1000000007</code>? <br />
  Note: <code>a^b</code> is the b-th power of a.</p>
  
  <p>The constraints are <code>1 &lt;= n &lt;= 10^16, 1 &lt;= x &lt;= 1000</code>. So the value of N is very large.</p>
  
  <p>I can only solve for <code>O(m log m)</code> if <code>m = 1000000007</code>. It is very slow because the time limit is 2 secs.</p>
  
  <p>Do you have any efficient algorithm?</p>
  
  <p>There was a comment that it might be duplicate of <a href="https://stackoverflow.com/questions/9169167/need-help-in-mod-1000000007-questions">this question</a>, but it is definitely different.</p>