Shrinking by one is too slow here

You could say 2 to the power 13 is 2 times 2 to the power 12, and keep going down by one. That is 13 calls, which is fine. But for an exponent of 10 to the power 15 it is that many calls: far too slow, and far too deep for any call stack.

It is like climbing a tall building one step at a time when there is an elevator.

Down by one each time: means as many calls as the exponent. Too many when it is huge.

The exponent at each call of power(2, 13)

exp

power(2, 13): 13 is odd. Ask for power(2, 6), square it, times one extra 2.

Move 1 of 6

Halve the exponent instead

2 to the power 12 is 2 to the power 6, times itself. So work out the half once, and square it. For an odd exponent, one base is left over: 2 to the power 13 is the half times the half times 2.

Each call halves the exponent, so 10 to the power 15 needs only about 50 calls. The base case is an exponent of 0, where the answer is 1.

Even exponent: the answer is the half times the half.

Odd exponent: the answer is the half times the half times the base.

Call once: store the half and reuse it. Calling twice undoes the speed-up.

In code

def power_mod(base, exp, mod):
    if exp == 0:
        return 1 % mod
    half = power_mod(base, exp // 2, mod)
    result = half * half % mod
    if exp % 2 == 1:
        result = result * (base % mod) % mod
    return result

Keep the numbers small with mod

2 to the power 1000 has hundreds of digits, so the problem asks for the answer mod m: the remainder after dividing by m. You may take the remainder after every multiplication, and the final remainder comes out the same, like a clock that wraps around.

With m up to 1,000,000, each product stays below 10 to the power 12, which fits in a long.

Reduce early: the remainder of a product equals the remainder of the reduced factors' product.

Use a long for products: in C++ and Java, since 999,999 times 999,999 overflows an int.