374 - Big Mod

計算 $R = B^P\mod{M}$

對相當大的 B、P、M 請寫一個有效率的演算法來。

Input

每筆測試資料有 3 行，各有 1 個整數分別代表 B、P、M。

其中 $0\leq{B,P}\leq{2147483647}, 1\leq{M}\leq{46340}$

Output

輸出計算的結果，每筆測試資料一行。

Sample Input

3
18132
17

17
1765
3

2374859
3029382
36123

Sample Output

13
2
13195