项链由很多种戒指拼成，可以先求出不同戒指数量，再来求项链方案数。

戒指数量计算方法和 P4980 区别不大，不同戒指数量即为 $\frac{1}{m}\sum_{d|m}R^d\times \varphi(\frac{m}{d})$，设一共有 $c$ 种戒指。

::::warning[注意] 这里需要求 $m$ 的逆元，但 $m$ 可以超过模数，如果 $m$ 是模数的倍数那就挂了。

这种情况可以把模数平方，$m$ 一定小于模数平方，不会挂了，算此时 $m$ 除以模数的逆元，然后结果除以模数。 ::::

然后就是求项链方案数，因为装饰物插到项链不同位置是不同方案，所以不用考虑旋转后相同的问题，只需要满足相邻两位不同。

考虑 DP，设 $f_i$ 表示长度为 $i$ 的项链的方案数，有转移：

• 如果 $i-1$ 和 $1$ 颜色不同，这时方案数就是 $f_{i-1}$，在 $i-1$ 和 $1$ 之间插入 $i$，有 $c-2$ 种颜色可染，$f_{i} \gets f_{i-1} \times (c-2)$。
• 如果 $i-1$ 和 $1$ 颜色相同，这时方案数就是 $f_{i-2}$，在 $i-1$ 和 $1$ 之间插入 $i$，有 $c-1$ 种颜色可染，$f_{i} \gets f_{i-2} \times (c-1)$。

边界为 $f_1=0，f_2=c(c-1)$。

直接 DP 肯定超时，考虑找出它的通项。

令 $F(x)=\sum\limits_{i=0}^{+\infty}f_ix^i$，得：

$$\begin{aligned} F(x) &=\frac{c(c-1)x}{1-(c-2)x-(c-1)x^2}\\ &=\frac{(c-1)x}{1-(c-1)x}+\frac{(c-1)x}{1+x}\\ &=(c-1)\sum_{i=0}^{+\infty}((c-1)^{i-1}-(-1)^{i-1})x^i \end{aligned}$$

得 $f_n=(c-1)^n+(c-1)(-1)^n$，代入计算即可。

::::info[代码]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=3214567ll*3214567,Mod=3214567;
ll n,m,R,c,ans;
ll mul(ll x,ll y){
	return (__int128)x*y%mod;
}
ll _pow(ll x,ll y){
	ll s=1;
	while(y){
		if(y&1) s=mul(s,x);
		x=mul(x,x),y>>=1;
	}
	return s;
}
ll phi(ll n){
	ll s=n;
	for(int i=2;i*i<=n;i++)
		if(n%i==0){
			s=s/i*(i-1);
			while(n%i==0) n/=i;
		}
	if(n>1) s=s/n*(n-1);
	return s;
}
void exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){x=1,y=0;return ;}
	exgcd(b,a%b,x,y);
	ll tmp=x;
	x=y,y=tmp-(a/b)*y;
}
ll Inv(ll x,ll p){
	ll a,b,t=__gcd(x,p);
	x/=t,p/=t;
	exgcd(x,p,a,b);
	return (a+p)%p;
}
int main(){
	cin>>n>>m>>R;
	for(int i=1;i*i<=m;i++){
		if(m%i) continue;
		c=(c+mul(_pow(R,i),phi(m/i)))%mod;
		if(i*i!=m) c=(c+mul(_pow(R,m/i),phi(i)))%mod;
	}
	if(m%Mod) c=(__int128)c*Inv(m,Mod)%Mod;
	else c=(__int128)c*Inv(m/Mod,mod)%mod,c/=Mod,c%=Mod;
	ans=_pow(c-1,n)%Mod;
	if(n&1) ans=(ans-(c-1)+Mod)%Mod;
	else ans=(ans+(c-1))%Mod;
	cout<<ans;
	return 0;
}
/*
300 3214567 22222
*/