Problem Description

You have a sequence of $K$ numbers from $a_1$ to $a_K$. The length of sequence $a_i$ is $n_i$, and the $j$-th number from the beginning is $a_{i,j}$.

You decided to create a new sequence $x$ using these sequences. Initially, the length of $x$ is $0$.

You will perform $Q$ operations. In the $i$-th operation, you replace $x$ with the concatenation of $x$ and sequence $a_{b_i}$ at the end of $x$.

Let $|x|$ denote the length of $x$. In the final $x$, find how many pairs of integers $(i,j)$ satisfy both $1 \leq i < j \leq |x|$ and $x_i > x_j$. Since this number can be very large, output it modulo $10^9$.

Input Format

The input is given from the standard input in the following format:

$ K $ $ n_1 $ $ a_{1,1} $ $ a_{1,2} $ $\cdots$ $ a_{1,{n_1}} $ $ n_2 $ $ a_{2,1} $ $ a_{2,2} $ $\cdots$ $ a_{2,{n_2}} $ $\vdots$ $ n_K $ $ a_{K,1} $ $ a_{K,2} $ $\cdots$ $ a_{K,{n_K}} $ $ Q $ $ b_1 $ $ b_2 $ $\cdots$ $ b_Q $

Output Format

Output the number of pairs $(i,j)$ in the final $x$ that satisfy both $1 \leq i < j \leq |x|$ and $x_i > x_j$, modulo $10^9$.

Sample Input and Output

Sample Input #1

2
3
1 3 2
2
5 4
2
1 2

Sample Output #1

2

Sample Input #2

10
8
16 6 15 10 18 13 17 11
13
4 10 6 4 14 17 13 9 3 9 4 8 14
11
11 17 12 3 13 8 10 11 18 2 19
10
18 11 16 19 4 17 7 3 5 8
3
3 10 9
13
8 17 20 8 20 1 5 17 4 16 18 20 4
15
11 2 1 16 8 17 4 7 3 6 4 13 16 16 16
2
12 12
8
7 14 7 5 8 17 19 4
15
3 6 1 16 11 5 3 15 9 15 12 15 5 19 7
20
4 3 7 6 1 8 2 3 9 8 6 3 10 9 7 7 3 2 2 10

Sample Output #2

12430

Notes/Hints

Constraints

• All given inputs are integers.
• $1 \leq K, Q \leq 10^5$
• $1 \leq n_i \leq 10^5$
• $1 \leq a_{i,j} \leq 20$
• $1 \leq b_i \leq K$
• $\sum_{i=1}^{K} n_i \leq 3 \times 10^5$

Sample Explanation 1

• Initially, $x$ is empty.
• After the first operation, $x$ is replaced with the sequence $(1,3,2)$.
• After the second operation, $x$ is replaced with the sequence $(1,3,2,5,4)$.
• The pairs $(i,j)$ that satisfy both $1 \leq i < j \leq |x|$ and $x_i > x_j$ are $(2,3)$ and $(4,5)$, totaling 2 pairs.

见题面 Input 部分

见题面 Output 部分