より直接的に，「まだ覆われていない場所の集合」についての包除原理を考えてみましょう．

集合 \(s \subset \{1, 2, \cdots, N\}\) を取ります．少なくとも \(s\) が覆われない，という状態が続く回数の期待値を考えます．これは \(s\) の要素を含まないようなボールの個数を \(k\) として，\(M/(M-k)\) と表せます．

よって，次のようなdpを考えます：

dp[\(i\)][\(j\)][\(f\)] := マス \(i\) まで考えて，\(i \in s\) で，\(i\) より左で \(s\) の元を含まない区間の個数が \(j\) で，\(s\) の元の個数の偶奇が \(f\) となるような \(s\) の個数

これを求めることができれば，答えを計算できます．

計算量は \(\mathrm{O}(MN^2)\) です．

実装例：https://atcoder.jp/contests/abc242/submissions/30186571