请求帮助的哇QWQ

//看似没有问题，但又全是问题
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e9+7 ;
ll a,b,m;
int getint(){       //快读？
    int res=0,ch=getchar();
    while(!isdigit(ch) and ch != EOF)
        ch=getchar();
    while(isdigit(ch)){
        res=(res<<3)+(res<<1)+(ch-'0');
        res%=N;
        ch=getchar();
    }
    return res;
}
int euler(ll n){        //浅浅求个欧拉？
	int ans=n;
	for(int i=2;i*i<=n;++i){
		if(n%i==0){
			ans=ans*(i-1)/i;
			while(n%i==0) n/=i;
		}
	}
	if(n!=1) ans=ans/n*(n-1);
	return ans;
}
int poww(ll b,ll e){        //浅浅幂一下
	int a=1;
	for(;e;e>>=1,b=b*b%m)
		if(e&1)a=a*b%m;
	return a;
}
int main(){
	a=getint();
	m=getint();
	b=getint();
	ll fm=euler(m); 
	ll d=b%fm+fm;
	ll ans=poww(a,d);
	cout<<ans<<endl;
	return 0;
}