题面翻译

有 $M$ 个集合，在这些集合中选出 $k$ 个，使这 $k$ 个集合的并集包含 $1$ 到 $N$ 中的任何一个数，求有多少种选法。

两个集合的并集指的是 两个集合中所有元素的总集合。多个集合的并集依此类推。

例如集合 $A=\{1,2,3\}$，$B=\{3,4,5\}$，则 $A,B$ 的并集为 $\{1,2,3,4,5\}$。

输入格式

第一行输入 $N$ $M$

接下来 $M$ 行，每行首先输入一个数字 $C_i$ 代表该集合里有 $C_i$ 个数字，然后继续输入 $C_i$ 个整数分别是 $a_{i,1}$ $a_{i,2}$ $\dots$ $a_{i,C_i}$

输出格式

输出一个整数代表答案

3 3
2
1 2
2
1 3
1
2

3

4 2
2
1 2
2
1 3

0

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

18

提示

数据范围

• $1\ \leq\ N\ \leq\ 10$
• $1\ \leq\ M\ \leq\ 10$
• $1\ \leq\ C_i\ \leq\ N$
• $ 1\ \leq\ a_{i,1}\ \lt\ a_{i,2}\ \lt\ \dots\ \lt\ a_{i,C_i}\ \leq\ N $

样例 1 解释

输入中给出的集合为 $S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace$ 。 以下三种方法都能满足问题陈述中的条件：

• 选择 $S_1, S_2$ ；
• 选择 $S_1, S_2, S_3$ ；
• 选择 $S_2, S_3$ 。