题目描述

在一个废弃的阁楼里放置有 $n$ 个箱子，这些箱子里存放着 $m$ 种玩具。对于第 $i$ 个箱子，它里面有 $k_i$ 个玩具（不同的箱子里可能有相同的玩具）。

现在你需要选出一部分箱子，使得它们中共有 $m$ 种玩具（即所有种类的玩具都包含）。求选择的方案总数（$\bmod\ 10^9+7$）。

输入格式

输入第一行包含两个整数 $n,m$。

接下来的 $n$ 行，每行首先输入一个整数 $k_i$；接下来 $k_i$ 个数表示第 $i$ 个箱子里所含的玩具情况。

输出格式

输入一行一个整数，为方案总数（$\bmod\ 10^9+7$）。

3 3
3 1 2 3
3 1 2 3
3 1 2 3

7

3 3
1 1
1 2
1 3

1

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

6

提示

数据规模与约定

• 对于 $50\%$ 的数据，保证 $n\le 100$，$m\le 15$；
• 对于 $70\%$ 的数据，保证 $m\le 15$；
• 对于 $100\%$ 的数据，保证 $1\le n\le 1\times 10^6$，$1\le m\le 20$，$0\le k_i\le m$。

说明

• 题目译自 COCI2011-2012 CONTEST #6 T6 KOŠARE。
• 感谢 @一扶苏一 的翻译支持！