Lũy thừa với modulo thay đổi

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

Một cụm máy chủ gồm nhiều node, mỗi node dùng một modulus riêng để kiểm tra lũy thừa. Với mỗi yêu cầu, hệ thống nhận bộ ba (b,p,m) và phải tính b^p mod m.

Do p và m đều có thể lớn, lời giải phải vừa nhanh vừa kiểm soát phép nhân trung gian.

Yêu cầu

Với mỗi truy vấn (b,p,m), tính b^p mod m.

Input

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

Output

Với mỗi truy vấn, in b^p mod m.

Ràng buộc

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

Chấm điểm

Ví dụ 1

Input

3
3 18132 17
17 1765 3
2374859 3029382 36123

Output

13
2
13195

Giải thích. Mỗi dòng sử dụng một modulus riêng, nhưng đều có thể xử lý bằng cùng nguyên lý lũy thừa nhanh.

Ví dụ 2

Input

3
10 0 7
0 5 13
123 456 1

Output

1
0
0

Giải thích. Mọi số mũ 0 cho kết quả 1 mod m; khi m=1, mọi phần dư bằng 0.

Thông tin bài tập

Nguồn: Phỏng theo UVa Online Judge 374 — Big Mod. Tham khảo: https://onlinejudge.org/external/3/374.pdf