尝试复健。

如果直接正向考虑 $M$ 不整除的情况，太复杂，所以考虑算出不好的排列，然后拿总数减去它。

总数可以直接算出来，故不细说。考虑 $f[i]$ 表示一共有 $i$ 对 $dist$ 被 $M$ 整除的数对的排列个数。这个直接做有点难，但是可以设 $f[i]$ 表示一共有 $\ge i$ 对不好的数对的排列个数，然后作容斥。

我们把整个序列每 $M$ 个切一段，那么 $\bmod\ M$ 同余的位置在每个段内相对位置相同，我们要做的就是在这些位置中取出若干对位置进行计数。具体地，设当前枚举 $\bmod{\ M}=i$，枚举选出 $j(2 \mid j)$ 个位置转移，则有方程（设 $tot$ 为整个序列中 $\bmod M=i$ 的位置个数）：

即 $tot$ 个位置中选 $j$ 个 $\times$ 分配颜色方案数 $\times$ 选出的 $j$ 个数顺序。

然后，我们已经选出了 $j$ 对，对于剩下的 $n-\frac{j}{2}$ 个数，依据上面的方式继续乘以 颜色分配方案数 乘以 颜色顺序即可。

以上我们即可求出 $f[i]$ 表示 $\ge i$ 对不好数对的方案数，最后乘以一个 $(-1)^{i+1}$ 的系数累加即可得到不好的排列个数，拿最开始的方案数即 $\binom{2 \times n}{n}$ 减去即可。

复杂度 $O(n^2)$。