Loading...
Loading...
Loading...
Kavya is building a puzzle game. A level's score starts at 1 and is multiplied by a whole number a, b times in a row. The factor a can be negative when a level has a penalty.
The score gets very large, so the game stores it modulo 10^9 + 7. Print a to the power b, modulo 10^9 + 7, as a value from 0 to 10^9 + 6. Any number to the power 0 is 1, including 0 to the power 0.
Example 1
Input
2 10
Output
1024
2 to the power 10 is 1024.
Example 2
Input
-2 3
Output
999999999
(-2)³ is -8. Modulo 10^9 + 7 that is 10^9 + 7 - 8 = 999999999.
Try the problem first. Open one hint at a time.
Multiplying b times is too slow when b is 10^18. Try to halve b at each step.
a^b = (a²)^(b / 2) when b is even, and a × a^(b - 1) when b is odd. Look at the bits of b.
Reduce a modulo 10^9 + 7 first, and fix a negative remainder by adding 10^9 + 7.
Keep every value below 10^9 + 7 and take % MOD after each multiplication, so each product stays below about 10^18 and fits in a long.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor