Description

Given three integers $a$, $b$, $p$, compute $a^b \bmod p$.

Input Format

The input contains a single line with three integers representing $a$, $b$, $p$.

Output Format

Output one line with the string a^b mod p=s, where $a$, $b$, $p$ are the given values and $s$ is the result.

2 10 9

2^10 mod 9=7

Hint

Sample Explanation:

$2^{10} = 1024$，$1024 \bmod 9 = 7$.

Constraints:

For $100\%$ of the testdata, it is guaranteed that $0 \leq a, b < 2^{31}$, $a + b > 0$, $2 \leq p \lt 2^{31}$.

Translated by ChatGPT 5