Consecutive Set Intersection Permutations

Given n sets \(s_1,s_2,\dots,s_n\) where each set contains distinct integers drawn from the range \([1,m]\), determine the number of permutations \(p\) of \(\{1,2,\dots,n\}\) such that

[ \Bigl( \sum_{i=1}^{n} |s_i| \Bigr) - \Bigl( \sum_{i=1}^{n-1} |s_{p_i} \cap s_{p_{i+1}}| \Bigr) = \left| \bigcup_{i=1}^{n} s_i \right|. ]

In other words, for every element \(x\) that appears in one or more sets, the sets containing \(x\) must appear consecutively in the permutation. Output the answer modulo \(998244353\). It is guaranteed that the answer prior to taking the modulo is positive.

inputFormat

The first line contains two integers \(n\) and \(m\).

Then, \(n\) lines follow. The \(i\)-th of these lines begins with an integer \(k_i\) denoting the number of elements in set \(s_i\), followed by \(k_i\) distinct integers representing the elements of \(s_i\). All elements are in the range \([1, m]\).

It is guaranteed that \(1 \le n \le 10\) (or a similarly small limit) so that a backtracking solution is feasible.

outputFormat

Output a single integer: the number of permutations satisfying the condition, modulo 998244353.

sample

2 3
2 1 2
2 2 3

2