Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUPH008 - Power Mod

Given 3 integers x, n and k. Calculate the value of xn % k.

Input

THe only line contains three integers x, n, k  (0< k <=109 , n>=0, x>=0).

Output

The value of the expression

Example

Input:
2 8 5

Output:
1

Added by:Ha Minh Ngoc
Date:2015-01-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYTHON3 RUBY SQLITE SWIFT VB.NET
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.