問題文

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$
• 入力される値はすべて整数である。

入力例 1Copy

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

出力例 1Copy

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$となります。

入力例 2Copy

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

出力例 2Copy

999999571

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