문제
태현이는 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로 나눈 나머지를 출력한다.
예제1
입력
33
3123
3123
3123
출력
7
예제2
입력
33
11
12
13
출력
1
예제3
입력
45
223
212
41235
41245
출력
6
출처
COCI 2011/2012 contest6 6