注意事项

请在提交源代码前添加 #include "splits.h"。

题目描述

对于一个数字 $1, 2, 3, \ldots, n$ 的排列 $p = p[0]\ p[1]\ p[2]\ \ldots\ p[n-1]$，我们定义一个分割为通过以下过程可以获得的排列 $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$ 和一个包含 $m$ 个长度为 $n$ 的排列的集合 $T$。计算存在多少个长度为 $n$ 的排列 $p$，使得 $T \subseteq S(p)$。由于这个数字可能很大，请计算其对 $998244353$ 取模的结果。

实现细节

你应该实现以下程序：

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

• $n$：排列的大小
• $m$：分割的数量
• $splits$：包含 $m$ 个互不相同的排列的数组，集合 $T$ 的元素，$T$ 是 $S(p)$ 的子集
• 该程序应返回可能的排列数量对 $998244353$ 取模的结果。
• 对于每个测试点，该程序只被调用一次。

示例评测程序

示例评测程序读取以下格式的输入：

• 第 $1$ 行：$n\ m$
• 第 $2+i$ 行：$s[i][0]\ s[i][1]\ \ldots\ s[i][n-1]$ 对于所有 $0 \leq i < m$

并输出调用函数 solve 的结果，使用相应的参数。

样例

考虑以下调用：

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

在这个样例中，排列 $p$ 的大小为 $3$，我们给定了 $2$ 个分割：

• $1\ 2\ 3$
• $2\ 1\ 3$

函数调用将返回 $4$，因为只有 $4$ 个排列 $p$ 可以生成这两个分割：

• $1\ 2\ 3$
• $1\ 3\ 2$
• $2\ 1\ 3$
• $2\ 3\ 1$

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示。