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
import java.util.*;
import java.io.*;

class Main {

	static final int MOD = 1000000007;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String line = br.readLine();
		int m = Integer.parseInt(line.substring(0,line.indexOf(" ")));
		int n = Integer.parseInt(line.substring(line.indexOf(" ")+1));

		long ans = 1;
		while (n > 0) {
			if ((n&1) == 1)
				ans = ans * m % MOD;
			m = m * m % MOD;
			n >>= 1;
		}

		System.out.println(ans);

		br.close();
	}
}