描述

求$a$的$b$次方对$p$取模的值，其中$1 \leq a,p \leq 10^9, 0 \leq b \leq 10^9$.

输入

输入$a,b,p$

输出

输出结果

样例

1 2 3

1

数据范围

1s, 1024KiB for each test case.