프로그램 명: coci_kosare
제한시간: 2 초
미코는 다락에서 잃어버린 장난감이 담긴 N 개의 박스를 발견 했다.
각 박스에는 1 에서 M 까지 번호가 붙은 서로다른 장난감이 담겨 있다. 하지만 하나의 장난감이 여러 박스에 여러개 존재할 수 있다.
미코는 여러개의 박스 중에 각 장남감 종류가 적어도 하나씩 만 존재하게 박스를 선택한 후 나머지 박스를 버리려고 한다.
미코가 선택 할 수 있는 방법의 수를 결정하시오.
입력
- 첫 라인은 두 정수 N,M 이 주어진다.(1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 20).
- 다음 N 줄에 걸쳐 첫 줄에는 정수 Ki(0 ≤ Ki ≤ M) 가 주어진 후 [1 .. M] 중 K 개의 서로다른 정수가 주어진다.
Mirko found N boxes with various forgotten toys at his attic. There are M different toys, numbered 1 through M, but each of those can appear multiple times across various boxes.
Mirko decided that he will choose some boxes in a way that there is at least one toy of each kind present, and throw the rest of the boxes away.
Determine the number of ways in which Mirko can do this.
입력
- The first line of input contains two integers N and M (1 ≤ N ≤ 1 000 000, 1 ≤ M ≤ 20).
- Each of the following N lines contains an integer Ki (0 ≤ Ki ≤ M) followed by Ki distinct integers from interval [1, M], representing the toys in that box.
출력
The first and only line of output should contain the requested number of ways modulo 1 000 000 007.
입출력 예
input
3 3
3 1 2 3
3 1 2 3
3 1 2 3
output
7
input
3 3
1 1
1 2
1 3
output
1
input
4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5
output
6
출처:coci 2012 6/6
[질/답]
[제출 현황]
[푼 후(0)]