考虑有 m 对二元组 [I_1,D_1][I_2,D_2]\dots[I_m,D_m]。问题可以转换为将 m 对二元组全排列并且保证每一对二元组都存在 I_i 一定在 D_i 之前出现。答案为：
但是还可能存在 $p$ 种，只有插入的情况。因此总的答案数为 $\displaystyle\frac{(2\times m+p)!}{2^m}$ 由于 $2\times m+p=n$ 所以答案是 $\displaystyle\frac{n!}{2^m}$。对结果取余 $10^9+7$，需要求逆元。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7, N = 1e5 + 5;
long long fpow(long long a, int b, int mod) {
long long s = 1;
while (b > 0) {
if (b & 1) {
s = (s * a) % mod;
}
a = (a * a) % mod;
b >>= 1;
}
return s;
}
int main() {
int n;
cin >> n;
unordered_map<int, int> opCount;
for (int i = 0; i < n; i++) {
string op;
int id, val;
cin >> op >> id;
if (op == "INSERT") cin >> val, opCount[id]++;
else if (op == "DELETE") opCount[id]--;
}
int m = 0;
for (auto& [id, cnt] : opCount)
if (cnt == 0) m++; // 统计成对的INSERT和DELETE
long long fact[N] = {0};
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
long long den = fpow(2, m, MOD);
long long inv = fpow(den, MOD - 2, MOD);
long long ans = (fact[n] * inv) % MOD;
cout << ans << endl;
return 0;
}
```