H. Gepeto and Notation
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Professor G. Coutinho wrote his old proofs for Phantasmagorical Graph Theory in English, using the field's standard notation. For example, the Greek letter $$$\alpha$$$ always refers to independent sets, while $$$\chi$$$ refers to proper colorings. Now he is teaching the course again, this time in Portuguese.

Some frightening graphs from Phantasmagorical Graph Theory

Since he is very busy, he has asked his old friend Gepeto to help translate his notes. Gepeto, however, is rather absent-minded: he does not remember the notation well and tends to mix up the symbols as he translates. This has made the lectures very confusing, and Coutinho wants to decide whether he should translate the notes himself.

He asks each student which symbols they consider essential and which substitutions they could tolerate. He then wants to count the ways Gepeto could mix up the notation so that every student is confused: the worst possible outcome.

Formally, there are $$$n$$$ standard symbols, numbered from $$$1$$$ to $$$n$$$, and $$$m$$$ students. For each student $$$i$$$, the set $$$A_i$$$ contains the symbols that student considers essential. Gepeto replaces the symbols according to a permutation of the $$$n$$$ symbols. Student $$$i$$$ is confused if at least one symbol in $$$A_i$$$ is replaced by a different symbol. Count the permutations that confuse every student.

Professor Coutinho is not known for his programming skills, so he has left this task to you. Help him!

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 1000$$$, $$$1 \leq m \leq 16$$$), the number of symbols and the number of students, respectively.

Each of the next $$$m$$$ lines describes one student's essential set. Line $$$i$$$ starts with an integer $$$k_i$$$ ($$$1 \leq k_i \leq n$$$), the size of $$$A_i$$$, followed by $$$k_i$$$ distinct integers $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq n$$$), its elements.

Output

Print the number of permutations of the $$$n$$$ symbols such that, for every student $$$i$$$, at least one element of $$$A_i$$$ is replaced by a different symbol. Since the answer may be large, print it modulo $$$998244353$$$.

Examples
Input
3 2
1 2
1 1
Output
3
Input
3 1
2 1 2
Output
5
Input
4 3
1 1
1 2
1 4
Output
11
Input
16 1
1 1
Output
612227903
Note

Explanation for example 1

Represent a permutation of the three symbols as a list in which the $$$i$$$-th element is the symbol used in place of symbol $$$i$$$. The possibilities are:

  • $$$1,2,3$$$: neither student is confused;
  • $$$1,3,2$$$: only the first student is confused;
  • $$$2,1,3$$$: both students are confused;
  • $$$2,3,1$$$: both students are confused;
  • $$$3,1,2$$$: both students are confused;
  • $$$3,2,1$$$: only the second student is confused.
Thus, the answer is $$$3$$$.