Big Mod

Calculate
R:=B^P
mod M, meaning remainder R when B raised to the power of P is divided by M.
for large values of B, P, and M using an efficient algorithm.
(That's right, this problem has a time dependency !!!.)

Input

Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.

Output

The result of the computation. A single integer.

Sample Input

3
18132
17

17
1765
3

2374859
3029382
36123

Sample Output

13
2
13195

// Big-Mod.cpp : Defines the entry point
for the console application.

//

 

#include "stdafx.h"

int _tmain(int argc, _TCHAR* argv[])
{
                void
bigmod(long int x,long int y,long int z);
                long int B,P,M;
                while(cin>>B)
                {
                                cin>>P;
                                cin>>M;
                                bigmod(B,P,M);
                }
                return 0;
}
void bigmod(long int x,long int y,long int z)
{
                int pow,rem;
                rem=x%z;
                for(pow=1;pow<y;pow++)
                {
                                rem=(rem*(x%z))%z;
                }
                cout<<rem<<endl;
}