Fast Power

Return xⁿ modulo 1,000,000,007. n can be as large as 10¹⁸, so going down one step at a time is far too slow. Halve n instead.

Examples

Example 1

Input:  x = 2, n = 10
Output: 1024

Example 2

Input:  x = 3, n = 0
Output: 1