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
class Main {

    private static final int CONST= 1000000007;
    public static void main(String args[]) {
		java.util.Scanner sc = new java.util.Scanner(System.in);
        long M = Integer.parseInt(sc.next());
        long N = Integer.parseInt(sc.next());
        System.out.println(myPow(M, N));
        sc.close();
    }

    private static long myPow(long m, long n){
        if(n == 0)  return 1;

        long res = myPow(m*m%CONST, n/2);
        if(n%2 == 1) res = res * m %CONST;
        return res;
    }
}
