Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Candy Boxes

By zobayer · 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 N boxes of Fox’s candies, and the M different colored candies in those boxes numbered from 1 to M. 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 T (T <= 20).

The first line of each test case will contain two integers N (1 <= N <= 10^5) and M (1 <= M <= 20) denoting the number of boxes and number of different colored candies respectively.

Each of the following N lines will start with an integer p (0 <= p <= M) followed by p distinct integers in the range [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. Please check the sample input-output section for formatting details.

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.

    Discussion

    Statistics


    100% Solution Ratio

    BerlekampMassyEarliest, 5M ago

    kzvd4729Fastest, 0.2s

    kzvd4729Lightest, 4.5 MB

    Deshi_TouristShortest, 912B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.