1. 题意理解

我们有：

• ( N ) 块绿色石头（编号 1 到 N）
• ( N ) 块灰色石头（编号 1 到 N）
• 总共 ( 2N ) 块石头排成一行，相邻石头距离 1 英寸

M-不幸的定义：存在两块相同编号的石头，它们之间的距离是 ( M ) 的倍数。

M-幸运：不是 M-不幸的花园。

要求：计算 M-幸运 花园的数量，对 ( 10^9+7 ) 取模。

---

2. 问题转化

设位置为 ( 1, 2, \dots, 2N )。

对于编号 ( i ) 的石头，有一绿一灰两块。它们在花园中的位置分别为 ( p_i )（绿）和 ( q_i )（灰）。

M-不幸的条件：存在某个 ( i )，使得 ( |p_i - q_i| ) 是 ( M ) 的倍数。

等价地：对于某个 ( i )，( p_i \equiv q_i \pmod{M} )。

---

3. 容斥原理思路

设 ( A_i ) 表示编号 ( i ) 的两块石头距离是 ( M ) 的倍数的事件。

我们要求： [ \text{答案} = \sum_{S \subseteq {1,\dots,N}} (-1)^{|S|} \times (\text{满足所有 } i\in S \text{ 的事件 } A_i \text{ 的方案数}) ]

---

4. 计算固定集合 S 的方案数

假设我们固定 ( k = |S| ) 个编号必须满足 ( p_i \equiv q_i \pmod{M} )。

4.1 模 M 的剩余类分析

位置 ( 1, 2, \dots, 2N ) 模 ( M ) 的分布：

对于余数 ( r )（从 0 到 M-1），位置个数为： [ \text{cnt}_r = \left\lfloor \frac{2N - 1 - r}{M} \right\rfloor + 1 ] 在代码中，cnt = (2 * n + i) / m 计算了余数 ( i ) 的位置数量（i 从 0 到 M-1）。

---

4.2 配对安排

对于每个余数类 ( r )：

• 有 cnt 个位置
• 我们要在这些位置中放置 ( S ) 中编号的绿色和灰色石头（它们必须同余数类）
• 还要放置其他编号的石头

关键：对于每个余数类，我们选择一些编号（来自 S）放置它们的绿石和灰石，并且它们必须成对出现（因为绿石和灰石都在这个余数类中）。

---

5. 动态规划 cal_f()

f[j] 表示：已经安排了 j 个编号（来自 S）的绿石和灰石，并且满足它们同余数类条件的方案数。

转移：

• 对于余数类 i，有 cnt 个位置
• 从中选择 2k 个位置给 k 个新编号（每个编号占 2 个位置：一绿一灰）
• 安排方式数：cal_a(cnt, 2*k)（排列）
• 从剩余编号中选择 k 个：cal_c(j+k, j)（组合）

所以： [ f[j+k] \mathrel{+}= f[j] \times A(cnt, 2k) \times C(j+k, j) ]

---

6. 最终容斥计算

for (int i = 0, o = 1; i <= n; i++, o = P - o) {
    ans = (ans + (ll)o * f[i] * cal_c(n, i) * fac[2*(n-i)]) % P;
}

这里：

• i 表示我们强制让 i 个编号满足同余条件（即 |S| = i）
• o 是容斥系数 ( (-1)^i )
• f[i] 是安排这 i 个编号的方案数（它们必须同余）
• cal_c(n, i) 是从 n 个编号中选择 i 个编号的方式数
• fac[2*(n-i)] 是安排剩下 n-i 个编号（没有限制）的方式数：它们有 2(n-i) 块石头，任意排列在剩余位置

---

7. 样例验证

样例 2：N=1, M=1

• 只有两个位置
• 两个花园：绿1在位置1灰1在位置2，或者绿1在位置2灰1在位置1
• 距离都是 1，是 M=1 的倍数 → 都是 M-不幸
• 输出 0，符合样例

---

8. 算法标签

• 容斥原理 (Inclusion–Exclusion Principle)
• 动态规划 (Dynamic Programming)
• 组合数学 (Combinatorics)
• 模运算 (Modular Arithmetic)

---

9. 核心思想总结

1. 问题转化：将“距离是 M 的倍数”转化为“位置模 M 同余”
2. 容斥原理：计算至少 k 个编号满足同余条件的方案数，带符号求和
3. 动态规划：按余数类逐步安排必须同余的编号
4. 组合计数：利用排列组合公式计算各种安排方式数

这种方法高效地计算了大规模约束下的合法排列数，时间复杂度 ( O(N^2 M) )，适合 ( N, M \leq 2000 )。