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
/**
 * @brief 剰余演算のテストプログラム
 *
 * @note  関連URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=NTL_1_B
 *
 * @date  2016/08/06
 */




// ********************************************************************************
// 必要なヘッダファイルのインクルード
// ********************************************************************************

#include <iostream>
#include <cstdint>
#include <type_traits>



// ********************************************************************************
// 関数の定義
// ********************************************************************************

/**
 * @brief 整数xをnで割った剰余を取得する
 *
 * @note  C++11において、負の値に対して剰余演算を適用して得られる値はx mod nとは異なる.
 * @note  ここでは負の値xに対しても剰余が扱えるようにした.
 * 
 * @param Integer1 x  整数x
 * @param Integer2 n  正整数n
 */
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(mod(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(mod(x, static_cast<typename std::make_unsigned<Integer2>::type>(n))
{
    return mod(x, static_cast<typename std::make_unsigned<Integer2>::type>(n));
}


/**
 * @brief 2進表現を用いてベキ乗剰余(modular exponentiation)を解く(反復2乗法(repeated squaring))
 *
 * @param Integer1 a 非負整数a
 * @param Integer2 b 非負整数b
 * @param Integer3 n 正整数n
 * @return a ^ b mod 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  // bの最下位ビットが1か否か判定
                ? mod(mod_pow(mod(a * a, n), b >> 1, n) * 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;
}