「裏を向けているカードの集合」についての包除原理によって答えを求めることを考えます（参考 : ABC242 Ex ユーザ解説）。

すると、元の問題は以下の問題と同値です。

長さが \(N\) で各要素が \(0\) か \(1\) であり、全てが \(1\) ではない数列 \(A\) は \(2^N-1\) 通りありますが、その全てに対して以下で定められる \(A\) のスコアの総和を求めよ。

\(1 \le i \le N\) を満たす整数 \(i\) のうち、\(A_i,A_{i+1},\dots,A_{i+M-1}\) が全て \(1\) である \(i\) の個数を \(u\) とする。ここで、\(A_i=A_{i-N}(i>N)\) とする。

また、\(A\) の要素のうち、\(0\) であるものの個数を \(v\) とする。 \(A\) のスコアは \(\displaystyle \frac{N}{N-u} \times (-1)^{v+1}\) である。

この問題は、以下のようにして解くことができます。

\(A\) を円環で表した時、以下のように \(p,q\) を定める。

• \(A_i=0\) を満たす整数 \(i\) のうち、\(A_{i+1}=A_{i+2}=\dots =A_{i+M}=1\) であるような \(i\) の個数を \(p\) とする。
• \(A_i=0\) を満たす整数 \(i\) のうち、\(A_{i+1}=A_{i+2}=\dots =A_{i+M}=1\) でないような \(i\) の個数を \(q\) とする。

例えば、\(N=5,M=2\) の時 \(A=(0,1,1,0,1)\) は \(p=1,q=1,u=1\) であり、\(A=(0,0,0,0,1)\) は \(p=0,q=4,u=0\) です。

\(p,q,u\) を固定した時、そのような \(A\) の個数は以下の値を全て掛け合わせた値の個数分あります。

• \(p\) 個ある \(0\) に \(u\) の条件を満たす \(i\) の個数を振り分ける方法 \(\binom{u-1}{p-1}\)
• \(q\) 個ある \(0\) に \(u\) の条件を満たさない \(i\) の個数を振り分ける方法 \([x^{N-pM - u}] (\sum_{i=1}^{M} x^i)^q\)
• \(0\) + \(0\) 個以上の \(1\) というグループ \(p+q\) 個のうち、\(A_1\) がどこに属するかの重複度 \(p+q\) で以下の \(2\) 個の値の積を割る
• 上記で定めたグループから初めて、それぞれの \(0\) が \(p\) として数えられたか \(q\) として数えられたかの順番の個数 \(\binom{p+q}{p}\)
• \(A\) を回転させる方法の個数 \(N\)

そして、\(p,q,u\) を固定した時のスコアは \(\displaystyle \frac{N}{N-u} \times (-1)^{p+q+1}\) です。

例えば、\(N=6,M=2,p=1,q=1,u=2\) の場合は、それぞれの値が \(1,1,\frac{1}{2},2,6\) となり、積は \(6\) です。実際、\((0,1,0,1,1,1)\) を回転させた \(6\) 通りがあります。また、\(N=6,M=2,p=2,q=0,u=2\) の場合はそれぞれの値が \(1,1,\frac{1}{2},1,6\) となり、積は \(3\) です。実際、\((0,1,1,0,1,1)\) を回転させた \(3\) 通りがあります。

より、\(p,q,u \le N\) なので適切な前計算のもと \(p,q,u\) を全探索し上記の値の積を取ることで、この問題を \(\mathrm{O}(N^3)\) で解くことができます。

\(p\) を固定した場合に \(q\) に対し \(\displaystyle \left(\sum_{i=1}^{M} x^i\right)^q \times \binom{p+q}{p} \times \frac{1}{p+q} \times (-1)^{p+q+1}\) の総和を高速に求め、\(x\) を全探索することができればよいです。

ここで、\(q\) の上限をなくしてもいいため多項式 \(f(x)\) に対して \(\displaystyle \sum_{i=0}^{\infty} f(x)^i \times \binom{i+p}{p} \times \frac{1}{i+p} \times (-1)^{i+p+1}\) が求められればよいです。これは式変形することにより \(\displaystyle \frac{(-1)^{p+1}}{p(1+f(x))^p}\) と等しいため、\(\mathrm{O}(N\log N)\) で求めることができます。

\(p=0\) の場合は \(q \ge 1\) の場合について和を取る必要があります。その場合は \(\displaystyle \sum_{i=1}^{\infty} \frac{f(x)^i}{i} \times (-1)^{i+1}\) となり、これは \(\log(1+f(x))\) と等しいです。これも \(\mathrm{O}(N\log N)\) で求めることができます。

よって、\(p\) を固定し \(q\) についての総和を上記を用いて \(\mathrm{O}(N\log N)\) で求め、\(u\) を全探索することでこの問題を \(\mathrm{O}(N^2\log N)\) で解くことができます。

\(p=0\) の場合は \(\mathrm{O}(N\log N)\) で解くことができているので、以降 \(p \ge 1\) と仮定します。自動的に \(u \ge 1\) となります。

\(\displaystyle \sum_{p=1}^{\infty} \sum_{u=1}^{N-1} [x^{N-pM-u}] \frac{(-1)^{p+1}}{p(1+f(x))^p} \times \binom{u-1}{p-1} \times \frac{N^2}{N-u}\) が求めるべき値です。

ここで、\(\displaystyle g(x) = \frac{x^M}{1+f(x)}\) とすると、上記の式は \(\displaystyle \sum_{p=1}^{\infty} \sum_{u=1}^{N-1} [x^{N-u}] g(x)^p \times \frac{(-1)^{p+1}}{p} \times \binom{u-1}{p-1} \times \frac{N^2}{N-u}\) となります。

\(u\) を固定した場合に対し、\(p\) に対し\(\displaystyle g(x)^p \times \frac{(-1)^{p+1}}{p} \times \binom{u-1}{p-1}\) の総和を高速に求めればよいです。

ここで、\(p\) の上限をなくしてもいいため \(\displaystyle \sum_{p=1}^{\infty} g(x)^p \times \frac{(-1)^{p+1}}{p} \times \binom{u-1}{p-1}\) が求められればよいです。これは式変形することにより \(-\displaystyle \frac{(1-g(x))^u-1}{u}\) と等しいです。

また、定数項が必要となることはないため、この値を \(\displaystyle -\frac{(1-g(x))^u}{u}\) と考えてよいです。

よって、求めるべき値は \(\displaystyle \sum_{u=1}^{N-1} [x^{N-u}] -\frac{(1-g(x))^u}{u(N-u)} \times N^2\) となります。

ここで、\(h(x) = (1-g(x))x\) とすると上記の式は \(\displaystyle \sum_{u=1}^{N-1} [x^{N}] -\frac{h(x)^u}{u(N-u)} \times N^2\) となるため、\(h(x)\) に対して \(h(x)^0,h(x)^1,\dots,h(x)^{N-1}\) の \(x^N\) の係数が求められればよいです。

これは実際に可能であり、以下のブログ(https://codeforces.com/blog/entry/77551) の一番最後に乗っている方法を使うことで \(\mathrm{O}(N\log N)\) で求めることができます。

よって、この問題を \(\mathrm{O}(N\log N)\) で解くことができました。\(h(x)\) の逆関数をニュートン法で求めるパートの定数倍が重いため注意してください。