题目描述

输人整数$\red{m,n,k,}$求$\red{m^n ~}$$\red{mod~}$$\red{k}$的值。$\red{m,n,k \times k }$为长整型范围内的自然数。

输入格式

输人一行$\red{3}$个整数,分别为$\red{m,n}$和$\red{k}$。

输出格式

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

样例

输入样例

2 10 9

输出样例

7