### 问题描述 在古老的阿尔法大陆，有一个被称为“费马的遗物”的神秘物品。据传闻，这个遗物是费马大师亲手制作的神秘计算器。阿尔法大陆的居民们相信，它可以预测未来、解决困境、甚至改变命运。但要启动这个神秘的遗物，需要快速求出密码，由于人力运算速度不够快，你希望能够借助计算机来快速完成计算。 现在给定三个正整数 $a, b, p$，其中 $p$ 是一个质数，目的是求 $a^b \mod p$ 的值。成功计算出这个值可能是启动“费马的遗物”的关键。 ### 输入格式 一行三个整数 $a, b, p$ 。其中 $1 \leq a, b \leq 10^9$ ，$2 \leq p \leq 10^7$ 且 $p$ 是质数。 ### 输出格式 输出一个整数，表示 $a^b \mod p$ 的值。 ### 样例输入 ``` 3 4 5 ``` ### 样例输出 ``` 1 ``` ### 样例说明 在古老的文献中，有这样的描述：当输入为 $3, 4, 5$ 时，遗物的魔法公式得出 $3^4 = 81$ ，然后计算 $81 \mod 5 = 1$。因此，输出结果为 $1$。 ### 测评数据规模 $1 \leq a, b \leq 10^9$，$2 \leq p \leq 10^7$，且 $p$ 是质数。