#P3035. 【模板】扩展欧拉定理

【模板】扩展欧拉定理

说明

给你三个正整数,a,m,ba,m,b,你需要求:abmodma^b \bmod m

输入格式

一行三个整数,a,m,ba,m,b

输出格式

一个整数表示答案

样例

输入数据 1

2 7 4

输出数据 1

2

样例

输入数据 2

998244353 12345 98765472103312450233333333333

输出数据 2

5333

提示

注意输入格式,a,m,ba,m,b 依次代表的是底数、模数和次数

【样例 11 解释】
24mod7=22^4 \bmod 7 = 2

【数据范围】
对于 100%100\% 的数据,1a1091\le a \le 10^91b10200000001m1081\le b \le 10^{20000000},1\le m \le 10^8