题目描述

有 $M$ 个集合，分别称为 $S_1, S_2, \\dots, S_M$，由整数 $1$ 到 $N$ 组成。
$S_i$ 包含 $C_i$ 个整数 $a_{i, 1}, a_{i, 2}, \\dots, a_{i, C_i}$。

从这 $M$ 个集合中选择一个或多个集合有 $(2^M-1)$ 种方式。
有多少种方式满足以下条件？

• 对于所有的整数 $x$，满足 $1 \\leq x \\leq N$，至少存在一个被选择的集合包含 $x$。

约束条件

• $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$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $M$ $C_1$ $a_{1,1}$ $a_{1,2}$ $\\dots$ $a_{1,C_1}$ $C_2$ $a_{2,1}$ $a_{2,2}$ $\\dots$ $a_{2,C_2}$ $\\vdots$ $C_M$ $a_{M,1}$ $a_{M,2}$ $\\dots$ $a_{M,C_M}$

输出

打印满足题目描述中条件的选择集的数量。

示例 1

3 3
2
1 2
2
1 3
1
2

输出示例 1

3

输入中给出的集合为 $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$。

示例 2

4 2
2
1 2
2
1 3

输出示例 2

0

可能没有一种方式满足题目描述中的条件。

示例 3

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

输出示例 3

18