Bài 2 THT bảng B, năm 2013

Tháp lũy thừa (power tower) hay lũy thừa lặp (iterated power) là một phép toán thường được
sử dụng để biểu diễn những giá trị rất lớn. Với hai số nguyên \(a\) và \(n\) \((a > 0, n \ge 0)\), tháp lũy thừa bậc \(n\) của \(a\) (kí hiệu \(a \uparrow \uparrow n\)) định nghĩa như sau:

• \(a \uparrow \uparrow n = 1\), nếu \(n = 0\)
• \(a \uparrow \uparrow n = a^{a \uparrow\uparrow n - 1} = a^{a^{...^{a}}}\) (\(n\) cấp), nếu \(n > 0\)

Ví dụ:

\(2 \uparrow\uparrow 1 = 2\)

\(2 \uparrow\uparrow 2 = 2^2 = 4\)

\(2 \uparrow\uparrow 3 = 2^{2^2} = 2^4 = 16\)

\(2 \uparrow\uparrow 4 = 2^{2^{2^2}} = 2^{16} = 65536\)

\(3 \uparrow\uparrow 3 = 3^{3^3} = 3^{27} = 7625597484987\)

Yêu cầu: cho ba số nguyên dương \(a, n, m\), hãy cho biết số dư trong phép
chia \((a \uparrow\uparrow n)\) cho \(m\).

Input

• 3 số nguyên dương \(a, n, m (a, n, m \le 10^6)\)

Output

• Kết quả bài toán

Example

2 4 100

36

11 2 100

11