#include<bits/stdc++.h>
using namespace std;
int f(int a,int b,int p){
	if(b==1)return a%p;
	if(b%2==0){
		int l=f(a,b/2,p);
		return l*l%p;//当它是偶数时(a^(b/2))^2)
	}else{
		return f(a,(b-1)/2,p)*f(a,(b+1)/2,p)%p;//当它是奇数时（(a^(b-1)/2)*(a(b+1)/2)） 
	}/*
	2 3
	(2 1) * (2 2)
	(2)  *  (2 1 * 2 1)
	(2)  *  (2 * 2)*/
}
int main()
{
	long long a,b,sum=1,p;
	scanf("%lld%lld%lld",&a,&b,&p);
	if(p==1||b==0)cout<<a<<"^"<<b<<" mod "<<p<<"="<<1;
	cout<<a<<"^"<<b<<" mod "<<p<<"="<<f(a,b,p);
	return 0;
}

评测记录