ll@n,@b,z=0;
ll a[b]{},c[b]{};
rep(i,b){
	long t=powmod(i,n,b);
	a[i]=t;
	c[t]+=1;
}
rep(x,b){
	rep(y,b){
		long t=a[x]+a[y];
		t-=t<b?0:b;
		z+=c[t];
	}
}
wt(z);