#include <stdio.h>
long long int dp[100000]={0},m;
long long int pow(long long int n){
    if(n==1)return m;
    long long int mid=n/2;
    if(n>=100000)return pow(n-mid)*pow(mid)%1000000007;
    if(dp[n]!=0)return dp[n];
    return dp[n]=(pow(n-mid)*pow(mid))%1000000007;
}
int main(){
    int n;
    scanf("%lld%d",&m,&n);
    printf("%lld\n",pow(n));
}
### Prompt

Create a solution in CPP for the following problem:

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

### Response

```cpp
#include <stdio.h>
long long int dp[100000]={0},m;
long long int pow(long long int n){
    if(n==1)return m;
    long long int mid=n/2;
    if(n>=100000)return pow(n-mid)*pow(mid)%1000000007;
    if(dp[n]!=0)return dp[n];
    return dp[n]=(pow(n-mid)*pow(mid))%1000000007;
}
int main(){
    int n;
    scanf("%lld%d",&m,&n);
    printf("%lld\n",pow(n));
}
```