题意：定义 \(n\) 个区间是好的，当且仅当：
- \(1 \leq l_i \leq r_i \leq N\)。
- 存在唯一的 \(N\) 阶排列 \(x_1,x_2,\cdots,x_N\)，使得 \(x_i \in \left[ l_i , r_i\right]\)
给定整数 \(N\)、素数 \(P\)。
求有多少组 \(\left[l_1,r_1\right],\left[l_2,r_2\right],\cdots,\left[l_N,r_N\right]\) 是好的。
答案对 \(P\) 取模。
做法：
显然不存在两区间相同，所以我不妨令 \(x_i = i\)，最后将答案乘上 \(n!\) 即可。
然后考虑我令 \(i\to [l_i,r_i]\setminus i\)，连若干条边，那么这个图中不能出现环，显然和原题条件是充要的。那么意味着这个图是 dag。
考虑经典的 0 度容斥，我们容斥入度为 \(0\) 的点，假设是 \(v_1,v_2,\cdots v_k\)，那么容斥系数是 \((-1)^{k+1}\)，还要考虑区间的问题，注意到对于 \(v_i\)，其区间 \([l_{v_{i}},r_{v_i}]\) 需要满足 \(v_{i-1}<l_{v_i}\le v_i\le r_{v_i}<v_{i+1}\)，同时对于不被选入的点，我们发现其区间不能碰到 \(v\) 中任意元素，否则 \(v_i\) 就不能被我们选出来作为 \(0\) 度点。
所以记 \(f_n\) 代表 \(n\) 个点的答案，转移式为：
\[\sum(-1)^{k+1}(\prod_{i=1}^k (v_i-v_{i-1})(v_{i+1}-v_i)f_{v_i-v_{i-1}-1}) \times f_{n-v_{k}}
\]
这里 \(v_0=1,v_{k+1}=n\)。
发现我们没有必要一步转移出来 \(f\)，可以分步转移，记为 \(g\)，代表最后一个转移点在 \(n\) 的位置，具体转移可以见代码。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 5005;
int f[maxn], g[maxn], n, mod;
signed main() {cin >> n >> mod;f[0] = f[1] = g[1] = 1;for (int i = 2; i <= n; i++) {g[i] = f[i - 1] * i % mod;for (int j = 1; j < i; j++)g[i] = (g[i] - g[j] * f[i - j - 1] % mod * (i - j) % mod * (i - j) % mod + mod) % mod;for (int j = 1; j <= i; j++)f[i] = (f[i] + g[j] * f[i - j] % mod * (i - j + 1)) % mod;}int ans = f[n];for (int i = 1; i <= n; i++)ans = ans * i % mod;cout << ans << endl;return 0;
}