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:
#define 1000000007
def power(x,y):
	if y==0:
		return 1
	t=power(x,y/2)%1000000007
	if y%2==0:
		return (t*t)%1000000007
	else: 
		return (((x*t)%1000000007)*t)%1000000007

import math
x=int(input())
y=int(input())
z=1000000007
ans=pow(x,y,z)

print ans