Description：

求有多少棵树，满足 $DFS$ 序为 $1,2,\dots,n$ 且满足 $m$ 个形如 $b$ 在 $a$ 子树的限制。

$1\leqslant n,m\leqslant 7000$

Solution：

先预处理一个 $r[i]$ 表示点 $i$ 在 $dfs$ 上右端点至少是几，这个的求的过程就是求出必须在 $i$ 的子树中的 $dfs$ 最大的那个点，然后我们可以把 $dfs$ 序列划分成若干个不相交的区间，这些区间会形成一个树结构，那么我们可以用类似树形 $DP$ 的方式，具体来说设 $f[i][j]$ 表示以第 $i$ 个点为根，最右链长度为 $j$ 的方案数，然后每次可以把另外一棵子树接在这个后面，具体做法是每次求一遍后缀和，然后把另一棵树接在后面，转移类似一个背包，因此由树形 $DP$ 的时间复杂度证明是 $O(n^2)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 7010

int r[MAXN];

#define P 998244353

int siz[MAXN];

int f[MAXN][MAXN];

int g[MAXN];

void dp(int k)

{

	siz[k] = 1;

	f[k][1] = 1;

	if(k == r[k])return;

	for(int i = k + 1;i <= r[k];i = r[i] + 1)

	{

		dp(i);

		for(int j = siz[k] - 1;j >= 1;--j)f[k][j] = (f[k][j] + f[k][j + 1]) % P;

		for(int j = 1;j <= siz[k] + siz[i];++j)g[j] = 0;

		for(int j = siz[k];j >= 1;--j)

			for(int l = siz[i];l >= 1;--l)

				g[j + l] = (g[j + l] + 1ll * f[k][j] * f[i][l] % P) % P;

		siz[k] += siz[i];

		for(int j = 1;j <= siz[k];++j)f[k][j] = g[j];

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)r[i] = i;

	int a,b;

	for(int i = 1;i <= m;++i){scanf("%d%d",&a,&b);r[a] = max(r[a],b);}

	r[1] = n;

	for(int i = 1;i <= n;++i)for(int j = i + 1;j <= r[i];++j)r[i] = max(r[i],r[j]);

	dp(1);

	int ans = 0;

	for(int i = 1;i <= n;++i)ans = (ans + f[1][i]) % P;

	cout << ans << endl;

	return 0;

}