#1414. 【模板】快速幂

【模板】快速幂

Description

给你三个数 a,b,pa,b,p,请计算 abmodpa^b \bmod p 的值。

Format

Input

一行三个数 a,b,pa,b,p

Output

一行一个数,为 abmodpa^b \bmod p 的值。

Samples

5 3 7
6

Limitation

数据范围:0a,b<2310\leqslant a,b< 2^{31}a+b>0a+b>02p<2312\leqslant p< 2^{31}