题目描述

小码哥正在学习快速幂算法，他现在想要求出$a^b \ mod\ p$的值，你能帮帮他吗？

输入格式

输入一行$3$个整数$a,b,p$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

2 3 7

样例输出 #1

1

说明/提示

有$0\leq a,b<2^{31},a+b>0,2\leq p<2^{31}$。