For given integers m and n, compute mn (mod 1,000,000,007). Here, A (mod M) is the remainder when A is divided by M.

Constraints

* 1 ≤ m ≤ 100
* 1 ≤ n ≤ 109

Input


m n


Two integers m and n are given in a line.

Output

Print mn (mod 1,000,000,007) in a line.

Examples

Input

2 3


Output

8


Input

5 8


Output

390625
    #include<stdio.h> 
    using namespace std; 
    long long c=1000000007;
    long long  PowerMod(long long  a, long long  b) 
{
    long long  ans = 1;
    a = a % c;
    while(b>0)
    {
    if(b % 2 == 1)
    ans = (ans * a) % c;
    b = b/2;
    a = (a * a) % c;
    }
    return ans;
}
    int main(){ 
 
       long long   x,n; 
       scanf("%lld%lld",&x,&n); 
       printf("%lld\n",mi(x,n)); 
      return 0; 
    }  
