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

Lưu ý: Trong bài này, giả định rằng ~0^0 = 1~

Đầu vào:

Dòng đầu tiên chứa số nguyên ~n~: số phép tính.

~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a~ và ~b~

Đầu ra:

In ra n dòng, mỗi dòng là kết quả của phép tính tương ứng.

Ràng buộc:

~1 \le n \le 2 \cdot 10^5~

~0 \le a,b \le 10^9~

Ví dụ :

Input:

3
3 4
2 8
123 123

Output:

81
256
921450052