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://atc002.contest.atcoder.jp/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

3

输入样例 #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 数が非常に大きくなることもあります。