TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P4289
  • Problem
  • P4289Too Young
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 3s,256m
    Description

    When nidgd was young, he used to play with boxes and balls. In his mind, a large quantity of boxes was as magical as constellations in the sky, and each ball in box was identical to a star which belongs to the constellation. One day nidgd made a statistic. There were 𝒏 boxes and 𝒎 kinds of balls. Each box contained some different kinds of balls. One kind of balls could appear in multiple boxes. Empty boxes were accepted. The next day, nidgd wanted to go on a journey, and wanted to take every kind of balls. Distinctly, he needed to take at least one ball of each type. However, nidgd has some psychosis that if he is going to bring some balls, he would bring all the balls in the boxes together. So he could only take some boxes of balls to cover all types, despite that there might be some repetition. Then nidgd want to know: how many different plans of choosing boxes satisfied the condition? The answer might be very great, so please modulo 10^9 + 7.

    Input Format

    Input file is A.in. The first line of input contains two integers 𝒏 and 𝒎, the number of boxes and the number of ball types. Following that there are 𝒏 lines, each line describe a box. At the beginning of the 𝒊 𝒕𝒕 line is a integer 𝒌𝒊, the number of ball in the 𝒊th box. Then 𝒌𝒊 integers 𝒄𝒊𝒊, 𝒄𝒊𝒊, … 𝒄𝒊𝒌𝒊 , describe types of balls.

    Output Format

    Output file is A.out. Print a single integer as the answer modulo 10^9 + 7.

    Sample Input 1

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

    Sample Output 1

    7

    Sample Input 2

    20 16
    5 8 10 11 15 16 
    7 3 4 6 8 9 12 15 
    5 3 4 5 8 9 
    9 1 3 5 7 8 9 10 12 15 
    6 2 4 8 9 13 16 
    5 2 3 8 15 16 
    8 4 5 6 8 12 14 15 16 
    5 4 7 8 10 12 
    8 1 2 3 5 8 12 15 16 
    10 2 3 6 8 10 11 12 14 15 16 
    7 2 4 6 8 9 11 15 
    8 6 7 8 9 11 13 15 16 
    10 1 3 4 5 7 8 9 13 15 16 
    7 3 6 7 8 11 12 15 
    7 1 2 3 5 9 15 16 
    11 1 4 5 6 7 8 9 10 12 15 16 
    8 2 5 11 12 13 14 15 16 
    8 2 3 4 5 6 8 14 16 
    10 1 2 4 6 7 9 11 13 15 16 
    8 1 2 5 7 8 9 10 12 

    Sample Output 2

    925580

    Hint

    【Hint】 There are 3 boxes and 3 kinds of balls. Each box contains all kinds of balls. Each box can be chosen or not independently but it must choose at least one box. So we have 7 different plans.

    【Data Range】 There are 20% of test cases, 𝑛 ≤ 20, 𝑚 ≤ 16. There are 40% of test cases, 𝑛 ≤ 10^3, 𝑚 ≤ 16. There are 70% of test cases, 𝑛 ≤ 10^6, 𝑚 ≤ 16. All 100% of test cases, 𝑛 ≤ 10^6, 𝑚 ≤ 22, 0 ≤ 𝑘𝑖 ≤ 𝑚, 1 ≤ 𝑐𝑖𝑖 ≤ 𝑚.

    【Warning】 Huge input, scanf is too slow!