【MX-X8-T4】「TAOI-3」Warmth of the Eternity
题目描述
Kukuru 是 AI 领域大神。[如果你是 E.Space 的粉丝的话](/problem/P8294)，你应该知道，$n$ 个 AI 会组成一个树形结构。具体地，对于 $n$ 个 AI，它们之间会构建出恰好 $(n-1)$ 条通路，每条通路会连接两个 AI，并且任意两个 AI 都被直接或间接地连接起来。
但是 Kukuru 忘记了她的 $n$ 个 AI 是如何连接的了。所幸，她还记得：对于所有 $i$，假如删去第 $i$ 个 AI 并断开所有和它相连的通路之后，剩下的 AI 组成的所有连通块的大小。
称若干 AI 形成一个连通块，当且仅当它们两两之间可以通过若干通路互相连接，且没有该连通块外的 AI 与连通块内的 AI 之间存在通路。一个连通块的大小被定义为这个连通块包含的 AI 的个数。
现在 Kukuru 想要知道：在给定这些信息的情况下，这 $n$ 个 AI 有多少种可能的连接方式呢？称两种连接方式不同，当且仅当在一个方案中某两个 AI $u,v$ 之间存在直接通路，而在另一种方案中不存在。因为方案可能很多，所以 Kukuru 只需要你告诉她答案对 $998244353$ 取模的结果就好了。你能解决这个问题吗？**特别地，保证存在至少一种合法的 AI 连接方式符合题意**。
输入输出格式
输入格式
第一行，一个正整数 $n$。
接下来 $n$ 行，第 $i$ 行的第一个正整数 $d_i$ 表示删掉第 $i$ 个 AI 后的连通块个数；接下来，同一行内包含 $d_i$ 个正整数，依次描述每个连通块的大小。
输出格式
仅一行，一个非负整数，表示 AI 可能的连接方式个数对 $998244353$ 取模的结果。
输入输出样例
输入样例 #1
4
1 3
2 1 2
2 1 2
1 3
输出样例 #1
2
输入样例 #2
7
2 2 4
1 6
3 1 1 4
1 6
2 3 3
2 1 5
1 6输出样例 #2
3
输入样例 #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 输出样例 #3
483840
输入样例 #4
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 输出样例 #4
268867231
说明
**【样例解释 \#1】**
**【样例解释 \#2】**
**【数据范围】**
**本题采用捆绑测试。**
- 子任务 1（16 分）：$n \leq 8$。
- 子任务 2（9 分）：存在合法的 AI 连接方式，使得至少一个 AI 与所有其它 AI 直接相连。
- 子任务 3（9 分）：存在合法的 AI 连接方式，使得 AI 都和不超过 $2$ 个其它 AI 直接相连。
- 子任务 4（21 分）：$n \leq 20$。
- 子任务 5（18 分）：$n \leq 5\times 10^3$。
- 子任务 6（27 分）：无特殊限制。
对于所有数据，保证 $2 \leq n \leq 3\times 10^5$。保证取模前的真实答案大于 $0$。