CSES - Exponentiation II | Lũy thừa II
Xem PDF
Điểm:
1400 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Việc của bạn là tính toán hiệu quả giá trị \(a^{b^c}\) modulo \(10^9 + 7\).
Lưu ý rằng trong bài này, ta cho rằng \(0^0 = 1\).
Input
- Dòng đầu tiên là 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 ba số nguyên \(a, b\) và \(c\).
Output
- In ra từng giá trị \(a^{b^c}\) modulo \(10^9+7\).
Constraints
- \(1 \le n \le 10^5\)
- \(1 \le a,b,c \le 10^9\)
Example
Sample input
3
3 7 1
15 2 2
3 4 5
Sample output
2187
50625
763327764
Bình luận
Note
\(C ≡ D\) (module m) không có nghĩa là \(A^C\) ≡ \(A^D\) (module m). Ví dụ \(2^3\) ≢ \(2^5\) (module 3)
Nhưng nếu \(C ≡ D\) (mod \(φ(n)\)) với \(φ\) là hàm phi Euler, thì \(A^C\) ≡ \(A^D\) (mod \(n\)) nếu như \(A\) nguyên tố cùng nhau với \(n\)
(Theo wikipedia, xem qua tại đây)
Hãy tính toán các giá trị \(a^{b^c} \space\) \(mod\) \(\space 10^9 +7\) một cách hiệu quả.
Lưu ý: trong bài này, ta giả định rằng \(0^0 = 1\).
Input
Output
Constraints
Example
Test
Input
Output
Note