[Pre-QNOI 2022#02] Chiều nay không có em

View as PDF

Submit solution


Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

__BruteForce__ tặng cho crush TB một bộ gồm \(n\) hộp quà, mỗi hộp gồm một số bé pokemon nhồi bông rất dễ thương và đáng yêu. Tuy nhiên, sau khi kiểm kê một lượt, TB nhận thấy rằng trong \(n\) hộp này có khá nhiều pokemon cùng loại bị trùng lặp, và tổng cộng chỉ có \(m\) loại pokemon khác nhau (được đánh số từ \(1\) đến \(m\)) trong tất cả các hộp. TB muốn chọn và giữ lại một vài hộp quà sao cho lực lượng pokemon trong các hộp đó phân bố đủ \(m\) loại khác nhau, sau đó cô sẽ đem các hộp còn lại cất vào nhà kho để tiết kiệm diện tích cho phòng ngủ của cô. Bạn hãy lập trình giúp TB tính toán giúp tổng số cách chọn khác nhau thỏa mãn yêu cầu của cô nhé!


Input

  • Dòng đầu chứa hai số nguyên dương \(n\) và \(m\).
  • Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa một số nguyên \(k_i\leq m\) thể hiện số lượng pokemon ở hộp quà thứ \(i\), theo sau là \(k_i\) số nguyên dương phân biệt thể hiện chủng loại của từng pokemon.

Output

  • Một số nguyên thể hiện số cách chọn thỏa mãn. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra phần dư của nó khi chia cho \(10^9+7\).

Ví dụ

Sample input 1
3 3
3 1 2 3
3 1 2 3
3 1 2 3
Sample output 1
7
Sample input 2
3 3
1 1
1 2
1 3
Sample output 2
1
Sample input 3
4 5
2 2 3
2 1 2
4 1 2 3 5
4 1 2 4 5
Sample output 3
6

Ràng buộc

  • Subtask 1 (20% số điểm): \(n\leq 20\), \(m\leq 15\).
  • Subtask 2 (50% số điểm): \(n\leq 100\), \(m\leq 15\).
  • Subtask 3 (15% số điểm): \(n\leq 10^6\), \(m\leq 15\).
  • Subtask 4 (15% số điểm): \(n\leq 10^6\), \(m\leq 20\).