说明

求$x^p$ $mod$ $m$ 的值

提示：若 $p$ 为偶数，$x^p=(x^2)^{p/2}$；若 p 为奇数，$x^p=x*(x^2)^{(p-1)/2}$，该题可以采用分治法求解。

输入格式

三个不超过 10000 的正整数$x，p，m$

输出格式

$x^p$ $mod$ $m$ 的值。

样例

2 10 100

24

来源

NOIP2017普及组初赛