Background

Original link: https://oier.team/problems/X8E.

Problem Description

Kukuru is a top expert in the AI field. If you are a fan of E.Space (/problem/P8294), you should know that $n$ AIs will form a tree structure. Specifically, for $n$ AIs, exactly $(n-1)$ paths are built between them. Each path connects two AIs, and any two AIs are connected directly or indirectly.

However, Kukuru forgot how her $n$ AIs were connected. Luckily, she still remembers the following: for every $i$, after deleting the $i$-th AI and removing all paths connected to it, the sizes of all connected components formed by the remaining AIs.

A group of AIs is called a connected component if and only if every pair of AIs in it can reach each other through some paths, and there is no path between any AI outside the component and any AI inside the component. The size of a connected component is defined as the number of AIs in it.

Now Kukuru wants to know: given this information, how many possible connection structures can these $n$ AIs have? Two connection structures are considered different if and only if, in one structure, there is a direct path between some two AIs $u,v$, while in the other structure, there is not. Since there may be many structures, Kukuru only needs you to output the answer modulo $998244353$. Can you solve this problem? In particular, it is guaranteed that there exists at least one valid AI connection structure that satisfies the statement.

Input Format

The first line contains a positive integer $n$.

In the next $n$ lines, in line $i$, the first positive integer $d_i$ indicates the number of connected components after deleting the $i$-th AI; then the same line contains $d_i$ positive integers, describing the size of each connected component in order.

Output Format

Only one line containing a non-negative integer, representing the number of possible AI connection structures modulo $998244353$.

4
1 3
2 1 2
2 1 2
1 3

2

7
2 2 4
1 6
3 1 1 4
1 6
2 3 3
2 1 5
1 6

3

20
2 18 1 
3 2 5 12 
2 2 17 
2 1 18 
2 14 5 
1 19 
1 19 
1 19 
3 16 2 1 
1 19 
2 18 1 
2 15 4 
3 16 1 2 
2 15 4 
2 13 6 
1 19 
2 18 1 
1 19 
1 19 
4 8 1 3 7 

483840

50
1 49 
1 49 
2 48 1 
1 49 
1 49 
2 36 13 
1 49 
1 49 
3 39 1 9 
1 49 
1 49 
5 6 1 39 1 2 
2 48 1 
6 1 5 1 4 37 1 
1 49 
1 49 
1 49 
2 1 48 
2 29 20 
1 49 
2 1 48 
2 1 48 
4 46 1 1 1 
1 49 
1 49 
1 49 
1 49 
1 49 
7 1 3 1 1 41 1 1 
4 30 1 4 14 
1 49 
1 49 
5 1 1 45 1 1 
1 49 
1 49 
5 11 5 21 11 1 
1 49 
1 49 
3 1 1 47 
1 49 
3 1 2 46 
1 49 
1 49 
1 49 
1 49 
4 1 1 2 45 
1 49 
1 49 
1 49 
4 44 2 1 2 

268867231

Hint

[Sample Explanation #1]

[Sample Explanation #2]

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (16 points): $n \leq 8$.
• Subtask 2 (9 points): There exists a valid AI connection structure such that at least one AI is directly connected to all other AIs.
• Subtask 3 (9 points): There exists a valid AI connection structure such that each AI is directly connected to no more than $2$ other AIs.
• Subtask 4 (21 points): $n \leq 20$.
• Subtask 5 (18 points): $n \leq 5\times 10^3$.
• Subtask 6 (27 points): No special restrictions.

For all testdata, it is guaranteed that $2 \leq n \leq 3\times 10^5$. It is guaranteed that the real answer before taking modulo is greater than $0$.

Translated by ChatGPT 5