快速幂取模问题

题目描述

求 $a$ 的 $b$ 次方对 $p$ 取模的值。

输入格式

三个整数 $a, b, p$，在同一行用空格隔开。

输出格式

输出一个整数，表示 $a^b \bmod p$ 的值。

输入输出样例 #1

输入 #1

3 2 7

输出 #1

2

输入输出样例 #2

输入 #2

123456789 987654321 1000000007

输出 #2

370471672

限制条件

• $0 \le a, b \le 10^9$
• $1 \le p \le 10^9$
• 所有输入均为整数

样例解释 #1

$3^2 = 9$，$9 \bmod 7 = 2$，因此输出 $2$。