No.181 A↑↑N mod M

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 30
作問者 : ぴろずぴろず
3 ProblemId : 472 / 出題時の順位表

問題文

$(A \upuparrows N) \; {\rm mod} \; M$を求めよ。
ただし、整数$a>0,n \geq 0$に対して$a \upuparrows n$を次のように定義する。

$\displaystyle a \upuparrows n = \begin{cases} 1 & (n = 0) \\ a^{(a \upuparrows (n-1))} & (otherwise) \end{cases}$

入力

$A$ $N$ $M$

1行目に3つの整数$A$,$N$,$M$がスペース区切りで与えられる。

$1 \leq A \leq 10^9$
$0 \leq N \leq 10^9$
$1 \leq M \leq 2000$

出力

$A \upuparrows N$を$M$で割った余りを1行に出力し、改行せよ。

サンプル

サンプル1
入力
3 2 100
出力
27

$3^{3^1} = 27 \equiv 27 \; (\rm mod \; 100)$ なので$27$が答えとなる。

サンプル2
入力
3 3 100
出力
87

$3 \upuparrows 3 = 3 ^ {3 \upuparrows 2} = 3 ^ {27} = 7625597484987 \equiv 87 \; (\rm mod \; 100)$ なので$87$が答えとなる。

サンプル3
入力
3 1000000000 2
出力
1

$3 \upuparrows n$がすべての整数$n(\geq 0)$について奇数であることが言える。

サンプル4
入力
87654321 0 1234
出力
1

$87654321 \upuparrows 0 = 1$

サンプル5
入力
1777 1855 1000
出力
97

サンプル6
入力
17893463 90476513 1458
出力
1091

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。