小鑫爱数学

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小鑫酷爱数学,数学成绩很好。一天一个MM有一个问题不会,跑过来问小鑫:给你一个正整数n,一个正整数m让你求出来(n^m)% 1000000007的结果。例如,n = 2m= 2n^m = 2^2 = 4, 4 % 1000000007 = 4,输出4。这个题目小鑫一下子就卡住了,但是他不想在妹子面前丢脸,所以请你来帮助他。赶紧帮他解决一下吧。

Input

多组输入。 
两个正整数n(1 <= n <= 10^15)m(1 <= m <= 10^12)

Output

 n^m%1000000007的结果

Sample Input

2 3
5 5

Sample Output

8
3125

Hint

 

Source

xfl