题目描述

给定整数 $b,p,k$，计算 $b^p\bmod k$。本题约定 $b^0=1$，包括 $b=0$ 的情况。

输入格式

输入一行三个整数 $b,p,k$。

输出格式

按照 b^p mod k=结果 的格式输出一行。

样例

2 10 9

2^10 mod 9=7

数据范围

$0\le b,p\le2^{31}-1$，$1\le k\le46340$，即 $k^2$ 在32位有符号整数范围内。