题目描述

《快速模幂》

给你三个整数a,b,p，求 a^b mod p。

输入格式

输入只有一行三个整数，分别代表 a,b,p。

输出格式

输出一行一个字符串 a^b mod p=s，其中 a,b,p分别为题目给定的值，s 为运算结果。 对于 100%的数据，保证 0≤a,b<2^31 ，a+b>0，2≤p<2^31 。

样例

输入样例 1

2 10 9

输出样例 1

2^10 mod 9=7

输入样例 2

2 10 100

输出样例 2

2^10 mod 100=24

输入样例 3

5 0 7

输出样例 3

5^0 mod 7=1