P6442 [COCI 2011/2012 #6] KOŠARE

In an abandoned attic, there are $n$ boxes, and these boxes store $m$ types of toys. For the $i$-th box, it contains $k_i$ toys (different boxes may contain the same toy). Now you need to choose some of the boxes so that, among the chosen boxes, there are all $m$ types of toys (that is, every toy type is included). Find the total number of ways to choose such boxes ($\bmod\ 10^9+7$).

The first line contains two integers $n, m$. The next $n$ lines each start with an integer $k_i$; then $k_i$ numbers describe which toys are contained in the $i$-th box.

Output one integer: the total number of valid selections ($\bmod\ 10^9+7$).

#### Constraints - For $50\%$ of the testdata, $n\le 100$, $m\le 15$. - For $70\%$ of the testdata, $m\le 15$. - For $100\%$ of the testdata, $1\le n\le 1\times 10^6$, $1\le m\le 20$, $0\le k_i\le m$. #### Notes - **This problem is translated from [COCI2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #6](https://hsin.hr/coci/archive/2011_2012/contest6_tasks.pdf) *T6 KOŠARE***. - Thanks to @[一扶苏一](https://www.luogu.com.cn/user/65363) for translation support. Translated by ChatGPT 5