题目描述

求 $x^p\ mod\ m$ 的值。（ $mod$ 代表取余数）

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

输入

$x$， $p$ 是不超过 $10^9$ 的非负整数， $m$ 是不超过 $10^9$ 的正整数。

输出

$x^p\ mod\ m$ 值。

样例

2 10 100

24

说明

NOIP2017普及组初赛