시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.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)$.

예제 입력 1

2 3
2 1 3
3 2 1 3
2 1 3
0 3
1 2 3

예제 출력 1

5
4