## LBC_2F - Mũ cực mạnh

[https://luyencode.net/problem/lbc_2f](https://luyencode.net/problem/lbc_2f)

Định lý Fermat nhỏ: $a^{m-1} \equiv 1 \pmod{m}$ nếu $m$ là số nguyên tố và $\gcd(a, m) = 1$

Suy ra $a ^ {x} \equiv a ^ {x \% (m-1)} \pmod m$

Ví dụ, cần tính $a^{100} \mod 19$

$a^{100} \equiv a ^ {18} \cdot a ^ {18} \cdot a ^ {18} \cdot a ^ {18} \cdot a ^ {18} \cdot a ^ {10} \pmod m$

$a^{100} \equiv 1 \cdot 1 \cdot 1 \cdot 1 \cdot 1 \cdot a ^ {10} \pmod m$

$a^{100} \equiv a ^ {10} \pmod m$

Vậy thay vì tính $a^{b^c}$, ta sẽ tính $x = b^c$ $\%$ $(m-1)$, rồi sau đó tính $a^x$ $\%$ $m$.

Chú ý là truy vấn cần in ra các tổng của $a^{b^c}$ theo thứ tự xoay vòng, ta có thể dùng một mảng tổng dồn để tính trước.