AT_past202010_k 転倒数

[problemUrl]: https://atcoder.jp/contests/past202010-open/tasks/past202010_k あなたは $ 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\ \ x_j $ の両方を満たすような整数の組 $ (i,j) $ がいくつあるかを求めてください。 これは非常に大きくなりうるので、$ 10^9 $ で割ったあまりを出力してください。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \ x_j $ の両方を満たすような $ (i,j) $ の個数を $ 10^9 $ で割ったあまりを出力せよ。

### 注意 この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 与えられる入力は全て整数 - $ 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 \- $ x $ ははじめ空です。 - $ 1 $ 回目の操作により、$ x $ が $ x $ と $ (1,3,2) $ を連結した数列である $ (1,3,2) $ に置き換えられます。 - $ 2 $ 回目の操作により、$ x $ が $ x $ と $ (5,4) $ を連結した数列である $ (1,3,2,5,4) $ に置き換えられます。 - $ 1\ \leq\ i\ \ x_j $ の両方を満たす $ (i,j) $ の組は $ (2,3) $ と $ (4,5) $ の $ 2 $ つです。