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

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:

1000

Output:

688423210