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;
bool judge(int s) {
  for (int i = 2; i * i <= s; i++) {
    if (s % i != 0 && (i + 1) * (i + 1) > s) {
      return true;
    }
    if (s % i == 0) {
      return false;
      break;
    }
  }
}
int main() {
  unsigned long long a;
  int m, n, b;
  cin >> m >> n;
  a = m;
  b = 1000000007;
  int l;
  l = n;
  int k[1000] = {};
  if (judge(l)) {
    k[0] = l;
  } else {
    int count = 0;
    for (int j = 2; j * j <= l;) {
      if (l == 1) {
        break;
      }
      if (l % j == 0 && judge(j)) {
        l = l / j;
        k[count] = j;
        count++;
        continue;
      }
      j++;
    }
  }
  for (int j = 0; k[j] != 0; j++) {
    for (int i = 1; i < k[j]; i++) {
      a = a * m;
      if (a >= b) {
        a = a % b;
        if (a == m && n - i > n % i) {
          n = n % i;
          i = 0;
        }
        if (a == 1) {
          break;
        }
      }
    }
  }
  return 0;
}
