最終的に \(P,Q\) の \(i\) どちらが \(P\) に属しているかを各 \(i\) について固定します。すると、「\(2 \times N\) の盤面 \(X\) に \(0,1\) が \(N\) 個ずつ書かれている。同じ行か列にあるマスに書かれている整数を入れ替える操作を \(M\) 回行う。最終的に上に \(0\) が \(N\) 個、下に \(1\) が \(N\) 個書かれているような操作列の個数は？」という問題になります。

盤面は \((X_{1,i},X_{2,i}) = (0,0),(0,1),(1,0),(1,1)\) なる \(i\) の個数 \(a,b,c,d\) によって特徴づけられます。そして、\(a+b+c+d=N,a=d\) が成り立つため \(a,b\) が定まれば \(c,d\) も定まります。よって、\(dp[k][x][y]=k\) 回操作して \(a=x,b=y\) となるような操作列の個数、という dp が回ります。

初期状態を求めるためには、\(P,Q\) の \(i\) の片方を \(0\)、もう片方を \(1\) に書き換える方法 \(2^N\) 通りに対する \((a,b)\) の分布を計算出来ればよいです。これは \(P_i \rightarrow Q_i\) という辺を貼ったサイクルの集合において、各サイクルごとに dp をすれば求まります。具体的には、\(1 \rightarrow 2 \rightarrow \dots \rightarrow k \rightarrow 1\) というサイクルがあったときは \(dp[i][x][y][z] = i\) まで \(0,1\) への割り当てを決め、今 \(a=x,b=y\) で、\(Q\) の \(1\) は \(z\) に書き換えた、という dp をすればよいです。

各サイクルの結果をまとめるには、同じ dp 配列を使い続ければ \(\mathrm{O}(N^3)\) になりますし、各サイクルごとに独立に dp をし、畳み込みを用いて \(\mathrm{O}(N^2 \log^2 N)\) でまとめてもよいです。この場合は \((a,b)\) を達成する方法の個数を \(x^{a + (N+1)b}\) の係数に対応させると楽です。

よって、全体 \(\mathrm{O}(N^3 + N^2M)\) でこの問題を解くことが出来ます。

実装例：https://atcoder.jp/contests/arc228/submissions/78749649