首先考虑如果固定了 \(a\)，如何判定这个 \(a\) 是否能被排序。
如果存在 \(a_i > a_j(i < j)\)，那么 \(a_i\) 肯定要交换到 \(a_j\) 后面，那么就肯定会交换 \(a_i, a_j\)。
于是合法条件就是如果存在 \(a_i > a_j(i < j)\)，那么 \(a_i, a_j\) 只相差一个二进制位。
那就还能知道此时一定 \(a_i\) 这一位为 \(1\)，\(a_j\) 这一位为 \(0\)，其余位都相同。
于是可以考虑从高位开始往低位比较两个数字。
如果满足 \(a_i, a_j(i < j)\) 前面已经遍历的位都相同，这一位不同且 \(a_i\) 这一位为 \(1\)，\(a_j\) 为 \(0\)，就要求剩下的位 \(a_i, a_j\) 相同。
于是可以考虑 DP。
考虑到如果有了上面提到的情况，那么此时 \(a_i, a_j\) 在低位就应该当作一个数了，相当于合并操作，同时还有提到从高位往低位去比较。 就可以设状态 \(f_{n, m}\) 为最高位为 \(n\)，当前有 \(m\) 个数的方案数。
接下来考虑转移，分为两种情况考虑：
-
不存在合并操作。
那么这个时候对于 \(n\) 这一位，就应该满足前面一部分为 \(0\)，后面这部分为 \(1\)，一共会有 \(m + 1\) 种可能的 \(01\) 分界线。同时考虑到此时先手可以操作使得这一位全变为 \(0\)，那么比较还得继续到下一位。
有转移 \(f_{n, m} = (m + 1)f_{n - 1, m}\)。
-
存在合并操作，即存在 \(i < j\)，\(a_i\) 第 \(n\) 位为 \(1\)，\(a_j\) 第 \(n\) 位为 \(0\)。
考虑找到最靠前的为 \(1\) 的位置 \(l\)，最靠后的为 \(0\) 的位置 \(r\)，此时肯定满足 \(l < r\)。
那么可以知道的是，不论 \(l < i < r\) 里的 \(i\) 第 \(i\) 位是什么，肯定都会和 \(l\) 合并或者和 \(r\) 合并。
于是可以知道，\(l\le i\le r\) 的 \(a_i\) 都会合并，还剩下 \(m - (r - l)\) 个数。同时如果先手也选择了把这一位设成 \(0\)，还需要轮到下一轮比较。
此时的方案数为中间 \(r - l - 1\) 个数这一位任选的 \(2^{r - l - 1}\)。
进一步的，考虑到对于同样的 \(r - l\)，不管 \(l, r\) 是多少，本质都是相同的，此时对应的有 \(m - (r - l)\) 种方案。
于是考虑枚举 \(m - (r - l)\)，有转移 \(f_{n, m} = \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
综上，有转移 \(f_{n, m} = (m + 1)f_{n - 1, m} + \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
对于转移的优化，考虑拎出后面求和的部分，令 \(g_{n, m} = \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
那么有 \(g_{n, m + 1} = \sum\limits_{i = 1}^m i 2^{m - i} f_{n - 1, i}\)。
可以发现有 \(g_{n, m + 1} = 2g_{n, m} + mf_{n - 1, m}\)，可以递推求出。
时间复杂度 \(\mathcal{O}(nm)\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
const int maxn = 5e3 + 10;
ll f[maxn], g[maxn];
int main() {
int n, m; scanf("%d%d", &n, &m);
std::fill(f + 1, f + m + 1, 1);
while (n--) {
std::copy(f + 1, f + m + 1, g + 1);
for (int i = 1; i <= m; i++)
f[i] = (f[i - 1] * 2 + g[i - 1] * (i - 1)) % mod;
for (int i = 1; i <= m; i++)
(f[i] += g[i] * (i + 1)) %= mod;
}
printf("%lld\n", f[m]);
return 0;
}