Nhiệm vụ của bạn là tính toán các giá trị ~a^b~ modulo ~10^9 + 7~.

Lưu ý: Giả định rằng ~0^0 = 1~.

Input

• Dòng đầu tiên là số nguyên dương ~n~ ~(1 \leq n \leq 2 \times 10^5)~ ~-~ số lượng phép tính cần thực hiện.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên không âm ~a~ và ~b~ ~(0 \leq a,b \leq 10^9)~.

Output

Gồm ~n~ dòng, mỗi dòng là kết quả của phép tính ~a^b~ modulo ~10^9 + 7~.

Sample Input

3
3 4
2 8
123 123

Sample Output

81
256
921450052