Binary Exponentiation - Classic Problems | Repovive

CLS9. Binary Exponentiation

1s256 MB

Given integers $x$ , $n$ , and $m$ , compute $x^n \mod m$ using fast exponentiation.

$x \quad n \quad m$

$x^n \mod m$

Input

2 10 1000

Explanation

For this input, the required output is 24.

Output

Input

3 5 100

Explanation

For this input, the required output is 43.

Output

Input

2 0 1000000007

Explanation

For this input, the required output is 1.

Output

Given integers $x$ , $n$ , and $m$ , compute $x^n \mod m$ using fast exponentiation.

$x \quad n \quad m$

$x^n \mod m$