题目描述

设 $A=\{1,2,\cdots,n\}$，给定 $m$ 个集合 $S_1, S_2, \cdots, S_m$，每个集合都是 $A$ 的子集，我们希望从这些集合中选出一些，使得它们的并集等于 $A$，请统计有多少种不同的选择方案？答案可能很大，取模 $10^9+7$ 的余数。

输入格式

第一行：两个整数 $n$ 和 $m$。 接下来 $2m$ 行，每两行代表一个集合，

• 前一行只有一个整数 $k_i$，表示第 $i$ 个集合中有多少元素，
• 后一行有 $k_i$ 个不同的正整数，表示第 $i$ 个集合的各元素。

输出格式

单个整数表示答案。

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

6

数据范围

• 对于的 $20\%$ 的数据，$1\leq n\leq 10$，$1\leq m\leq 10^3$；
• 对于的 $50\%$ 的数据，$1\leq n\leq 15$，$1\leq m\leq 10^4$；
• 对于的 $100\%$ 的数据，$1\leq n\leq 22$，$1\leq m\leq 10^5$。