问题描述

$M$ 个集合 $S_1, \ldots, S_M$（元素 $1..N$）。选非空子集（$2^M-1$ 种），要求并集为 $\{1, \ldots, N\}$。求方案数。

输入格式

第一行输入两个整数 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行首先输入一个整数 $C_i$，随后输入 $C_i$ 个整数，表示集合 $S_i$。

输出格式

一个整数。

样例输入 1

3 3
2 1 2
2 1 3
1 2

样例输出 1

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

评测数据规模

对于 $100\%$ 的数据，$1 \le N, M \le 10$。