Limits 1s, 512 MB

Mehdi won a million dollars lottery, and not knowing what to do with such big amounts of money, he bought a ton of Fox’s 180g candy boxes. Each of these boxes should contain 40 candies, but Mehdi has eaten all the candies from a few of the boxes already.

The boxes have candies of various different colors and flavors. Mehdi decided to give some of these boxes as gifts to the kids in his neighborhood. He wanted to make sure that he has gifted at least one piece of candy of each color.

Let’s imagine that there are NN boxes of Fox’s candies, and the MM different colored candies in those boxes numbered from 1 to MM. Please note that each color can appear zero or more times in each box. Since there are a lot of boxes, we need your help to calculate the number of ways Mehdi could choose a set of boxes that would contain at least one candy of each color across the set of chosen boxes.

Input

The first line of the input file will contain the number of test cases TT (T20T \le 20).

The first line of each test case will contain two integers NN (1N1051 \le N \le 10^5) and MM (1M201 \le M \le 20) denoting the number of boxes and number of different colored candies respectively.

Each of the following NN lines will start with an integer pp (0pM0 \le p \le M) followed by pp distinct integers in the range [1,M][1, M], representing the different candies present in the corresponding box.

Output

For each test case, first print the serial number of the test case, followed by the requested number of ways. Since the output numbers can be very large, you have to print the numbers modulo 1000000007.

Sample

InputOutput
3
3 3
3 1 2 3
3 1 2 3
3 1 2 3
3 3
1 1
1 2
1 3
4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5
Case 1: 7
Case 2: 1
Case 3: 6

The input file is very large, please use faster IO.

Submit

Login to submit.

Statistics

80% Solution Ratio
BerlekampMassyEarliest, May '21
nusuBotFastest, 0.2s
kzvd4729Lightest, 4.5 MB
Deshi_TouristShortest, 912B
Toph uses cookies. By continuing you agree to our Cookie Policy.