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;
using i64 = int64_t;
using ui64 = uint64_t;

/////

const i64 mod = (i64)1e9+7;

i64 power(i64 e, i64 x){
    if(x == 0)return 1LL;
    i64 p = power(e, x/2);
    if(x&1)return p * p % mod * e % mod;
    else return p * p % mod;
}

int main(){
    i64 e,x;
    cin >> e >> x;
    cout << power(e,x) << endl;
}
