Description

强哥的要求很简单，他就是想求a的b次幂。 你没有听错，就是这么简单。 答案会很大，所以结果要取模 $1000000007$

Input

首先输入测试数据的个数。 对于每组测试样例： 输入两个整数，$a(0 < a < 100000)，b(0 < b < 100000)$。

Output

输出每个测试样例中a的b次幂。

Sample Input

3
2 3
5 2
3 2

Sample Output

8
25
9