AtCoder Typical Contest 002

B - n^p mod m


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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

NP 乗を M で割ったあまりを求めよ。


入力

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

N M P

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

出力

NP 乗を M で割ったあまりを出力せよ。


入力例 1

12 15 7

出力例 1

3

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


入力例 2

123456789 234567894 6574837563712

出力例 2

120678297

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


Submit提出する