说明

求 $x^p\ mod \ m$ 的值。 提示：若 $p$ 为偶数，$x^p = (x^2)^{\frac p 2}$；若 $p$ 为奇数，$x^p = x\times (x^2)^{\frac {p-1} 2}$，该题可以采用分治法求解。

输入格式

三个不超过 $10,000$ 的正整数 $x，p，m$。

输出格式

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

样例

2 10 100

24

提示

NOIP2017普及组初赛