5252 - 快速幂  

通过次数

3

提交次数

15

Time Limit : 1 秒
Memory Limit : 256 MB

  给定A, B, P,求(A^B) mod P。

Input

  输入共一行。
  第一行有三个数,N, M, P。

Output

  输出共一行,表示所求。

Examples

Input

2 5 3

Output

2

Hint

数据规模和约定

  共10组数据
  对100%的数据,A, B为long long范围内的非负整数,P为int内的非负整数。

Source

蓝桥杯提高