题目描述

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

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

输入格式

三个正整数 $x,p,m$，都在 int 范围内。

输出格式

参考样例。

2 10 100

2^10 mod 100=24