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 LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
template <typename T>
using VT = vector<T>;
const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;
LL f(int M, int N) {
  if (N == 0) return 1;
  if (M & 1) return M * f(M, N - 1) % MOD;
  LL t = f(M, N / 2);
  return t * t * MOD;
}
void solve(int M) {
  int N;
  cin >> N;
  cout << f(M, N) << endl;
  return;
}
signed main(void) {
  LL n, m, p, a, b, c, x, y, z, q;
  string s;
  bool f = false;
  while (cin >> n, n) {
    solve(n);
    return 0;
  }
}
