Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Exponenciació modular P29212

Statement

html

Feu un programa que, donats n, k i m, calculi n^k modm.

Entrada

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

Sortida

Per a cada cas, escriviu n^k modm.

Public test cases

Input

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

Output

Information