Košare
레이팅 미적용의견: 0
\(6^{th}\) round, April \(14^{th}\), 2012
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.
In test cases worth 50% of total points, \(N \le 100\) and \(M \le 15\) will hold.
In test cases worth 70% of total points, \(N \le 1\,000\,000\) and \(M \le 15\) will hold.
The first line of input contains two integers N and M (\(1 \le N \le 1\,000\,000\), \(1 \le M \le 20\)).
Each of the following N lines contains an integer K_{i} (\(0 \le K_{i} \le M\)) followed by K_{i} 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.
3 3
3 1 2 3
3 1 2 3
3 1 2 373 3
1 1
1 2
1 314 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 56평가 및 의견
Košare
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Košare