시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 6 | 3 | 3 | 50.000% |
ICPCCamp teams are often selected by a mysterious $(X, Y)$-rule described in a blog (?).
There are $(n + 1)$ selection contests held to choose ICPCCamp team among $m$ teams conveniently labeled with $1, 2, \dots, m$. The number of teams attending the $i$-th contest is $k_i$. As the last (the $(n + 1)$-th) contest called EasyCamp-Final is very important, $k_{n + 1} = m$ always holds. The scoreboard of the $i$-th contest is $r_{i, 1}, r_{i, 2}, \dots, r_{i, k_i}$ which indicates that team $r_{i, j}$ has rank $j$ in the contest.
The $(X, Y)$-rule works as follows. Firstly, two non-negative integers $X$ and $Y$ and a permutation $P = \{p_1, p_2, \dots, p_n\}$ of $\{1, 2, \dots, n\}$ are chosen. After that, the first $X+Y$ distinct teams in the list $\{r_{n + 1, 1}, r_{n + 1, 2}, \dots, r_{n + 1, Y}, r_{p_1, 1}, r_{p_2, 1}, \dots, r_{p_n, 1}, r_{p_1, 2}, r_{p_2, 2}, \dots, r_{p_n, 2}, \dots\}$ will be selected as ICPCCamp team. In other words, the list goes in the following order: the first $Y$ EasyCamp-Final teams, then the top teams from the first $n$ contests in the order defined by $P$, then the second teams from the first $n$ contests in the same order, and so on.
Bobo would like to know the number of possible sets of ICPCCamp teams modulo $(10^9+7)$ if he can choose $X$, $Y$ and $P$ arbitrarily.
Wish you enjoy yourself in the upcoming World Finals!
The input contains zero or more test cases, and is terminated by end-of-file. For each test case:
The first line contains two integers $n$ and $m$ ($0 \leq n \leq 2 \cdot 10^5$, $1 \leq m \leq 2 \cdot 10^5$).
The $i$-th of following $n$ lines contains an integer $k_i$ followed by $k_i$ integers $r_{i, 1}, r_{i, 2}, \dots, r_{i, k_i}$ ($1 \leq k_i \leq m$).
The last line contains $m$ integers $r_{n + 1, 1}, r_{n + 1, 2}, \dots, r_{n + 1, m}$ ($1 \leq r_{i, j} \leq m$, and for each $i$, the numbers $\{r_{i, 1}, r_{i, 2}, \dots, r_{i, k_i}\}$ are distinct).
It is guaranteed that both the sum of $k_i$ and the sum of $m$ do not exceed $2 \cdot 10^5$.
For each test case, output an integer which denotes the number of sets modulo $(10^9+7)$.
2 3 2 1 3 3 2 1 3 2 1 3 0 3 1 2 3
5 4