普及⏱ 1000ms💾 256MB#P5134🏷️ 分治数学

题目描述

密码学兴趣课的第一讲是模运算:老师给出一组 $b, p, k$, 要求计算 $b^p \bmod k$ 的值——即 $b$ 的 $p$ 次幂再除以 $k$ 的余数。

按指定格式输出计算结果。

输入格式

一行,三个整数 $b, p, k$,用空格分开(均为长整型数范围内的数,且 $k \times k$ 也在长整型范围内)。

输出格式

一行,严格按 b^p mod k=值 的格式输出(等号两边均无空格)。

数据范围

$b, p, k$ 为长整型范围内的非负数,且 $k \times k$ 不溢出。

样例输入 #1
2 10 9
样例输出 #1
2^10 mod 9=7
样例输入 #2
3 5 7
样例输出 #2
3^5 mod 7=5