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 <bits/stdc++.h>
using namespace std;

using Int = long long;
//(x^k) mod m
Int powMod(Int x, Int k, Int m) {
	if (k == 0)     return 1;
	if (k % 2 == 0) return powMod(x*x % m, k / 2, m);
	else            return x*powMod(x, k - 1, m) % m;

}
int main(void) {
	long long M, N;
	cin >> M >> N;
	cout << powMod(M, N, 1'000'000'007) << endl;
	return 0;
}
