你有一个数字 \(x\) 和若干个操作，每个操作是 \(+a_i\) 或者乘 \(\times a_i\) 中的一种。你可以重新排列这些操作的顺序，然后对数字 \(x\) 执行这些操作。
比如说三个操作是 \(+a_1,+a_2,\times a_3\)。如果按顺序执行这三个操作，那么得到的结果是 \(((x+a_1)+a_2)\times a3\)。如果排列成 \(+a_2,\times a_3,+a_1\)，那么得到的结果是 \(((x+a_2)\times a_3)+a_1\)。
我们会发现，有一些操作顺序计算出来的结果是本质相同的，比如说 \(+a_1,+a_2,\times a_3\) 和 $+a_2,+a_1,\times a_3 $这样运算下来结果是一样的。我们认为两个操作顺序计算的结果本质相同，当且仅当无论代入什么数，计算出来的结果都是一样的。
请问有多少种本质不同的操作序列。换句话说就是最多能找到多少个操作序列，使得这些操作序列任意两个都不是本质相同的。由于答案很大，输出对 \(10^9+7\) 取模的结果。
在这个题目中，我们只会给出加法操作和乘法操作的个数，分别是 \(n,m\)，并不会给出具体的顺序和数字。容易发现，答案与具体的顺序和数字无关。
共 \(T\) 组询问，\(1\leq T\leq 10^4,1\leq n,m\leq 3000\)．
把 \(x\) 个有标号球放进 \(y\) 个有区分非空盒子方案数 \(=\ y!\times\) 把 \(x\) 个有标号球放进 \(y\) 个无区分非空盒子方案数 \(=\ \begin{Bmatrix}x\\y\end{Bmatrix}y!\)，设其为 \(calc(x,y)\)。
其中 \(\begin{Bmatrix}x\\y\end{Bmatrix}\) 为第二类斯特林数。
考虑枚举有 \(i\) 个连起来的乘法块，那么其方案数为 \(calc(m,i)\)．
\(i\) 个乘法块形成了 \((i+1)\) 个空隙，两边的 \(2\) 个可空，中间的 \((m-1)\) 个非空。
\(n\) 个加法有三种方法：
-
只放中间 \((m-1)\) 个（钦点两个可空的都不放）：\(calc(n,i-1)\)；
-
钦点一个可空的为非空的，另一个不放：\(calc(n,i)\times 2\)；
-
钦点两个可空的为非空的：\(calc(n,i+1)\)．
故答案为
时间复杂度为 \(\mathcal{O}(m^2+Tm)\)．
#include<iostream>
#include<cstdio>
#include<algorithm>
typedef long long ll;
const ll mod = 1000000007;
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
ll Add(ll x, ll y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
ll cAdd(ll &x, ll y) { return x = (x + y >= mod) ? (x + y - mod) : (x + y); }
ll Mul(ll x, ll y) { return x * y % mod; }
ll Mod(ll x) { return (x >= mod) ? (x - mod) : (x < 0 ? (x + mod) : x); }
ll qpow(ll x, ll y) {
ll sumq = 1;
while(y) {
if(y&1) sumq = sumq * x % mod;
x = x * x % mod;
y >>= 1;
}
return sumq;
}
int &read(int &r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) w = ch == ‘-‘ ? 1 : 0, ch = getchar();
while(ch >= ‘0‘ && ch <= ‘9‘) r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
const int N = 3010;
ll S[N][N], fac[N], inv[N];
ll C(int x, int y) { return fac[x] * inv[y] % mod * inv[x-y] % mod; }
void pre() {
S[1][1] = 1;
for(int i = 2; i <= 3000; ++i)
for(int j = 1; j <= i; ++j)
S[i][j] = Add(S[i-1][j-1], S[i-1][j] * j % mod);
fac[0] = 1; for(int i = 1; i <= 3000; ++i) fac[i] = fac[i-1] * i % mod;
inv[0] = 1; inv[3000] = qpow(fac[3000], mod-2);
for(int i = 2999; i; --i) inv[i] = inv[i+1] * (i+1) % mod;
}
ll calc(int x, int y) { return S[x][y] * fac[y] % mod; }
void solve() { ll ans = 0;
int n, m; read(n); read(m);
for(int i = 1; i <= m; ++i)
ans = Add(ans, calc(m,i) * ((calc(n, i-1) + calc(n, i) * 2 + calc(n, i+1)) % mod) % mod);
printf("%lld\n", ans);
}
signed main() {
pre();
int T; read(T);
while(T--) solve();
return 0;
}