无脑的 APJ 用最无脑的方法解题！！！做了两天图论脑子爆炸后的 apj 寻求精神慰藉
首先考虑 \(n\) 一定是从前往后的最大值与从后往前的最大值，这样我们只需要求出长度为 \(n\)，有 \(k\) 个前缀最大值的排列数量，记作 \(f_{n, k}\)。
考虑每次将当前排列中的最大值与最大值后面的排列去掉，这样就能递归到一个子问题里。例如 \({\color{red}1},{\color{red}4},2,{\color{red}6},3,5\)，我们可以将 \({\color{red}6}, 3, 5\) 删去。枚举删去的后缀的长度 \(i\)，那么后缀本身的方案有 \((i-1)!\) 种，将后缀与前缀混合在一起的方案数为 \(\binom{n-1}{i-1}\)，所以我们可以得出转移式子：
\[f_{n, k} = \sum_{i=1}^n \binom{n-1}{i-1} (i-1)! f_{n - i, k - 1} \]然后把组合数拆一下，移项，得：
\[\frac{f_{n, k}}{n!} = \frac{1}{n}\sum_{i=1}^n \frac{f_{n - i, k - 1}}{(n-i)!} \]后面求和指标换一下：
\[\frac{f_{n, k}}{n!} = \frac{1}{n}\sum_{i=0}^{n-1} \frac{f_{i, k - 1}}{i!} \]然后无脑写成生成函数，设 \(F_k(x) = \sum_{i \ge 0} \frac{f_{i, k}}{i!}x^i\)，那么容易推出：
\[F_k(x) = \int \frac{F_{k-1}(x)}{1-x} \mathrm{d} x \]这个式子直接做看起来还是不可做。我们代具体的式子进去试试：
由于有 \(F_0(x) = 1\)，那么有：
\[\begin{aligned} F_1(x) &= \int \frac{1}{1-x} \mathrm{d} x\\ &= -\ln (1-x)\\ F_2(x) &= \int \frac{-\ln(1-x)}{1-x} \mathrm{d} x\\ &= \int (-\ln(1-x)) (-\ln(1-x))' \mathrm{d} x\\ &= \int u \mathrm{d}u\\ &= \frac{u^2}{2}\\ &= \frac{(-\ln(1-x))^2}{2}\\ F_3(x) &= \int \frac{(-\ln(1-x))^2}{2(1-x)}\\ &= \int \frac{u^2}{2} \mathrm{d}u\\ &= \frac{u^3}{6}\\ &= \frac{(-\ln(1-x))^3}{6}\\ \end{aligned} \]由此归纳可以得出 \(F_k(x) = \frac{(-\ln(1-x))^k}{k!}\)。
回到原问题来，我们枚举了中间的最大值的位置 \(i\)，那么答案应该为 \(\displaystyle \sum_{i=1}^n f_{i - 1, a - 1} f_{n - i, b - 1} \binom{n - 1}{i - 1}\)，发现这其实就等于 \(\displaystyle (n-1)! [x^{n - 1}]F_{a-1}(x) F_{b-1}(x) = (n-1)! [x^{n - 1}]\frac{(-\ln(1-x))^{a+b-2}}{(a-1)!(b-1)!}\)，后者直接多项式快速幂即可。容易 \(O(n \log n)\)。
其实最后还是第一类斯特林数，我这是不是相当于自己把第一类斯特林数的生成函数推导了一遍啊，呃呃。
int main() {
scanf("%d%d%d", &n, &a, &b);
if (a == 0 || b == 0 || n - a - b + 1 < 0) {
printf("0\n");
return 0;
}
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = 1ll * fac[i - 1] * i % P;
inv[n] = qpow(fac[n], P - 2);
for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % P;
f.set(n - 1);
for (int i = 0; i < n; i++) f[i] = qpow(i + 1, P - 2);
f = f.pow(a + b - 2, n);
printf("%lld\n", 1ll * fac[n - 1] * f[n - a - b + 1] % P * inv[a - 1] % P * inv[b - 1] % P);
return 0;
}