H - Doki Doki Programming Clubs! Editorial /

Time Limit: 2 sec / Memory Limit: 512 MB

配点 : \(200\) 点

問題文

W大学ではサークル活動が盛んで、 \(N\) 個の競技プログラミングサークルがあります。 サークル \(i\ (0 \leq i \leq N-1)\) の部員の人数は \(K_i\) であり、その \(j\ (0 \leq j \leq K_i-1)\) 番目の部員のレートは \(A_{i,j}\) です。

毎日、どのサークルがパソコン室を使うかで言い争いになり、サークル同士は競技プログラミング対決で決着をつけます。対決はそれぞれのサークルの部員が順番に1対1の勝負を行いますが、人数が少ない方のサークルの部員は多い方の人数に合わせて、対決が終わるまでローテーションします。

サークル \(X\) とサークル \(Y\) の対決の「白熱度」は対決する部員のレートの積の総和で表されます。式で表すと、以下のようになります。

  • 数列\(A_X,A_Y\)について、\(0 \leq j \leq \max(K_X,K_Y)-1\)における\(\sum{(A_{X,\ {j \mod K_X}} \times A_{Y,\ {j \mod K_Y}})}\)の値

今、対決が \(Q\) 回行われ、\(i\ (0 \leq i \leq Q-1)\) 番目の対決はサークル \(X_i\) とサークル \(Y_i\) の対決でした。それぞれの対決について、「白熱度」を求めてください。ただし、答えは非常に大きくなることがあるので、\(10^9+7\)で割ったあまりを答えること。

制約

  • \(2 \leq N \leq 200000\)
  • \(1 \leq K_i\)
  • \(\sum K_i \leq 200000\)
  • \(1 \leq A_{i,j} \leq 10^9\)
  • \(1 \leq Q \leq 200000\)
  • \(0 \leq X_i, Y_i \leq N-1\)
  • \(X_i \neq Y_i\)
  • 入力される値はすべて整数である。

入力

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

\(N\)
\(K_0\ A_{0,0}\ A_{0,1}\ \dots\ A_{0,K_0-1}\)
\(K_1\ A_{1,0}\ A_{1,1}\ \dots\ A_{1,K_1-1}\)
\(\vdots\)
\(K_{N-1}\ A_{{N-1},0}\ A_{{N-1},1}\ \dots\ A_{{N-1},K_{N-1}-1}\)
\(Q\)
\(X_0\ Y_0\)
\(X_1\ Y_1\)
\(\vdots\)
\(X_{Q-1}\ Y_{Q-1}\)

出力

それぞれのクエリに対して答えを\(10^9+7\)で割ったあまりを出力してください。


入力例 1

3
1 7
2 5 6
3 3 3 4
3
0 1
0 2
1 2

出力例 1

77
70
53

例えば、二つ目のクエリに対しては、数列\(A_0,A_2\)に注目し\(K_0=1,K_2=3\)より答えは\(A_{0,0} \times A_{2,0}+A_{0,0} \times A_{2,1}+A_{0,0} \times A_{2,2}=70\)となります。

三つ目のクエリに対しては、数列\(A_1,A_2\)に注目し\(K_1=2,K_2=3\)より答えは\(A_{1,0} \times A_{2,0}+A_{1,1} \times A_{2,1}+A_{1,0} \times A_{2,2}=53\)となります。


入力例 2

2
3 1000000000 999999999 999999998
10 1 2 3 4 5 6 7 8 9 10
1
0 1

出力例 2

999999571

\(10^9+7\)で割ったあまりを出力してください。