#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Binary Exponentiation - Classic Problems | Repovive

CLS9. Binary Exponentiation

1s256 MB

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

Constraints

$0 \le x \le 10^9$
$0 \le n \le 10^9$
$1 \le m \le 10^9 + 7$

Input

$x \quad n \quad m$

Output

$x^n \mod m$

Samples

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.

$0 \le x \le 10^9$
$0 \le n \le 10^9$
$1 \le m \le 10^9 + 7$

$x \quad n \quad m$

$x^n \mod m$