Modular Fast Exponentiation

medium
Question Solve Solutions 
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.

Input Format

The first line contains the integer x and n.

Output Format

Output an integer in a line containing x^n mod 10^9+7.

Constraints

1 <= x <= 10^9
0 <= n <= 10^9

Example

Input
10 5
Output
100000
Previous
Wilsons Theorem
Next
Modular C(n,r)

Related Questions

medium Extended Euclidean Algorithm medium Linear Diophantine Equation hard Eulers Totient Function medium Wilsons Theorem medium Modular C(n,r) hard No Max No Min medium Prime Factors Using Sieve medium All Factors Using Sieve easy Count Of Common Divisors medium Gcd Length medium I Hate 1111 medium Relatively Prime Pairs medium Sum Of Factors easy Chinese Remainder Theorem easy Monkey Tradition