给定 $T\le 10^6$ 组询问，每组提供两个整数 $x, y \le 10^9$，求 $x^y \bmod (10^9 + 7)$。

样例

5
1 10000000
2 10000006
3 1000532
4 20349054
5 23490234

1
365977616
299038887
395085149
481385390