問題文

整数 $N, M, P$ が与えられる。

$N$ の $P$ 乗を $M$ で割ったあまりを求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $P$

$1$ 行目には、整数 $N, M, P (1≦N,M≦10^{9}, 1≦P≦10^{14})$ が、スペース区切りで与えられる。

出力

$N$ の $P$ 乗を $M$ で割ったあまりを出力せよ。

解説

繰返し二乗法 from AtCoder Inc.

入力例 1

12 15 7

出力例 1

3

$12$ の $7$ 乗は $35831808$ になります。これを $15$ で割った余りは $3$ です。

入力例 2

123456789 234567894 6574837563712

出力例 2

120678297

数が非常に大きくなることもあります。