考虑若已求出钦定 \(k\) 个升高的排列数量 \(f_k\)，那么二项式反演就可以求出恰好 \(k\) 个升高的排列数量 \(g_k\)，即：
\[g_k = \sum\limits_{i = k}^n (-1)^{i - k} \binom{i}{k} f_i \]考虑求 \(f_i\)。相当于钦定原序列构成了 \(n - k\) 个上升段。相当于把 \(n\) 个数分成 \(n - k\) 个互相区分的集合，每个集合内部升序排序就是上升段。所以：
\[f_i = \begin{Bmatrix} n \\ n - i \end{Bmatrix} (n - i)! \]直接 NTT 求一行的斯特林数可以通过 P5825 排列计数，但是这题的模数只能 MTT。考虑用斯特林数的通项公式展开，把 \(f_i\) 代入 \(g_k\)：
\[\begin{aligned} g_k & = \sum\limits_{i = k}^n (-1)^{i - k} \binom{i}{k} \sum\limits_{j = 1}^{n - i} (-1)^{n - i - j} j^n \binom{n - i}{j} \\ & = \sum\limits_{j = 1}^n (-1)^{n + k + j} j^n \sum\limits_{i = k}^{n - j} \binom{i}{k} \binom{n - i}{j} \\ & = \sum\limits_{j = 1}^n (-1)^{n + k + j} j^n \binom{n + 1}{k + j + 1} \end{aligned} \]最后一步用到了这个恒等式：\(\sum\limits_i \binom{i}{a} \binom{n - i}{b} = \binom{n + 1}{a + b + 1}\)。组合意义即为考虑 \(n + 1\) 个物品中选 \(a + b + 1\) 个，枚举第 \(a + 1\) 个物品的位置，加上左边选 \(a\) 个的方案数乘上右边选 \(b\) 个的方案数。
直接快速幂计算 \(i^n\) 就是 \(O(n \log n)\) 的，也可以线性筛做到 \(O(n)\)。
code
// Problem: #2834. 「JOISC 2018 Day 2」修行
// Contest: LibreOJ
// URL: https://loj.ac/p/2834
// Memory Limit: 256 MB
// Time Limit: 600 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
const ll mod = 1000000007;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, m, fac[maxn], ifac[maxn];
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
void solve() {
scanf("%lld%lld", &n, &m);
fac[0] = 1;
for (int i = 1; i <= n + 1; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[n + 1] = qpow(fac[n + 1], mod - 2);
for (int i = n; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
m = n - m;
ll ans = 0;
for (int i = 1; i <= n; ++i) {
ans = (ans + (((n + m + i) & 1) ? mod - 1 : 1) * qpow(i, n) % mod * C(n + 1, m + i + 1)) % mod;
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}