快速幂

题目描述

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

提示：
若 $p$ 为偶数，$x^p = (x^{p/2})^2$；
若 $p$ 为奇数，$x^p = x \times (x^{(p-1)/2})^2$。

该题可以采用分治法求解。

输入格式

一行三个整数 $x, p, m$。

其中：

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

输出格式

输出一个整数，表示 $x^p \bmod m$ 的值。

输入输出样例 #1

输入

2 10 100

输出

24

说明

noip2017 普及组初赛