Problem: Rhezo likes numbers of the form A^B. But computing A^B, for any 2 numbers A and B is a hard task for him. He would like you to help him out in this.

Input:
First line of input contains a single integer A. Second line contains the integer B.

Output:
Help Rhezo find A^B. As this number can be large, print it modulo 10^9+7.

Constraints:
 1 ≤ A ≤ 10^9  
 1 ≤ B ≤ 10^{10^5} 

SAMPLE INPUT
4
3

SAMPLE OUTPUT
64

Solution (in PYTHON):

Solution:
def pow_mod(a,b):
	ans = 1
	MOD = 10**9+7
	while(b > 0):
		if(b&1==1):
			ans = (ans*a)%MOD
		a = (a*a)%MOD
		b = b >> 1
	return ans%MOD
 
A=int(raw_input().strip())
B=int(raw_input().strip())
print(pow_mod(A,B))