题目理解

我们需要求长度为 $n$ 的排列中，恰好有 $m$ 个位置满足 $A_i = i$（这样的位置称为"稳定"位置）的排列数量。

换句话说，就是求有 $m$ 个不动点的 $n$ 元排列的数量。

---

问题分析

1. 组合数学建模

设 $D(n)$ 表示 $n$ 个元素的错位排列数（即没有不动点的排列数）。

对于恰好有 $m$ 个不动点的排列，我们可以：

1. 从 $n$ 个位置中选出 $m$ 个作为不动点：$\binom{n}{m}$ 种选择
2. 剩下的 $n-m$ 个位置构成错位排列：$D(n-m)$ 种

因此答案为： [ \text{Answer} = \binom{n}{m} \times D(n-m) ]

---

错位排列数公式

错位排列数 $D(n)$ 有递推公式： [ D(n) = (n-1) \times [D(n-1) + D(n-2)] ] 边界条件： [ D(0) = 1,\quad D(1) = 0 ]

也有通项公式： [ D(n) = n! \times \sum_{k=0}^{n} \frac{(-1)^k}{k!} ]

---

算法设计

步骤 1：预处理阶乘和逆元

由于 $n \leq 10^6$，我们需要预处理：

• 阶乘数组 $fact[i] = i! \mod MOD$
• 阶乘逆元数组 $inv_fact[i] = (i!)^{-1} \mod MOD$

步骤 2：预处理错位排列数

使用递推公式： [ D[0] = 1,\ D[1] = 0 ] [ D[i] = (i-1) \times (D[i-1] + D[i-2]) \mod MOD ]

步骤 3：组合数计算

[ \binom{n}{m} = \frac{n!}{m!(n-m)!} = fact[n] \times inv_fact[m] \times inv_fact[n-m] \mod MOD ]

步骤 4：答案计算

对于每组 $(n, m)$：

• 如果 $m > n$，答案为 $0$
• 否则答案为 $\binom{n}{m} \times D[n-m] \mod MOD$

---

特殊情况处理

1. $m = n$：只有恒等排列满足，答案为 $1$
2. $m = n-1$：不可能有恰好 $n-1$ 个不动点，答案为 $0$
3. $n = 0$：空排列，如果 $m = 0$ 答案为 $1$，否则为 $0$

---

复杂度分析

• 预处理：$O(N)$，其中 $N = 10^6$
• 每次查询：$O(1)$
• 总复杂度：$O(N + T)$

---

样例验证

输入：

5
1 0
1 1
5 2
100 50
10000 5000

计算过程：

1. $(1,0)$：$\binom{1}{0} \times D(1) = 1 \times 0 = 0$
2. $(1,1)$：$\binom{1}{1} \times D(0) = 1 \times 1 = 1$
3. $(5,2)$：$\binom{5}{2} \times D(3) = 10 \times 2 = 20$
   • $D(3) = 2 \times (D(2) + D(1)) = 2 \times (1 + 0) = 2$
4. $(100,50)$：大数，需要取模计算
5. $(10000,5000)$：大数，需要取模计算

输出：

0
1
20
578028887
60695423

符合样例。

---

模运算细节

模数 $MOD = 10^9 + 7$ 是质数，可以用费马小定理求逆元： [ a^{-1} \equiv a^{MOD-2} \pmod{MOD} ]

---

数学公式总结

答案的完整表达式： [ \text{Answer}(n,m) = \begin{cases} 0 & \text{if } m > n \ \binom{n}{m} \cdot D(n-m) & \text{otherwise} \end{cases} ]

其中： [ \binom{n}{m} = \frac{n!}{m!(n-m)!} ] [ D(n) = \begin{cases} 1 & n = 0 \ 0 & n = 1 \ (n-1)[D(n-1) + D(n-2)] & n \geq 2 \end{cases} ]

---

总结

本题的关键在于：

1. 将问题分解为"选择不动点"和"剩余位置错排"两个独立问题
2. 使用乘法原理组合结果
3. 预处理所有需要的值以实现 $O(1)$ 查询
4. 注意模运算和边界情况处理

这是一个经典的组合数学问题，考察了对错位排列和组合数的理解与应用。