FASTPOW - Fast Power

no tags 

You are asked to compute A^B (A to the power of B) (1 <= A,B <= 100 000 000). You surely understand that this number can be quite astonishing and i don't like big numbers unless they are on my paycheck so I'm just interested in the reminder of A^B mod C (1<= C <= 1000000)

Input

Three integers A B and C.

Output

Single integer - the result of the computation.

Example

Input:
2 10 1000

Output:
24

hide comments
prashant_pc: 2018-02-28 12:02:31

First I used int ..it didn't work then i used unsigned long long int and it worked!!!

:.Mohib.:: 2015-01-07 14:57:03

Last edit: 2015-07-25 20:45:43
John and the cows: 2013-08-11 13:38:07

Last edit: 2013-08-12 04:26:40

Added by:Nikola P Borisov
Date:2008-11-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET