Modular Exponentiation

You are given three positive integers, a, m, and b. Your task is to compute the value of \(a^b \bmod m\).

Please note that the computation might be large, so you should use an efficient algorithm (such as fast modular exponentiation) to solve the problem.

inputFormat

The input consists of a single line containing three positive integers a, m, and b separated by spaces.

\(1 \leq a, m, b \leq 10^{9}\)

outputFormat

Output the value of \(a^b \bmod m\).

sample

2 5 3

3