Description

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$).

Input Format

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 Format

Output one integer: the total number of valid selections ($\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

Hint

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 CONTEST #6 T6 KOŠARE.
• Thanks to @一扶苏一 for translation support.

Translated by ChatGPT 5