/**
 * @brief 剰余演算のテストプログラム
 * @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(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));
}



/**
 * @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_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;
}

Measured memory_bytes: 3108