만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

ICPCCamp 2017에 오신 것을 환영합니다

시간 제한1초메모리 제한512 MB

요약
n개의 대회 순위표와 마지막 결승 순위가 주어질 때, (X, Y)-규칙으로 만들 수 있는 ICPCCamp 팀 집합의 개수를 10^9+7로 나눈 나머지로 구합니다.
난이도

어려움10점 중 8점

유형
조합론, 그리디, 배열
정답자
아직 제출이 없습니다

문제

ICPCCamp 팀은 블로그에 나온 신비로운 (X,Y)(X, Y) 규칙에 따라 뽑히는 경우가 많다 (?).

mm개의 팀에는 1,2,…,m1, 2, \dots, m번 번호가 붙어 있다. 이 중에서 ICPCCamp 팀을 고르기 위해 (n+1)(n + 1)번의 선발 대회가 열린다. ii번째 대회에 참가하는 팀 수는 kik_i이다. 마지막 (n+1)(n + 1)번째 대회는 매우 중요한 EasyCamp-Final이므로 항상 kn+1=mk_{n + 1} = m이다. ii번째 대회의 순위표는 ri,1,ri,2,…,ri,kir_{i, 1}, r_{i, 2}, \dots, r_{i, k_i}이며, 이는 팀 ri,jr_{i, j}가 그 대회에서 jj등을 했다는 뜻이다.

(X,Y)(X, Y) 규칙은 다음과 같이 동작한다. 먼저 음이 아닌 정수 XX, YY와 {1,2,…,n}\{1, 2, \dots, n\}의 순열 P={p1,p2,…,pn}P = \{p_1, p_2, \dots, p_n\}을 고른다. 그다음 목록 {rn+1,1,…,rn+1,Y,rp1,1,rp2,1,…,rpn,1,rp1,2,rp2,2,…,rpn,2,… }\{r_{n + 1, 1}, \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\}에서 처음 나오는 서로 다른 X+YX+Y개의 팀을 ICPCCamp 팀으로 뽑는다. 즉 목록은 EasyCamp-Final의 앞 YY개 팀으로 시작하고, 이어서 PP의 순서대로 처음 nn개 대회의 1등 팀, 같은 순서로 2등 팀이 나열되는 식으로 진행된다.

Bobo는 XX, YY, PP를 자유롭게 고를 수 있을 때, 가능한 ICPCCamp 팀 집합의 개수를 109+710^9+7로 나눈 나머지로 알고 싶어 한다.

다가오는 World Finals에서 즐거운 시간 보내세요!

입력

입력은 0개 이상의 테스트 케이스로 이루어지며, 파일의 끝에서 끝난다. 각 테스트 케이스는 다음과 같다.

첫 줄에 정수 nn, mm (0≤n≤2⋅1050 \leq n \leq 2 \cdot 10^5, 1≤m≤2⋅1051 \leq m \leq 2 \cdot 10^5)이 주어진다.

이어지는 nn개의 줄 중 ii번째 줄에는 정수 kik_i와 그 뒤에 kik_i개의 정수 ri,1,ri,2,…,ri,kir_{i, 1}, r_{i, 2}, \dots, r_{i, k_i} (1≤ki≤m1 \leq k_i \leq m)가 주어진다.

마지막 줄에는 mm개의 정수 rn+1,1,rn+1,2,…,rn+1,mr_{n + 1, 1}, r_{n + 1, 2}, \dots, r_{n + 1, m} (1≤ri,j≤m1 \leq r_{i, j} \leq m)이 주어진다. 각 ii에 대해 ri,1,…,ri,kir_{i, 1}, \dots, r_{i, k_i}는 서로 다르다.

모든 테스트 케이스에 걸쳐 kik_i의 합과 mm의 합은 각각 2⋅1052 \cdot 10^5을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 집합의 개수를 109+710^9+7로 나눈 나머지를 정수 하나로 출력한다.

예제1

  1. 예제 1

    입력
    2 3
    2 1 3
    3 2 1 3
    2 1 3
    0 3
    1 2 3
    
    예상 출력
    5
    4