Máy chủ lũy thừa modulo

Bối cảnh và bài toán

Một dịch vụ xác thực sinh mã bằng biểu thức a^b mod 1 000 000 007. Hệ thống phải xử lý một lượng lớn yêu cầu, trong khi số mũ có thể lên tới hàng tỷ.

Không thể thực hiện b phép nhân cho từng yêu cầu.

Yêu cầu

Với mỗi cặp (a,b), tính a^b mod 1 000 000 007. Trong bài này quy ước 0^0 = 1.

Input

• Dòng 1: số nguyên q.
• q dòng tiếp theo: mỗi dòng chứa hai số nguyên a b.

Output

Với mỗi truy vấn, in giá trị a^b mod 1 000 000 007 trên một dòng.

Ràng buộc

• 1 <= q <= 2 * 10^5
• 0 <= a,b <= 10^9

Chấm điểm

Ví dụ 1

Input

3
3 4
2 8
123 123

Output

81
256
921450052

Giải thích. Các lũy thừa được lấy modulo 1 000 000 007 sau quá trình tính.

Ví dụ 2

Input

3
0 0
0 5
1000000008 2

Output

1
0
1

Giải thích. Theo quy ước, 0^0=1. Ngoài ra 1000000008 ≡ 1 (mod 1000000007).

Thông tin bài tập

Nguồn: Phỏng theo CSES Problem Set — Exponentiation (Task 1095). Tham khảo: https://cses.fi/problemset/task/1095/