#include<cstdio>
int main() {
	long long m, n, p=1000000007, d, ans=1;
	scanf("%lld%lld", &m, &n);
	for (d = 1 << 30; d >= 1; d >>= 1) {
		if (d&n) {
			ans = ((ans*ans)%p)*m%p;
		}
		else {
			ans = (ans*ans)%p;
		}
	}
	printf("%d\n", ans);
	return 0;
}

### Prompt

Create a solution in Cpp for 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<cstdio>
int main() {
	long long m, n, p=1000000007, d, ans=1;
	scanf("%lld%lld", &m, &n);
	for (d = 1 << 30; d >= 1; d >>= 1) {
		if (d&n) {
			ans = ((ans*ans)%p)*m%p;
		}
		else {
			ans = (ans*ans)%p;
		}
	}
	printf("%d\n", ans);
	return 0;
}

```