背景

demon学长正在打一场算法比赛，遇到了一个简单题：给定 $a, b, m$，求 $a^b \bmod m$。他信心满满地用 Python 写了个循环，结果直接 TLE 了……

"我靠，$b$ 居然是 $10^9$ 级别的？Python 不是号称大数运算很快吗？？"

冷静下来后，demon学长突然想起大一计组课上老师讲过的原码、反码、补码——计算机里所有的数都是用二进制表示的！既然指数可以写成二进制，那能不能用这个来加速计算呢？

你能帮帮他吗？

描述

给定三个整数 $a, b, m$，计算 $a^b \bmod m$ 的值。

输入格式

一行三个整数 $a, b, m$。

输出格式

一行一个整数，表示 $a^b \bmod m$ 的结果。

样例

2 10 1000

24

3 0 7

1

限制

$0 \le a, b \le 10^9$，$1 \le m \le 10^9$。

对于 $30\%$ 的数据，$b \le 10^6$。

对于 $100\%$ 的数据，$b \le 10^9$。

提示：$b$ 的二进制表示最多只有 $30$ 位。试试看能不能用这个来加速？