#include<bits/stdc++.h>
#define LL long long
int d=0;
LL a,n,k,ans=1,prime[10000];;
inline const void get_prime()
{
	bool pp;
	for(LL i=2;i<=sqrt(a);i++)
	{	
		pp=true;
		for(LL j=1;j<=d;j++)
		{
			if(!(i%prime[j]))
			{
				pp=false;
				break;
			}
		}
		if(pp)prime[++d]=i;
	}
}
inline const LL fast_pow(LL x,LL y)
{
	LL base=x,ans=1,r=y;
	while(r)
	{
		if(r&1)ans=ans*base%k;
		r=r>>1;base=base*base%k;
	}
	return ans;
}
LL factor[10000];
int tot=0;
inline const void resolve()
{
	for(int i=1;i<=d;i++)
	{
		if(a==1)break;
		while(!(a%prime[i]))
		{
			a/=prime[i];
			factor[++tot]=prime[i];
		}
	}
}
int main()
{
	std::cin>>a>>n>>k;
	get_prime();
	resolve();
	LL ans=1;
	for(LL i=1;i<=(1<<tot)-1;i++)
	{	
		LL c=0,om=1;
		for(LL j=1;j<=tot;j++)
		{
			if(i&(1<<(j-1)))
			{	
				om*=factor[j];
				c^=1;
			}
		}
		if(c)ans=ans*fast_pow(om,n/om)%k;
		else ans=ans*fast_pow(fast_pow(om,n/om),k-2)%k;
	}
	std::cout<<ans;
	return 0;
}