Counting Box Selection Ways

In an abandoned attic, there are \( n \) boxes containing toys of \( m \) different types. The \( i\)th box holds some toys, and note that different boxes may contain the same toy types. You are required to select a subset of boxes such that together they contain all \( m \) types of toys.

More formally, each box \( i \) is described by an integer \( k_i \) (the number of toys in the box) followed by \( k_i \) integers representing the toy types it contains (each toy type is an integer between 1 and \( m \)). A selection of boxes is valid if the union of the toy types in the chosen boxes is \( \{1, 2, \dots, m\} \). Compute the total number of valid selections, modulo \(10^9+7\).

inputFormat

The first line contains two integers \( n \) and \( m \) representing the number of boxes and the number of toy types.

Then \( n \) lines follow. The \( i\)th line starts with an integer \( k_i \) which is the number of toys in the \( i\)th box, followed by \( k_i \) integers indicating the toy types in that box.

outputFormat

Output a single integer, the number of ways to select a subset of boxes such that all \( m \) toy types are included, modulo \(10^9+7\).

sample

3 2
1 1
1 2
2 1 2

5