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>
int bk[15][2];
void pfuct(int);
int pnCheck(int);
int powpow(int s);
int bkn;
int tai = 5;
int main() {
  int sis = 8;
  int mod = 1000000007;
  int ans, tmp;
  if (tai > mod) tai %= mod;
  pfuct(sis);
  ans = 1;
  for (bkn = 0; bkn < 15 && bk[bkn][0]; bkn++) {
    tmp = powpow(1);
    tmp %= mod;
    ans *= tmp;
    ans %= mod;
  }
  printf("%d\n", ans);
  return 0;
}
int powpow(int s) {
  int tn = 1;
  int i;
  if (s == bk[bkn][1]) {
    for (i = 0; i < bk[bkn][0]; i++) {
      tn *= tai;
    }
  } else {
    for (i = 0; i < bk[bkn][0]; i++) {
      tn *= powpow(s + 1);
    }
  }
  return tn;
}
void pfuct(int data) {
  int i;
  int cod;
  int bkcnt = 0;
  for (i = 0; i < 15; i++) bk[i][1] = bk[i][0] = 0;
  cod = data;
  i = 2;
  while (data % i == 0) {
    if (bk[bkcnt][0] != i) {
      bk[bkcnt][0] = i;
    }
    data /= 2;
    bk[bkcnt][1]++;
  }
  if (bk[bkcnt][1]) bkcnt++;
  for (i = 3; i <= data && i * i <= cod; i += 2) {
    if (pnCheck(i)) {
      while (data % i == 0) {
        if (bk[bkcnt][0] != i) {
          bk[bkcnt][0] = i;
        }
        data /= i;
        bk[bkcnt][1]++;
      }
      if (bk[bkcnt][1]) bkcnt++;
    }
  }
  if (data != 1) {
    bk[bkcnt][0] = data;
    bk[bkcnt][1] = 1;
  }
}
int pnCheck(int x) {
  int i;
  int fl = 0;
  for (i = 3; i * i <= x; i += 2) {
    if (pnCheck(i)) {
      if (fl = (x % i == 0)) break;
    }
  }
  return !fl;
}
