A^B mod C

Problem Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<=1000000000).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

Sample Output

#include
  
   
__int64 power(__int64 a,__int64 b,__int64 c)
{
	__int64 ans=1;
	while(b)
	{
		if(b&1)  //当b为奇数时
		{
			ans=(ans*a)%c;   // a的99次方的等于a的49次方的平方，还要再乘以a
			b--;
		}
		b/=2;   //二分
		a=a*a%c;    //  a的98次方的等于a的49次方的平方
	}
	return ans;
	
}
int main()
{
	long  a,b,c;
	while(scanf("%ld%ld%ld",&a,&b,&c)!=EOF)
	{
	
		printf("%ld\n", power(a,b,c));
	}
	return 0;
}