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>
template <
    class Integer1, class Integer2,
    typename std::enable_if<std::is_signed<Integer1>::value &&
                            std::is_signed<Integer2>::value>::type* = nullptr>
constexpr auto mod(Integer1 x, Integer2 n) -> decltype(x % n) {
  static_assert(
      std::is_integral<Integer1>::value && std::is_integral<Integer2>::value,
      "only makes sence for integral types");
  return x >= 0 ? x % n : ((x % n) + n) % n;
}
template <
    class Integer1, class Integer2,
    typename std::enable_if<std::is_signed<Integer1>::value &&
                            std::is_unsigned<Integer2>::value>::type* = nullptr>
constexpr auto mod(Integer1 x, Integer2 n)
    -> decltype(x % static_cast<typename std::make_signed<Integer2>::type>(n)) {
  return mod(x, static_cast<typename std::make_signed<Integer2>::type>(n));
}
template <
    class Integer1, class Integer2,
    typename std::enable_if<std::is_unsigned<Integer1>::value &&
                            std::is_unsigned<Integer2>::value>::type* = nullptr>
constexpr auto mod(Integer1 x, Integer2 n) -> decltype(x % n) {
  return x % n;
}
template <
    class Integer1, class Integer2,
    typename std::enable_if<std::is_unsigned<Integer1>::value &&
                            std::is_signed<Integer2>::value>::type* = nullptr>
constexpr auto mod(Integer1 x, Integer2 n)
    -> decltype(x %
                static_cast<typename std::make_unsigned<Integer2>::type>(n)) {
  return mod(x, static_cast<typename std::make_unsigned<Integer2>::type>(n));
}
template <
    class Integer1, class Integer2, class Integer3,
    typename std::enable_if<std::is_integral<Integer1>::value &&
                            std::is_unsigned<Integer2>::value &&
                            std::is_integral<Integer3>::value>::type* = nullptr>
constexpr auto mod_pow(Integer1 a, Integer2 b, Integer3 n)
    -> decltype(mod(a, n)) {
  return b == 0     ? 1
         : b & 0x01 ? mod_pow(mod(a * a, n), b >> 1, n) * mod(a, n)
                    : mod_pow(mod(a * a, n), b >> 1, n);
}
template <
    class Integer1, class Integer2, class Integer3,
    typename std::enable_if<std::is_integral<Integer1>::value &&
                            std::is_signed<Integer2>::value &&
                            std::is_integral<Integer3>::value>::type* = nullptr>
constexpr auto mod_pow(Integer1 a, Integer2 b, Integer3 n)
    -> decltype(mod(a, n)) {
  return mod_pow(a, static_cast<typename std::make_unsigned<Integer2>::type>(b),
                 n);
}
int main(void) {
  using namespace std;
  const std::int64_t n = 1000000007;
  std::int64_t a, b;
  cin >> a >> b;
  cout << mod_pow(a, b, n) << endl;
  return 0;
}
