题目描述

在信息安全课程中，小明学习了 RSA 加密算法的基础。其中最核心的运算是对大数进行模幂运算。现在给定三个整数 $a, b, p$，请你帮小明计算 $a^b \bmod p$ 的值。

输入格式

输入一行，包含三个整数 $a, b, p$，用空格分隔。

输出格式

输出一行，格式为 a^b mod p=s，其中 $a, b, p$ 为输入的原值，$s$ 为 $a^b \bmod p$ 的结果。

样例

2 10 9

2^10 mod 9=7

提示

数据范围

对于 $100\%$ 的数据，$0 \le a, b \lt 2^{31}$，$a + b \gt 0$，$2 \le p \lt 2^{31}$。