问题描述

输入整数$m，n，k$，求$m^n$ mod $k$的值。$m，n，k*k$为长整型范围内的自然数。

输入格式

输入一行3个整数，分别为$m，n$和$k$。

输出格式

输出一行一个整数，表示结果。

样例

2 10 9

7

来源

• 信息学奥赛之数学一本通
• stong9070整理