Modular Exponentiation

Interview

Time limit0.5sMemory limit128 MB

Summary

Compute A raised to the power B modulo C efficiently using fast modular exponentiation.

Level: Easy3 of 10
Topics: Math, Number theory, Recursion
Solved: No attempts yet

Problem

Given natural numbers A, B, and C, compute the remainder when A^B is divided by C. The value of A^B can be very large, so compute the remainder efficiently.

Input

The first line contains A, B, and C separated by spaces. Each of A, B, and C is a natural number not greater than 2,147,483,647.

Output

Print the remainder when A^B is divided by C.

Examples1

Example 1
Input
```
10 11 12
```
Expected output
```
4
```