Description

You are given three positive integers $a$, $m$, and $b$. You need to compute: $a^b \bmod m$.

Input Format

One line with three integers, $a,m,b$.

Output Format

Output one integer representing the answer.

2 7 4

2

998244353 12345 98765472103312450233333333333

5333

Hint

Pay attention to the input format: $a,m,b$ represent the base, the modulus, and the exponent, in this order.

[Sample $1$ Explanation]
$2^4 \bmod 7 = 2$.

[Constraints]
For $100\%$ of the testdata, $1\le a \le 10^9$, $1\le b \le 10^{20000000}$, $1\le m \le 10^8$.

Translated by ChatGPT 5