Counting AI Tree Structures

Kukuru, a legend in the AI field, built a tree‐like connection among n AIs. In such a tree, there are exactly n−1 edges and any two AIs are connected directly or indirectly. However, Kukuru forgot the actual configuration. Fortunately, she remembered the following: for every vertex i (representing an AI), if you remove the ith AI (and disconnect all edges incident to it), then the remaining graph breaks into several connected components; the sizes of these components are recorded. (A connected component is a maximal set of vertices such that any two vertices in it are connected by some path.)

More formally, when the ith vertex is removed from the tree, suppose the sizes of the resulting connected components are \(a_{i,1}, a_{i,2}, \dots, a_{i,d_i}\). Note that the number d_i is exactly the degree of vertex i (since each neighbor will lie in a different component) and it holds that \[ \sum_{j=1}^{d_i}a_{i,j}=n-1. \] For a leaf (a vertex of degree 1) the only connected component has size n−1 (because after removing a leaf the remaining tree is still connected).

Your task is to count, modulo \(998244353\), the number of labeled trees on \(n\) vertices which could have produced the given deletion information (that is, for every vertex i, the set of connected component sizes produced by deleting vertex i is exactly the given one). Two trees are considered different if there exists a pair of vertices \(u,v\) such that one tree has an edge between \(u\) and \(v\) while the other does not.

Important notes:

• It is guaranteed that the input is such that at least one valid tree exists.
• You may assume that if a vertex has degree 1 then its only recorded component size is n−1 and if a vertex has degree at least 2 then the sum of its recorded sizes is n−1.
• A necessary condition for any tree is that the sum of the degrees is \(2(n-1)\).

A well‐known fact (from the Prüfer code) is that if the degree of vertex \(i\) is \(d_i\) then the number of trees with the given degree sequence is \[ \frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}. \] Using the deletion information we know the degree for each vertex (d_i is just the number of recorded component sizes for vertex i). In this problem, you only need to check that the recorded information is globally consistent (for example, the sum of the degrees equals \(2(n-1)\)) and then output the number of trees computed by the above formula modulo \(998244353\). (If the recorded information is inconsistent, output 0.)

inputFormat

The first line contains a single integer n (possibly n=1 is allowed).

Then follow n lines. The ith line begins with an integer k which denotes the number of connected components obtained by removing the ith vertex, followed by k integers \(a_{i,1}, a_{i,2}, \dots, a_{i,k}\). It is guaranteed that if k=1 then \(a_{i,1}=n-1\), and if k>1 then \(\sum_{j=1}^{k}a_{i,j}=n-1\>.

You may assume that the input is such that at least one valid tree exists.

outputFormat

Output a single integer — the number of valid trees (i.e. the number of connection schemes) modulo 998244353.

sample

2
1 1
1 1

1