title: What's wrong with my power function which takes 2 as base, n as exponent and computes answer modulo 10^9+7?
body: <p><strong>My code:</strong></p>
  <pre><code>int power(int n)
  {
      int num = 1000000007;
      if (n == 0)
          return 1;
      if (n%2 == 1)
      {
          int storage = power((n-1)/2);
          return (2*storage*storage)%num;
      }
      int storage = power(n/2);
      return (storage*storage)%num;
  }
  
  </code></pre>
  <p>I have used <a href="https://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow noreferrer">exponentiation by squaring</a> to make it more efficient, I know that something is wrong because the output to <code>n= 1000</code> generates <code>495105785</code> whereas the correct answer is <code>688423210</code>.</p>
  <p>I even tried changing the return datatype to long long to check possible overflow that may occur in lines <code>9</code> and <code>12</code>, but the answer remained the same. Any help would be appreciated.</p>