Problem Description

Given integers $N$, $M$, and $P$.

Compute the remainder when $N$ raised to the power of $P$ is divided by $M$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ P $

The first line contains the integers $N$, $M$, and $P$ separated by spaces, where $1 \leq N, M \leq 10^9$ and $1 \leq P \leq 10^{14}$.

Output Format

Output the remainder when $N$ raised to the power of $P$ is divided by $M$.

Sample Input and Output

Sample Input #1

12 15 7

Sample Output #1

3

Sample Input #2

123456789 234567894 6574837563712

Sample Output #2

120678297

Notes/Hints

Explanation

Repeated Squaring Method by AtCoder Inc.

Sample Explanation 1

$12$ raised to the power of $7$ is $35831808$. The remainder when this is divided by $15$ is $3$.

Sample Explanation 2

Numbers can become very large.

见题面 Input 部分

见题面 Output 部分