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
var log = console.log;
if (typeof process != "undefined") {
	var input = "";
	process.stdin.resume();
	process.stdin.setEncoding('utf8');
	process.stdin.on('data', function (chunk) {
		input += chunk;
	});
	process.stdin.on('end', function () {
		var lines = input.split("\n");
		main(lines);
	});
}
var mod = 1000000007;
function rec(m,n){
	if(n <= 3){
		return Math.pow(m,n) % mod;
	}
	if(n % 2 == 0){
		return Math.pow(rec(m,n/2),2) % mod;
	}else{
		return (Math.pow(rec(m,(n-1)/2),2) * m) % mod;
	}
}
function main(lines){
  var k = lines[0];
  var j = k.split(" ").map(function(e){return Number(e);});
  log(rec(j[0],j[1]));
}