Modular Fast Exponentiation
medium
1. You are given a number x. 2. You are given another number n. 3. You are required to calculate x raised to the power n mod 10^9 + 7 in logn complexity.
Constraints
1 <= x <= 10^9 0 <= n <= 10^9
Format
Input
The first line contains the integer x and n.
Output
Output an integer in a line containing x^n mod 10^9+7.
Example
Sample Input
10 5
Sample Output
100000