该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

古代密码

题目背景

在一次考古发掘中，噜噜和一只羊发现了一卷古老的羊皮卷。羊皮卷上记载了一种奇特的加密方法，用于在古代战争中传递秘密信息。这种方法被称为“乘方取模加密法”。

加密规则如下：将一个原始数（称为“底数” $A$）自乘 $B-1$ 次，得到它的 $B$ 次方，然后将这个结果对一个特定的数（称为“模数” $P$）取余数，最终得到的余数就是加密后的密文。

“一只羊”对这种古老的智慧非常着迷，它想请聪明的噜噜帮它实现一个计算器，来快速算出任意给定底数、指数和模数的加密结果。

问题描述

给定三个整数 $A, B, P$，请你计算 $A^B \pmod P$ 的值。

这里的 $A^B \pmod P$ 表示计算 $A$ 的 $B$ 次方，然后对 $P$ 取余数的结果。

输入格式

输入一行，包含三个整数 $A, B, P$，三个数之间用一个空格隔开。

输出格式

输出一个整数，表示 $A^B \pmod P$ 的结果。

样例输入与输出

样例输入 1

2 10 9

样例输出 1

7

样例 1 解释

$2^{10} = 1024$。 $1024 \pmod 9 = 7$。 （计算过程：$1024 = 9 \times 113 + 7$）

样例输入 2

3 0 100

样例输出 2

1

样例 2 解释

按照数学约定，$3^0 = 1$。 $1 \pmod {100} = 1$。

数据规模与约定

• 对于30% 的数据：$0 \le A, P \le 1000$, $0 \le B \le 10^5$。
• 对于另外30% 的数据：$0 \le A, P \le 10^9$, $0 \le B \le 10^{18}$。保证 $P > 1$。
• 对于最后的40% 的数据：$0 \le A, P \le 10^9$, $0 \le B \le 10^{18}$。 保证输入的 $A, B$ 为非负整数，$P$ 为正整数。