No.181 A↑↑N mod M
ぴろずProblem Statement
Find $(A \upuparrows N) \; {\rm mod} \; M$.
Here, for integers $a>0,n \geq 0$, $a \upuparrows n$ is defined as follows.
$\displaystyle a \upuparrows n = \begin{cases}
1 & (n = 0) \\
a^{(a \upuparrows (n-1))} & (otherwise)
\end{cases}$
Input
$A$ $N$ $M$
The first line contains three space-separated integers $A$,$N$,$M$.
$1 \leq A \leq 10^9$
$0 \leq N \leq 10^9$
$1 \leq M \leq 2000$
Output
Output the remainder when $A \upuparrows N$ is divided by $M$ on one line, followed by a newline.
Sample
Sample 1
Input
3 2 100
Output
27
Since $3^{3^1} = 27 \equiv 27 \; (\rm mod \; 100)$, the answer is $27$.
Sample 2
Input
3 3 100
Output
87
Since $3 \upuparrows 3 = 3 ^ {3 \upuparrows 2} = 3 ^ {27} = 7625597484987 \equiv 87 \; (\rm mod \; 100)$, the answer is $87$.
Sample 3
Input
3 1000000000 2
Output
1
It can be shown that $3 \upuparrows n$ is odd for every integer $n(\geq 0)$.
Sample 4
Input
87654321 0 1234
Output
1
$87654321 \upuparrows 0 = 1$
Sample 5
Input
1777 1855 1000
Output
97
Sample 6
Input
17893463 90476513 1458
Output
1091
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。