K - 転倒数 解説 /

実行時間制限: 5 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

あなたは a_1 から a_K の K 個の数列を持っています。 数列 a_i の長さは n_i で、先頭から j 番目の数は a_{i,j} です。

あなたはこれらの数列を使って、新しい数列 x を作ることにしました。 はじめ、x の長さは 0 です。

あなたは Q 回操作を行います。 i 回目の操作では、x を x の末尾に数列 a_{b_i} を連結したものに置き換えます。

x の長さを |x| と書くことにします。 最終的な x において、1 \leq i < j \leq |x| と x_i > x_j の両方を満たすような整数の組 (i,j) がいくつあるかを求めてください。 これは非常に大きくなりうるので、10^9 で割ったあまりを出力してください。

制約

  • 与えられる入力は全て整数
  • 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

入力

入力は以下の形式で標準入力から与えられる。

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

出力

最終的な x における 1 \leq i < j \leq |x| と x_i > x_j の両方を満たすような (i,j) の個数を 10^9 で割ったあまりを出力せよ。

入力例 1

2
3
1 3 2
2
5 4
2
1 2

出力例 1

2
  • x ははじめ空です。
  • 1 回目の操作により、x が x と (1,3,2) を連結した数列である (1,3,2) に置き換えられます。
  • 2 回目の操作により、x が x と (5,4) を連結した数列である (1,3,2,5,4) に置き換えられます。
  • 1 \leq i < j \leq |x| と x_i > x_j の両方を満たす (i,j) の組は (2,3) と (4,5) の 2 つです。

入力例 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

出力例 2

12430

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

You have K number sequences called a_1 through a_K. The length of the sequence a_i is n_i, and its j-th element is a_{i,j}.

Using those sequences, you have decided to make a new sequence x. Initially, the length of x is 0.

You will do Q operations. In the i-th of them, you will replace x with the result of concatenating the sequence a_{b_i} to the end of x.

Let |x| denotes the length of x. Find the number of pairs of integers (i,j) such that 1 \leq i < j \leq |x| and x_i > x_j after all the operations. Since it can be enormous, print it modulo 10^9.

Constraints

  • All values in input 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

Input

Input is given from 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

Print the number of pairs of integers (i,j) such that 1 \leq i < j \leq |x| and x_i > x_j after all the operations, modulo 10^9.

Sample Input 1

2
3
1 3 2
2
5 4
2
1 2

Sample Output 1

2
  • Initially, x is empty.
  • In the 1-st operation, x is replaced with the concatenation of x and (1,3,2), that is, (1,3,2).
  • In the 2-st operation, x is replaced with the concatenation of x and (5,4), that is, (1,3,2,5,4).
  • Now, there are two pairs (i,j) such that 1 \leq i < j \leq |x| and x_i > x_j: (2,3) and (4,5).

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