【模板】扩展欧拉定理
题目描述
求 $a^b\mod m$ 。
输入输出格式
输入格式
一行三个正整数 $a,m,b$ 。
输出格式
一个整数表示答案。
输入输出样例
输入样例 #1
2 7 4输出样例 #1
2输入样例 #2
998244353 12345 98765472103312450233333333333输出样例 #2
5333说明
$50\%$ 的数据有：$1\le a\le 10^9,1\le m\le 10^6$，$a$ 和 $m$ 互质；其中一半的数据有 $1\le b\le 10^9$。
剩下的 $50\%$ 里，有一半的数据是随机生成的。
$100\%$ 的数据有：$1\le a,m\le 10^{12},1\le b\le 10^{20000000}$ 。