\(K=1\) の場合が解ければ、その他の場合は全て答えが等しいため簡単に求めることができます。以降 \(K=1\) とします。

頂点 \(1,2,...,N\) からなり、\(i\) から \(P_i\) へ辺を貼ったグラフを考えます。このグラフはいくつかのサイクルからなります。

頂点 \(1\) が含まれるサイクルのサイズを \(S\) とした時、\(M \equiv 0 \pmod S\) であることが十分必要条件です。

そのような順列 \(P\) の個数は、以下を全てかけ合わせることで求めることができます。

• 頂点 \(1\) と同じサイクルに含まれる頂点を選ぶ方法の個数 \(\displaystyle \binom{N-1}{S-1}\)
• 大きさ \(S\) の円順列の個数 \((S-1)!\)
• 頂点 \(1\) と違うサイクルに含まれる \(N-S\) 頂点に対する \(P\) の決め方 \((N-S)!\)

以上より、本問題を \(\mathrm{O}(N)\) で解くことができます。