FASTPOW - Fast Power

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

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

hide comments
2021-05-24 05:25:47 [Lakshman]
@phoenix_0 why are using mod = 1000000007?. you have to answer again % c, not 1000000007. Check this https://ideone.com/w4GUIm
2021-05-23 22:08:17
https://ideone.com/6bio2z
can anybody help, plz...
2018-02-28 12:02:31
First I used int ..it didn't work then i used unsigned long long int and it worked!!!
2015-01-07 14:57:03 :.Mohib.:


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


Last edit: 2013-08-12 04:26:40
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.