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\)\(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


  • 2
    penistone    4:21 a.m. 26 Tháng 12, 2023 đã chỉnh sửa
    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)

    • 1 bình luận nữa