Problem Description

In an abandoned attic, there are $n$ boxes containing $m$ types of toys. For the $i$-th box, it contains $k_i$ toys (different boxes may contain the same toys).

You need to select some boxes such that they collectively contain all $m$ types of toys. Find the total number of such selection schemes modulo $10^9+7$.

Input Format

The first line of input contains two integers $n$ and $m$.

The next $n$ lines, each starts with an integer $k_i$, followed by $k_i$ numbers indicating the toys contained in the $i$-th box.

Output Format

Output a single integer, which is the total number of schemes modulo $10^9+7$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

7

Sample Input #2

3 3
1 1
1 2
1 3

Sample Output #2

1

Sample Input #3

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

Sample Output #3

6

Notes

Data Size and Constraints

• For $50\%$ of the data, $n \le 100$ and $m \le 15$;
• For $70\%$ of the data, $m \le 15$;
• For $100\%$ of the data, $1 \le n \le 1 \times 10^6$, $1 \le m \le 20$, $0 \le k_i \le m$.

Notes

• The problem is translated from COCI2011-2012 CONTEST #6 T6 KOŠARE.
• Thanks to @一扶苏一 for translation support!

见题面 Input 部分

见题面 Output 部分