n^p mod m

题意翻译

求 $n^p$ $mod$ $m$ 的值 # 输入格式一行，为整数 n,m,p(注意顺序) # 输出格式一行，为 $n^p$ $mod$ $m$ 的值 # 数据说明对于100%的数据 $1≤n,m≤10^9$ $1≤p≤10^{14}$ 翻译提供者：Ryan_wxn_

题目描述

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

输入输出样例

输入样例 #1

12 15 7

输出样例 #1

输入样例 #2

123456789 234567894 6574837563712

输出样例 #2

120678297

说明

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