COCI 2011/2012 contest6 6- 장난감 상자 > 문제은행 : 정보올림피아드&알고리즘




3658 : 장난감 상자

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
2 회   
시도횟수
4 회   

문제

태현이는 M종류의 장난감을 모으려고 한다. 태현이는 장난감을 모으기 위해 마트에서 장난감 상자를 사려고 한다. 마트에서는 N종류의 장난감 상자를 팔고 있으며 각 상자에는 M종류의 장난감 중 일부가 들어있다. 서로 다른 장난감 상자가 같은 종류의 장난감 구성을 이룰 수 있다.

 

같은 장난감 상자를 여러 개 사는 것은 낭비이므로 태현이는 각 장난감 상자는 사지 않거나 하나만 살 것이다. 태현이가 모든 종류의 장난감을 모으도록 장난감을 사는 방법의 수를 구하는 프로그램을 작성하여라.

 


입력형식

첫 번째 줄에 장난감 상자의 수 N과 장난감의 종류 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 20)

두 번째 줄부터 N개의 줄에는 각 장난감 상자의 구성 K T1 T2 … TK가 주어진다. K는 장난감 상자에 들어있는 장남감의 수이며 T1, T2, …, TK는 장난감 상자에 들어있는 장난감의 번호이다. T1, T2, …, TK는 1 이상 M 이하의 서로 다른 정수이다.

 


출력형식

첫 번째 줄에 태현이가 장난감 상자를 사는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

 


입력 예

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

출력 예

7

입력 예

3 3
1 1
1 2
1 3

출력 예

1

입력 예

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

출력 예

6


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP