AT_atc002_b n^p mod m

[problemUrl]: https://atcoder.jp/contests/atc002/tasks/atc002_b 整数 $ 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 $ で割ったあまりを出力せよ。

### 解説 **[繰返し二乗法](//www.slideshare.net/secret/5WFErY1jizuEOP "繰返し二乗法")** from **[AtCoder Inc.](//www.slideshare.net/chokudai)** ### Sample Explanation 1 $ 12 $ の $ 7 $ 乗は $ 35831808 $ になります。これを $ 15 $ で割った余りは $ 3 $ です。 ### Sample Explanation 2 数が非常に大きくなることもあります。