# Binary Exponentiation

Given 3 numbers

`x`

, `n`

, and `m`

, you are asked to calculate the result of

. Input

The only line of the input contains 3 integers

`x`

, `n`

, and `m`

(1 β€ x, n, m β€ ). Output

The program should print the result of the

expression. Examples

Input | Output |

2 10 5 | 4 |

Explanation

- 2^10 = 1024 β 1024 mod 5 = 4

Β

Tutorial

As all the numbers are pretty large, we need to use a fast algorithm to make sure itβs quick enough. 1. Binary exponentiation is an efficient way of computing large powers of a number. It reduces the number of multiplications required to compute the power, which makes it faster than the traditional method of looping from 1 through

`n`

and multiplying the result by `x`

.Β

The binary exponentiation algorithm is based on the following mathematical observation: if we have a number

`x`

raised to the power of `n`

, then

can be represented as:`if`

`n`

is even

`if`

`n`

is odd

This actually makes the process of calculating the way faster as we can calculate the

once and then multiply the result twogether. So, the algorithm can look like this:```
def binpow(x, n, m):
if n == 0: # Base case: x^0 = 1
return 1
if n % 2 == 0: # n is even => calculate half and multiply
half = binpow(x, n // 2, m) # calculate the half
return (half * half) % m # res = x^(n/2) * x^(n/2)
# n is odd => res = x * x^(n-1)
return (x * binpow(x, n - 1, m)) % m
```

With binary exponentiation, we reduce the time complexity from operations to as we split

`n`

on every iteration where `n`

is even. Itβs important to note that for each operation where `n`

is odd, for the next iteration `n`

is even.Letβs simulate the algorithm on several inputs:

`x = 2`

, `n = 10`

(we discard `m`

for simplicity)

- [n = 10] β n % 2 == 0 β calculate binpow(2, 5)

- [n = 5] β n % 2 β 0 β return 2 * binpow(2, 4)

- [n = 4] β n % 2 == 0 β calculate binpow(2, 2)

- [n = 2] β n % 2 == 0 β calculate binpow(2, 1)

- [n = 1] β n % 2 β 0 β return 2 * binpow(2, 0)

- [n = 0] β n == 0 β return 1

- [up to n = 1] β return 2 * 1 = 2

- [up to n = 2] β return 2 * 2 = 4

- [up to n = 4] β return 4 * 4 = 16

- [up to n = 5] β return 2 * 16 β 32

- [up to n = 10] β return 32 * 32 = 1024

Β

Β

#### Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB