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;
const auto gcu = getchar_unlocked;
const auto pcu = putchar_unlocked;
template <typename T>
T in(int c) {
  T n = 0;
  int m = 1;
  while (isspace(c)) {
    c = gcu();
  }
  if (c == '-') m = -1, c = gcu();
  do {
    n = 10 * n + (c - '0'), c = gcu();
  } while (c >= '0' && c <= '9');
  return m * n;
}
inline int in() { return in<int>(gcu()); }
template <typename T>
T scan(T &n) {
  int c = gcu();
  return c == EOF ? false : (n = in<T>(c), true);
}
inline bool scan(char &c) {
  c = gcu();
  gcu();
  return c != EOF;
}
template <typename H, typename... T>
inline bool scan(H &h, T &&...t) {
  return scan(h) && scan(t...);
}
inline void out(bool b) { pcu('0' + b); }
inline void out(const char *s) {
  while (*s) pcu(*s++);
}
inline void out(char c) { pcu(c); }
template <typename T>
inline void out(T n) {
  static char b[20];
  char *p = b, m = n < 0 ? pcu('-'), -1 : 1;
  if (!n)
    *p++ = '0';
  else
    while (n) *p++ = n % 10 * m + '0', n /= 10;
  while (p != b) pcu(*--p);
}
inline void outl() { out('\n'); }
template <typename H, typename... T>
inline void out(H &&h, T &&...t) {
  out(h);
  out(move(t)...);
}
template <typename... T>
inline void outl(T &&...t) {
  out(move(t)...);
  outl();
}
int main() {
  int r = 1, M = 1000000007;
  for (int m = in (), n = in(); n; n >>= 1, m = m * m % M)
    if (n & 1) r = r * m % M;
  outl(r);
}
