Modular exponentiation P29212

Statement

Write a program that, given $n$ , $k$ and $m$ , computes $n^k \bmod m$ .

Input

Input consists of several cases, each one with three natural numbers $n$ , $k$ and $m$ . Assume $2 \le n \le 30000$ and $2 \le m \le 30000$ .

For every case, print $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