题目描述

存在若干个集合（集合数量未知，不存在空集），给定 $n$，每个集合中元素 $x$ 满足 $1 \le x \le n$，你现在已知 $M$ 个集合内的元素情况。

定义全集 $U=\{1,2,\dots ,n\}$，这若干个集合间满足两个性质：

• 若集合 $A$ 存在，那么 $\complement_UA$ 也存在。
• 对于当前的两个集合 $A,B$，集合 $C=A \cup B$ 也存在。

希望你求出最小的集合数量，把它对 $10^9+9$ 取模的结果。

输入格式

第一行一个整数 $n$。

第二行一个整数 $M$，表示已知的集合数量。

以下 $M$ 行，一行一个整数 $B$，表示当前集合元素数量，随后是 $B$ 个数字，表示集合元素。

输出格式

一行一个整数，即最小集合数量对 $10^9+9$ 取模的结果。

3 
1 
2 1 2

3

10 
2 
6 3 4 5 6 7 8 
2 5 6

7

提示

【样例解释】

• 对于第一个样例，集合为 $\{1,2\},\{3\},\{1,2,3\}$。

• 对于第二个样例，另外的 $5$ 个集合为 $\{1, 2, 9, 10\},\{1,2,3,4,7,8,9,10\},\{1,2,3,4,5,6,7,8,9,10\},\{3,4,7,8\},\{1,2,5,6,9,10\}$。

【数据范围与约定】

• 对于 $40\%$ 的数据，满足 $n \le 30$，答案不超过 $5000$。

• 对于 $100 \%$ 的数据，满足 $1\le n \le 2\times 10^5,1\le M \le 50$。