Exponenciació modular P29212

Statement

Feu un programa que, donats $n$ , $k$ i $m$ , calculi $n^k \bmod m$ .

Entrada

L’entrada consisteix en diversos casos, cadascun amb tres naturals $n$ , $k$ i $m$ . Assumiu $2 \le n \le 30000$ i $2 \le m \le 30000$ .

Per a cada cas, escriviu $n^k \bmod m$ .

Public test cases

Input

2 10 10000
2 10 2
7 1000000 29999
7 1000000 30000
30000 1000000000 29876

Output

Information