Nội dung bài toán

Nhiệm vụ của bạn là tính giá trị ~ a^b \mod (10^9 + 7) ~ một cách hiệu quả.

Lưu ý rằng trong bài toán này, ta giả định ~ 0^0 = 1 ~.

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên ~ n ~: số lượng phép tính.
• Tiếp theo là ~ n ~ dòng, mỗi dòng chứa hai số nguyên ~ a ~ và ~ b ~.

Dữ liệu ra

• In ra ~ n ~ giá trị, mỗi giá trị là kết quả của ~ a^b \mod (10^9 + 7) ~.

Ràng buộc

• ~ 1 \leq n \leq 2 \cdot 10^5 ~
• ~ 0 \leq a, b \leq 10^9 ~

Ví dụ

Dữ liệu vào

3
3 4
2 8
123 123

Dữ liệu ra

81
256
921450052