【模板】快速幂||取余运算

题目描述

给你三个整数 $b,p,k$,求 $b^p \bmod k$。

输入输出格式

输入格式


一行三个整数 $b,p,k$

输出格式


输出 `b^p mod k=s` $s$ 为运算结果

输入输出样例

输入样例 #1

2 10 9

输出样例 #1

2^10 mod 9=7

说明

【样例解释】 $2^{10} = 1024$,$1024 \bmod 9 = 7$。 【数据范围】 对于 $100\%$ 的数据,$0\le b,p,k < 2^{31}$。