Description

村庄发生了袭击，袭击者不知道是谁，聪明的村民又双叒叕猜到了是玩家搞的。玩家告诉他们一个事实，如果村民们平均涨价$a$，最高涨价$b$，最低涨价$m$，自己的打折机就会给他们打折$a^b~ {\tt mod}~ m$次。

村民们想知道自己在平均涨价涨价$a,$最高涨价$b,{\tt 最低涨价}m$的情况下要被打折多少次。

Format

Input

输入a,b,m

Output

输出结果

Samples

2 2 3

1

Limitation

$1<=a,b,m<=10^{15}$

注意！！！这题只给5ms

subtask1:卡各种极限

subtask2:正常数据