What's wrong with my power function which takes 2 as base, n as exponent and computes answer modulo 10^9+7?

My 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;
}

I have used exponentiation by squaring to make it more efficient, I know that something is wrong because the output to n= 1000 generates 495105785 whereas the correct answer is 688423210.

I even tried changing the return datatype to long long to check possible overflow that may occur in lines 9 and 12, but the answer remained the same. Any help would be appreciated.

Solution

storage * storage may overflow int value sometimes, e.g. if storage is 2^30 then storage * storage is 2^60 which will be truncated to int to fit into 2^32 but you want full-size computation otherwise you'll get wrong remainder. Use int64_t for intermediate results, like in code below:

Try it online!

#include <cstdint>
#include <iostream>
using namespace std;

int power(int n)
{
    int64_t num = 1000000007;
    if (n == 0)
        return 1;
    if (n % 2 == 1)
    {
        int64_t storage = power((n - 1) / 2);
        return (2 * storage * storage) % num;
    }
    int64_t storage = power(n / 2);
    return (storage * storage) % num;
}

int main() {
    cout << power(1000) << endl;
    return 0;
}

Input:

Output:

688423210