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;
int main() {
  long int m, n, i, x = 1, s = 1, t, u, v, w, y, r = 1, k;
  scanf("%ld %ld", &m, &n);
  for (i = 1; x < 1000000007 && i <= n; ++i) {
    x = x * m;
  }
  if (x < 1000000007) {
    cout << x << endl;
  } else {
    t = n / (i - 1);
    u = n % (i - 1);
    v = x % 1000000007;
    for (w = 1; w <= t; ++w) {
      s = s * v;
    }
    for (k = 1; k <= u; ++k) {
      r = r * m;
    }
    y = s * r;
    printf("%ld\n", y % 1000000007);
  }
  return 0;
}
