#213800. [CEOI 2025] Splits

For a permutation of the numbers we define a split as a permutation which can be obtained by the following process:

1. Select two sets of numbers and such that , , and
2. The permutation will be

Moreover, we define to be the set of all splits of a permutation .

You are given a number and a set of permutations of length . Count how many permutations of length exist such that . Since this number can be large, find it modulo .

Implementation Details

You should implement the following procedure:

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

• : the size of the permutation
• : the number of splits
• : array containing pairwise distinct permutations, the elements of the set , which is a subset of

This procedure should return the number of possible permutations modulo . This procedure is called exactly once for each test case.

样例输入 1

3 2
1 2 3
2 1 3

样例输出 1

4

Sample Explanation 1

Consider the following call:

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

In this sample, the size of the permutation is and we are given splits:

The function call will return as there are only four permutations that can generate both of those splits:

Constraints

Subtasks

1. (6 points)
2. (7 points)
3. (17 points)
4. (17 points)
5. (16 points)
6. (16 points)
7. (21 points) No additional constraints.