题目描述

一座能量塔的初始能量为 A。
每进行一次充能操作，能量都会按照如下规则变化：

其中：

• $E_i$ 表示第 $i$ 次操作后的能量值
• $\bmod M$ 表示对 $M$取模

请你计算在进行 B 次充能操作后，能量塔的最终能量值。

输入格式

一行三个整数：A B M

输出格式

输出一个整数，表示最终的能量值。

数据范围

• $0 \le A < M \le 10^9 + 7$
• $0 \le B \le 10^{6}$

样例输入输出

3 4 100

21

样例解释

$E_0 = 3$

$E_1 = 3^2 \bmod 100 = 9$

$E_2 = 9^2 \bmod 100 = 81$

$E_3 = 81^2 \bmod 100 = 61$

$E_4 = 61^2 \bmod 100 = 21$

###此题极水，有时间记得重新设计测试点