【模板】欧拉定理

题目背景

出题人也想写有趣的题面,可惜并没有能力。

题目描述

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

输入输出格式

输入格式


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

输出格式


一个整数表示答案

输入输出样例

输入样例 #1

2 7 4

输出样例 #1

2

输入样例 #2

998244353 12345 98765472103312450233333333333

输出样例 #2

5333

说明

注意输入格式,$a,m,b$ 依次代表的是底数、模数和次数 **样例1解释:** $2^4 \bmod 7 = 2$ 输出`2` **数据范围:** 对于全部数据: $1≤a≤10^9$ $1≤b≤10^{20000000}$ $1≤m≤10^6$