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<iostream>
#include<cstdio>
using namespace std;
typedef long long int ll;
ll M,N;
const ll MOD=1e9+7;
ll X[50];
ll ans=1;
int main()
{
	scanf("%lld%lld",&M,&N);
	X[0]=1;
	X[1]=M;
	for(int i=2;i<50;i++)X[i]=(X[i-1]*X[i-1])%MOD;
	for(int i=0;i<50;i++){
		if(N%2==1){
			ans*=X[i+1];
			ans%=MOD;
		}
		N/=2;
	}
	printf("%lld\n",ans);
	return 0;
}