1616：A 的 B 次方

题目描述

给出三个整数 $a, b, m$，求 $a^b \bmod m$ 的值。

输入格式

一行三个整数 $a, b, m$。

输出格式

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

样例

样例输入 #1

2 100 1007

样例输出 #1

169

样例解释 #1

计算 $2^{100} \bmod 1007$ 的值。

$2^{100}$ 是一个非常大的数，直接计算会溢出，因此需要用快速幂算法在取模意义下计算。

$2^{100} \bmod 1007 = 169$。

数据范围

对于全部数据：

• $1 \le a, b, m \le 10^9$

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：本题是快速幂取模的模板题。由于 $b$ 可能很大，需要用 $O(\log b)$ 的快速幂算法。基本思想：将 $b$ 表示为二进制，例如 $b = \sum 2^i$，则 $a^b = \prod a^{2^i}$。在计算过程中每一步都取模，避免溢出。注意 $m$ 可能为 $1$，此时结果恒为 $0$（因为任何数模 $1$ 为 $0$）。