次の問題のテスター解です．形式的冪級数の操作により $O(N \log N)$ で解けます．

問題文を次のように言い換えます．

${1,\ldots,N}$ の順列 $\sigma$ が与えられる．$\tau^M = \sigma$ を満たす順列 $\tau$ の個数を求めよ．

$\sigma$ をサイクルの非交和 (disjoint union) に分解しておきます．

$km$-サイクルを $M$ 乗すると $k$ 個の $m$-サイクルが出来る条件は，$\gcd(km, M) = k$ です．また，$k$ 個の $m$-サイクルから元の $km$-サイクルを復元する方法は $(k-1)! m^{k-1}$ 通りあります．

そこで，各 $m$ について，$\tau$ が含む全ての $m$-サイクルをいくつかのサイクルにまとめることを考えます．$\tau$ が $m$-サイクルを $s$ 個含むとき，これらを ($M$ 乗すると元の $m$-サイクル $s$ 個に戻るような) $1$ 個以上のサイクルとして並べる方法の数を $f(s)$ とします．$f(s)$ の指数型母関数は， $$ \sum_{s \geq 0} \frac{f(s)}{s!} x^s = \exp \left(\sum_k \frac{(k-1)!m^{k-1}}{k!} x^k \right) $$ で表せます．ただし $k$ は $\gcd(km, M) = k$ を満たす範囲を動くとします．

右辺の $s$ 次の項の係数は $O(s \log s)$ 時間で計算できます．各 $m$ について，この値の総積をとればよいです．よって $O(N \log N)$ 時間でこの問題が解けました．