A的B次方取余数

题目描述

求 $A^B$ 除以$C$ ，剩下的余数是多少

输入格式

三个正整数 $A$，$B$ ,$C$。

$1 \le A \le 100$

$1 \le B \le 10000$

$10 \leq C \leq 50000$。

提示：直接算$A^B$ 会超出数据类型的范围，取余运算有个特性，对每个计算过程取余数等价于对最终结果取余数。

AxAxAxAxA%C=(A%CxA%CxA%CxA%CxA%C)%C

输出格式

输出一个整数

样例 #1

样例输入 #1

2 3 2

样例输出 #1

0