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"
#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(v) v.begin(),v.end()
#define PB push_back
#define MP make_pair
using namespace std;
int main(){
    vector<int>S,T;
    int a,n,q;
    cin>>n;
    REP(i,n){cin>>a;S.PB(a);}
    cin>>q;
    REP(i,q){cin>>a;T.PB(a);}
    sort(ALL(S));
    sort(ALL(T));
    int cnt=0;
    if(binary_search(ALL(S),T[i]))cnt++;
    cout<<cnt<<endl;
}