Description

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

Format

Input

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

Output

输出一行一个字符串 a^b mod p=s，其中 a,b,p 分别为题目给定的值， s 为运算结果。

Samples

2 10 9

2^10 mod 9=7

#样例解释 2^10=1024，1024mod9=7。

Limitation

对于 100% 的数据，保证 0≤a,b<2^31 ，a+b>0，2≤p<2^31