P13694 [CEOI 2025] Splits

For a permutation $p = p[0], p[1], p[2], \ldots, p[n - 1]$ of the numbers $1, 2, 3, \ldots, n$ we define a split as a permutation $q$ which can be obtained by the following process: 1. Select two sets of numbers $A = i_1, i_2, \ldots, i_k$ and $B = j_1, j_2, \ldots, j_l$ such that $A \cap B = \emptyset$, $A \cup B = 0, 1, 2, \ldots, n - 1$, $i_1 < i_2 < \ldots < i_k$ and $j_1 < j_2 < \ldots < j_l$ 2. The permutation $q$ will be $q = p[i_1] p[i_2] \ldots p[i_k] p[j_1] p[j_2] \ldots p[j_l]$ Moreover, we define $S(p)$ to be the set of all splits of a permutation $p$. You are given a number $n$ and a set $T$ of $m$ permutations of length $n$. Count how many permutations $p$ of length $n$ exist such that $T \subseteq S(p)$. Since this number can be large, find it modulo $998\,244\,353$. ### Implementation Details You should implement the following procedure: ```cpp int solve(int n, int m, std::vector& splits); ``` * $n$: the size of the permutation * $m$: the number of splits * $splits$: array containing $m$ pairwise distinct permutations, the elements of the set $T$, which is a subset of $S(p)$ This procedure should return the number of possible permutations modulo $998\,244\,353$. This procedure is called exactly once for each test case.

N/A

N/A

### Sample Explanation 1 Consider the following call: ```cpp solve(3, 2, {{1, 2, 3}, {2, 1, 3}}) ``` In this sample, the size of the permutation $p$ is $3$ and we are given $2$ splits: * $123$ * $213$ The function call will return $4$ as there are only four permutations $p$ that can generate both of those splits: * $123$ * $132$ * $213$ * $231$ ### Constraints * $1 \leq n \leq 300$ * $1 \leq m \leq 300$ ### Subtasks 1. (6 points) $m = 1$ 2. (7 points) $1 \leq n, m \leq 10$ 3. (17 points) $1 \leq n, m \leq 18$ 4. (17 points) $1 \leq n \leq 30, 1 \leq m \leq 15$ 5. (16 points) $1 \leq n, m \leq 90$ 6. (16 points) $1 \leq n \leq 300, 1 \leq m \leq 15$ 7. (21 points) No additional constraints.