eolymp
bolt
Try our new interface for solving problems
Problems

Modular Exponentiation

Modular Exponentiation

Time limit 1 second
Memory limit 128 MiB

Find the value of the expression x^n~mod~m.

Input data

Three positive integers x, n, m~(1 \le x, n \le 10^9, 2 \le m \le 10^9).

Output data

Print the value of x^n~mod~m.

Examples

Input example #1
2 3 100
Output example #1
8