Skip to content
CodeKruPro

Fast power: x to the power n, modulo 1,000,000,007

Coding problemEasy-Medium

Given an integer x and a whole number n, return x to the power n, divided by 1,000,000,007, keeping the remainder (this is called "modulo"). The answer is always between 0 and 1,000,000,006, even when x is negative.

Any number to the power 0 is 1, including 0 to the power 0.

n can be as large as about 9 x 10^18, so multiplying x by itself n times is far too slow.

Examples

Example 1
Input: x = 2, n = 10
Output: 1024
Example 2
Input: x = -2, n = 3
Output: 999999999
(-2)^3 = -8. Its remainder in the range 0 to 1,000,000,006 is 1,000,000,007 - 8.
Example 3
Input: x = 5, n = 0
Output: 1

Constraints

  • -1,000,000,000 <= x <= 1,000,000,000
  • 0 <= n <= 9,223,372,036,854,775,807 (a 64-bit integer)

Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.

Run your code to see the results here.

to answer and keep your progress. Reading is free for everyone.