Lũy thừa nhanh

Trung bình

số họcchia để trị3 test · 3 giây

Tính aᵇ mod m cho nhiều bộ (a, b, m).

b lên tới 10¹⁸ nên không thể nhân b lần. Bình phương liên tiếp: aᵇ = (a^(b/2))² nếu b chẵn → O(log b). Cẩn thận tràn số khi nhân hai số ~10⁹ trong C++/Java (dùng 64-bit).

Dữ liệu vào

Dòng 1: t (1 ≤ t ≤ 10⁴).

t dòng: a b m (0 ≤ a ≤ 10⁹, 0 ≤ b ≤ 10¹⁸, 1 ≤ m ≤ 10⁹).

t dòng.

Input

Output

24
1
0

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.