题目描述

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

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

输入格式

输入三个正整数 $x$、$p$、$m$，以空格隔开。

输出格式

输出 $x^p \bmod m$ 的值。

样例

2 10 100

24

数据范围与提示

$x, p, m$ 均不超过 $10000$。

来源

NOIP