1240 - Happy horidays!!!
テスター募集中！
Aphorismus
クリスマスには、すべての道が故郷へと向かう。
── マージョリー・ホームズ
問題
関数 $f(n, r)$ を整数$n \gt 0, r \ge 0$に対して次のように定義する。
$\displaystyle f(n, r) = \begin{cases}
1 & (r = 0) \\
a^{f(n,r-1)} & (otherwise)
\end{cases}$
この時$f(a,b)\; {\rm mod} \;m$を求めよ。
入力
a b m
出力
ans
制約
$1$ ≤ $n$ ≤ $10^9$$0$ ≤ $r$ ≤ $10^9$
$1$ ≤ $m$ ≤ $1.5 \times 10^3$
テストケース
例1
入力
3 2 1000
出力
27
$f(3, 2) = 3^3 \equiv 27 \pmod {1000}$
例2
入力
3 3 1000
出力
987
$f(3, 2) = 3^{3^3} \equiv 987 \pmod {1000}$
例3
入力
1825 1821 1333
出力
650
Happy hoRidays!!!