RT,AC4 WA27

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,x,m;
int ksm(int a,int b,int p){
	int ans=1;
	while(b){
		if(b&1)
		ans=(ans%p)*(a%p);
		b>>=1;
		a=(a*a)%p;
	}
	return ans%p;
}
int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	int ret=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return ret;
}
int get(int a,int mod){
	int x,y;
	int d=exgcd(a,mod,x,y);
	return d==1?(x%mod+mod)%mod:-1;
}
signed main(){
	scanf("%lld%lld%lld",&a,&x,&m);
	int k=ksm(a,x-1,m);
	int c=get(a-1,m);
	printf("%lld\n",((k%m)*(c%m))%m);
	return 0;
}