Description

对于一个长度为 $n$ 的排列 $p = p[0], p[1], p[2], \ldots, p[n - 1]$（包含数字 $1, 2, 3, \ldots, n$ 的一个全排列），我们定义分割排列（split）为一个排列 $q$，它可以通过以下过程得到：

1. 选择两个数集
   $A = i_1, i_2, \ldots, i_k$
   $B = j_1, j_2, \ldots, j_l$
   满足：
   • $A \cap B = \emptyset$
   • $A \cup B = \{0, 1, 2, \ldots, n - 1\}$
   • $i_1 < i_2 < \ldots < i_k$
   • $j_1 < j_2 < \ldots < j_l$
2. 将 $q$ 定义为：$$q = p[i_1]\, p[i_2] \ldots p[i_k]\, p[j_1]\, p[j_2] \ldots p[j_l]$$

进一步，我们定义 $S(p)$ 为排列 $p$ 的所有分割排列的集合。

现在，给定一个整数 $n$ 和一个集合 $T$，其中包含 $m$ 个长度为 $n$ 的排列。要求统计有多少个长度为 $n$ 的排列 $p$ 满足 $T \subseteq S(p)$。由于答案可能很大，请将结果对 $998\,244\,353$ 取模。

实现细节

你需要实现以下函数：

int solve(int n, int m, std::vector<std::vector<int>>& splits);

• $n$：排列的长度
• $m$：给定的分割排列数量
• splits：包含 $m$ 个两两不同的排列，表示集合 $T$，该集合是某个 $p$ 的 $S(p)$ 的子集

该过程应返回满足条件的排列数量，结果对 $998\,244\,353$ 取模。该过程在每个测试用例中仅调用一次。

3 2
1 2 3
2 1 3

4

Hint

样例解释 1

考虑以下调用：

solve(3, 2, {{1, 2, 3}, {2, 1, 3}})

在此例中，排列 $p$ 的长度为 $3$，给定的分割排列有：

• $123$
• $213$

只有以下 $4$ 个排列 $p$ 可以同时生成这两个分割排列：

• $123$
• $132$
• $213$
• $231$

因此答案为 $4$。

数据范围

• $1 \leq n \leq 300$
• $1 \leq m \leq 300$

子任务

1. （6 分）$m = 1$
2. （7 分）$1 \leq n, m \leq 10$
3. （17 分）$1 \leq n, m \leq 18$
4. （17 分）$1 \leq n \leq 30,\ 1 \leq m \leq 15$
5. （16 分）$1 \leq n, m \leq 90$
6. （16 分）$1 \leq n \leq 300,\ 1 \leq m \leq 15$
7. （21 分）无额外限制

翻译由 ChatGPT-5 完成