Lũy thừa nhanh

Trong một thiên hà xa xôi, một nền văn minh cổ đại đã phát triển một hệ thống số học phức tạp để đo lường năng lượng của các vì sao. Năng lượng của một chòm sao, được biểu diễn bằng một số nguyên không âm \(a\), khi được kích hoạt bởi một hằng số vũ trụ \(b\), sẽ tạo ra một giá trị năng lượng mới. Giá trị này được tính toán bằng phép toán luỹ thừa, nhưng để tránh sự quá tải năng lượng, kết quả phải được lấy theo một modulo đặc biệt, là \(10^9 + 7\).

Tuy nhiên, có một trường hợp đặc biệt mà các nhà thiên văn học cổ đại đã ghi chép lại: khi một chòm sao có năng lượng ban đầu là 0 được kích hoạt bởi hằng số 0, nó sẽ tạo ra một năng lượng kích hoạt cơ bản bằng 1.

Bạn là một nhà toán học vũ trụ, được giao nhiệm vụ giải mã những công thức cổ đại này. Bạn cần xây dựng một chương trình để tính toán giá trị năng lượng cuối cùng cho một loạt các chòm sao và hằng số vũ trụ được đưa ra.

Yêu cầu: Cho các cặp số nguyên không âm \((a, b)\), hãy tính giá trị \(a^b \pmod{10^9 + 7}\). Lưu ý rằng theo quy tắc đặc biệt, \(0^0 = 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \cdot 10^5\)), là số lượng câu hỏi.
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a, b\) (\(0 \le a, b \le 10^9\)).

Output

• In ra \(n\) dòng, mỗi dòng chứa một số nguyên là kết quả của phép tính \(a^b \pmod{10^9 + 7}\) tương ứng với mỗi cặp \((a, b)\) trong dữ liệu vào.

Example

3
3 4
2 8
123 123

81
256
921450052

Scoring

• Subtask \(1\) (\(50\%\) số điểm) : \(n, a, b \leq 1000\).
• Subtask \(2\) (\(50\%\) số điểm) : không có ràng buộc gì thêm.