19369번 - Welcome to ICPCCamp 2017 다국어

문제

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)$.

제한

힌트