题目意思：sum(xi^n) = a(mod P)。首先考虑特殊情况：x^n = m(mod P)。对于高次同余有以下结论：
1.若n|P-1，同余方程有解的充要条件是：a^((p-1)/n)=1(mod P).并且在有解时的解数为n.
2.若n%(P-1)!=0，同余方程x^n=m(mod P)有解的充要条件是同余方程x^k = a(mod P)，P%a!=0,有解，其中k = (n, P-1),且两者的解数相同。
即：a^((P-1)/k) = 1 (mod P)。且有解时解数为k.
由于题目已经说明了(n, P-1) = 1，所以考虑对于方程x^n = m(mod P)对于m取1~P-1都有1解。考虑特殊情况，x^n=0(mod P)也只有唯一解。
所以变成了sum(xi) = a(mod P) 其中xi取0~P-1，所以对于上述方程的解的个数为p^(r-1)。
#include <stdio.h>
#include <string.h>
typedef long long LL;
const LL mod = 10000007;
LL pow_mod(LL a, LL b){
LL ret = 1;
while(b){
if(b&1) ret = ret*a%mod;
a = a * a % mod;
b>>=1;
}
return ret;
}
int main(){
LL a, n, r, p;
while(scanf("%lld%lld%lld%lld", &a, &n, &r, &p)!=EOF){
printf("%lld\n", pow_mod(p, r-1));
}
return 0;
}