B - n^p mod m Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

整数 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 で割ったあまりを出力せよ。

解説

入力例 1

12 15 7

出力例 1

3

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

入力例 2

123456789 234567894 6574837563712

出力例 2

120678297

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