【模板】扩展欧拉定理

题目描述

求 $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}$ 。