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
      N7hoatt 8:57 a.m. 30 Tháng 8, 2023

      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

      • Dòng đầu tiên gồm số nguyên \(n\): số lượng các tính toán.
      • \(n\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(a\), \(b\)\(c\).

      Output

      • In giá trị của mỗi \(a^{b^c} \space\) \(mod\) \(\space 10^9 +7\).

      Constraints

      • \(1 \leq n \leq 2 \times 10^5\).
      • \(0 \leq a, b, c \leq 10^9\).

      Example

      Test

      Input
      3
      3 7 1
      15 2 2
      3 4 5
      Output
      2187
      50625
      763327764
      Note
      1 phản hồi