Where it runs
1. The problem
Step 135 found primes with less work per number. This step does less work per power. You need base^exp: base multiplied by itself exp times. When exp is small, you just multiply. When exp is a million or a billion, multiplying one step at a time means a million or a billion operations.
There is a second problem. The number 21000000 has more than 300,000 digits. A normal integer cannot hold it, and you usually don't need it anyway: the problem asks for the answer modulo some number m, that is, the remainder after dividing by m. So you need base^exp mod m, with the numbers kept small the whole way and far fewer steps than exp.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that raise a number to a huge power, often with a remainder. Squaring the base and halving the exponent takes O(log n) steps where plain multiplying takes n. When the modulus is near 10^9 the squares pass 2^53, and lesson 137 shows the fix.
Fast power on a decimal number with no remainder. For a negative n, raise 1/x to the power minus n.
The modulus is 1337, so the squares stay far below 2^53. Go through the digits of b, raise the result so far to the 10th power and multiply by a to the next digit.
Each check is two powMod calls, and the outer modulus is at most 1000, so the lesson's version is safe.