注意：2↑↑nを解いていない場合はそちらを先に解くことをお勧めします。

問題文

$\uparrow\uparrow$をクヌースの矢印表記を用いたテトレーションとする。$a\uparrow\uparrow n$を$m$で割った余りを求めよ。

制約

• $1\leq a,n,m\leq10^{9}$
• 入力は全て整数

入力

入力は以下の形式で与えられる。$\\$

a n m

出力

計算結果を1行に出力せよ。

サンプル

2 3 5

1

$2\uparrow\uparrow 1=2,\ 2\uparrow\uparrow 2=2^{2\uparrow\uparrow 1}=4,\ 2\uparrow\uparrow 3=2^{2\uparrow\uparrow 2}=16$となります。

2 6 998244353

220050301

2↑↑nの解説より、$a=2,n\geq6,m=998244353$ならば答えは$220050301$となります。

3 9 10

7

2016年東大文系数学第4問と同じです。