题意：中文题自己看吧
分析：这题分两步
第一步：利用已知公式求出k；
第二步：求出k然后使用欧拉降幂公式即可，欧拉降幂公式不需要互质（第二步就是BZOJ3884原题了）
求k的话就需要构造了（引入官方题解）
然后就求出k了，我就很奇怪为什么是这个式子，然后就网上搜啊搜
找到了一个推导（看完了以后恍然大悟）
推导链接：http://blog.****.net/wust_zzwh/article/details/51966450
高度仰慕数学好的巨巨
吐槽：这个题n是无平方因子，然后就要往欧拉函数是积性函数的性质上想，但是主要是还是要多做数学题
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <stack>
#include <map>
using namespace std;
typedef long long LL;
const int N = 1e7+;
const int mod=1e9+;
bool check[N];
LL phi[N],prime[N>>],tot;
LL sum[N],k,n,m,p;
LL qpow(LL a,LL b,LL mod){
LL ret=;
while(b){
if(b&)ret=(ret*a)%mod;
a=(a*a)%mod;
b>>=;
}
return ret;
}
void getphi(){
phi[]=;tot=;
for(int i=;i<=N-;++i){
if(!check[i]){
prime[++tot]=i;
phi[i]=i-;
}
for(int j=;j<=tot;++j){
if(i*prime[j]>N-)break;
check[i*prime[j]]=true;
if(i%prime[j]==){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else phi[i*prime[j]]=phi[i]*(prime[j]-);
}
}
for(int i=;i<=N-;++i){
sum[i]=(sum[i-]+phi[i])%mod;
}
}
LL solve(LL n,LL m){
if(m==)return ;
if(m==)return phi[n];
if(n==)return sum[m];
if(phi[n]==n-){
return (phi[n]*solve(,m)%mod+solve(n,m/n))%mod;
}
for(int i=;i<=tot&&prime[i]*prime[i]<=n;++i){
if(n%prime[i])continue;
return (phi[prime[i]]*solve(n/prime[i],m)%mod+solve(n,m/prime[i]))%mod;
}
}
LL f(LL x){
if(x==)return ;
return qpow(k,f(phi[x])+phi[x],x);
}
int main(){
getphi();
while(~scanf("%I64d%I64d%I64d",&n,&m,&p)){
k=solve(n,m);
printf("%I64d\n",f(p));
}
return ;
}