#include <stdio.h>
#include <string.h>
long long int d = 1000000007ll;

long long int pow(long long int m, long long int n){
	long long int res;
	if(n == 0) return 1;
	res = pow((m*m)%d, n/2);
	if(n % 2){
		res = (res*m)%d;
	}
	return res;
}

int main(void) {
	long long int n;
	int m;
	
	scanf("%d%lld", &m, &n);
	
	printf("%lld\n", pow(m, n));
	
	return 0;
}
### Prompt

Generate a CPP solution to the following problem:

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

### Response

```cpp
#include <stdio.h>
#include <string.h>
long long int d = 1000000007ll;

long long int pow(long long int m, long long int n){
	long long int res;
	if(n == 0) return 1;
	res = pow((m*m)%d, n/2);
	if(n % 2){
		res = (res*m)%d;
	}
	return res;
}

int main(void) {
	long long int n;
	int m;
	
	scanf("%d%lld", &m, &n);
	
	printf("%lld\n", pow(m, n));
	
	return 0;
}
```