反正各种数学证明，我就不说了。主要是数学符号打不出来。
#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;
}