Đị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.