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<stdio.h>
#define DIV 1000000007

typedef unsigned long long int verylong

verylong mod(verylong m,int n){
    verylong x,y=0,z=0,i,j;
    /*printf("mod(%d,%d): called\n",m,n);*/
    if(n==0){
        return 1;
    }else if(n==1){
        return m;
    }else{
        if(m>DIV-m)m=DIV-m;
        for(i=0;i<m;i++){/*????????¢???????????§???????????????????????§?????????*/
            y+=m;
            if(y>DIV)y=y%DIV;
        }
        x = mod(y,n/2)%DIV;
        if(n%2==0){
            return x;
        }else{
            for(j=0;j<m;j++){
               z+=x;
               if(z>DIV)z=z%DIV;
            }
            return z;
        }
    }
}

int main(){
    int m;
    int n;
    scanf("%d %d",&m,&n);
    printf("%d\n",mod(m,n));
}