题目描述

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

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

输入格式

三个不超过 int 的正整数 $x,p,m$。

输出格式

参考样例。

2 10 100

2^10 mod 100=24