Lũy thừa mod

Xem PDF
Thời gian:
Python 0.75s
Tác giả:
phanhuykhang
Dạng bài
Điểm: 250 (p) Thời gian: 2.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Tính: \(a^{b^c}\) \(mod\) \(10^{18} + 9\).

Input

  • Dòng đầu ghi \(Q\) không quá \(5000\) - số câu hỏi.
  • \(Q\) dòng tiếp theo mỗi dòng ghi 3 số \(a,b,c\) không quá \(10^{15}\).

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm.

Example

Test 1

Input 
3
2 3 2
5 2 2
3 4 5
Output 
512
625
824168097938645257

Bình luận