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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mars_Dingdang

题目描述

给定 a,b,m ,求 a^b\bmod m

注意 a,m 不一定互质。数据略大,请采用恰当的读入方式

\color{white}{a^b ≡a^{(b\bmod φ(m)) + φ(m)}\pmod m}

由于 SYZOJ 对于 \rm{\LaTeX} 的 feature,如果你使用的是 Google Chrome,你可以使用 F12 打开源代码,选择左上角的 Select 工具,点击上方空白行,展开网页代码得到提示公式。当然你也可以直接抄题解。

输入格式

一行三个数 a,m,b ,注意顺序。

输出格式

一行一个正整数表示答案。

样例

Input:

3 7 4 

Output:

4

Input 2:

998244353 12345 98765472103312450233333333333

Output 2:

5333

数据范围与提示

样例一中, 3^4 = 81 81\bmod 7≡4

对于全部数据, 1\le a\le 10^9,1\le m\le 10^8,1\le b\le 10^{1000000}