Lũy thừa mod

Xem PDF

Đ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


  • 0
    huyhau6a2    8:25 p.m. 20 Tháng 12, 2021

    bài này mình nghĩ dùng công thức bài power01 được


    • 0
      nguyendanghau2006    9:16 p.m. 20 Tháng 12, 2021

      thank hint 😃


      • 0
        huyhau6a2    6:51 a.m. 21 Tháng 12, 2021

        Chưa chắc đâu vì mình chưa chắc a^((b^c)%k)%k=(a^b^c)%k đâu nha


        • 0
          PhanHuyKhang    7:45 a.m. 21 Tháng 12, 2021

          không bằng đâu bạn nhé


          • 0
            huyhau6a2    7:57 a.m. 21 Tháng 12, 2021 đã chỉnh sửa

            phải có cách nào đó khác chứ. Thế (((a^b)%k)^c)%k có bằng (a^b^c)%k không ta


            • 0
              PhanHuyKhang    8:29 a.m. 21 Tháng 12, 2021

              định lí fermat nhỏ ấy bạn


              • 0
                huyhau6a2    8:35 a.m. 21 Tháng 12, 2021

                chỉ cho mình đi, mình không biết

    7 bình luận nữa