#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <stdlib.h>#include <time.h>#define LL __int64 using namespace std;LL e,n,c,p,q,f;int cnt;LL prime[10];LL gcd(LL a,LL b){	if(b==0) return a;	return gcd(b,a%b);}LL random(LL nc){	return (LL)((double)rand()/RAND_MAX*nc+0.5);}LL multi(LL a,LL b,LL m){	LL ret=0;	while(b>0){		if(b&1)		ret=(ret+a)%m;		b>>=1;		a=(a<<1)%m;	}	return ret;}LL quick(LL a,LL b,LL m){	LL ans=1;	a%=m;	while(b){		if(b&1)		ans=multi(ans,a,m);		b>>=1;		a=multi(a,a,m);	}	return ans;}LL witness(LL a, LL nc){	LL m=nc-1;	int j=0;	while(!(m&1)){		j++;		m>>=1;	}	LL x=quick(a,m,nc);	if(x==1||x==nc-1)	return false;	while(j--){		x=multi(x,x,nc);		if(x==nc-1)		return false;	}	return true;}bool miller_rabin(LL nc){	if(nc<2) return false;	if(nc==2) return true;	if(!(nc&1)) return false;	for(int i=1;i<=10;i++){		LL a=random(nc-2)+1;		if(witness(a,nc)) return false;	}	return true;}LL pollard_rho(LL nc,int inc){	LL x,y,d,i=1,k=2;	x=random(nc-1)+1;	y=x;	while(1){		i++;		x=(multi(x,x,nc)+inc)%nc;		d=gcd(y-x,nc);		if(d>1&&d<nc)		return d;		if(y==x)		return nc;		if(i==k){			y=x;			k=(k<<1);		}	}}bool  find(LL nc,int k){	if(nc==1)	return false;	if(miller_rabin(nc)){		p=nc;		return true;	}	LL pe=nc;	while(pe>=nc)	pe=pollard_rho(pe,k--);	if(find(pe,k)) return true;;	if(find(nc/pe,k)) return true;;}void exgcd(LL a,LL b,LL &x,LL &y){	if(b==0){		x=1; y=0;		return ;	}	exgcd(b,a%b,x,y);	LL tmp=x;	x=y;	y=tmp-a/b*y;}int main(){	LL x,y;	while(scanf("%I64d%I64d%I64d",&c,&e,&n)!=EOF){		srand(time(0));		cnt=0;		find(n,201);		q=n/p;		f=(p-1)*(q-1);		exgcd(e,f,x,y);		x=(x%f+f)%f;		LL ans=quick(c,x,n);		printf("%I64d\n",ans);	}	return 0;}