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:
MOD = 1000000007

''''
def power(a,b):
    if(b==0):
        return 1
    temp = power(a, b/2)
    if(b%2 == 0):
        return temp*temp
    else:
        return a*temp*temp
'''

if __name__ == "__main__":
    try:
        A = int(input())
        B = int(input())
        print(pow(A,B,MOD))
    except Exception as e:
        print(e)