Problem Description

At W University, there are \(N\\) competitive programming clubs. The number of members in club \(i\\ (0 \\leq i \\leq N-1)\\) is \(K\_i\\), and the rating of the \(j\\ (0 \\leq j \\leq K\_i-1)\\)th member is \(A\_{i,j}\\).

Every day, disputes arise over which club gets to use the computer room, and clubs settle their disputes through competitive programming duels. The duels are conducted by members of each club in turn, with 1-on-1 matches. If one club has fewer members, its members will rotate to match the number of members of the larger club until the duel is over.

The "intensity" of a duel between club \(X\\) and club \(Y\\) is represented by the sum of the products of the ratings of the dueling members. In formula, it is expressed as follows:

• For sequences \(A\_X, A\_Y\\), the value of \(\\sum{(A\_{X, {j \\mod K\_X}} \\times A\_{Y, {j \\mod K\_Y}})}\\) where \(0 \\leq j \\leq \\max(K\_X, K\_Y)-1\\).

Now, \(Q\\) duels have taken place, and the \(i\\ (0 \\leq i \\leq Q-1)\\)th duel was between club \(X\_i\\) and club \(Y\_i\\). For each duel, find the "intensity". Note that the answer can be very large, so output it modulo \(10^9+7\\).

Input Format

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

\(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}\)

Output Format

For each query, output the answer modulo \(10^9+7\\).

Sample Input and Output

Sample Input #1

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

Sample Output #1

77
70
53

Sample Input #2

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

Sample Output #2

999999571

Notes/Hints

Constraints

• \(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\\)
• All input values are integers.

Sample Explanation 1

For example, for the second query, focus on sequences \(A\_0, A\_2\\) with \(K\_0=1, K\_2=3\\), the answer is \(A\_{0,0} \\times A\_{2,0} + A\_{0,0} \\times A\_{2,1} + A\_{0,0} \\times A\_{2,2} = 70\\). For the third query, focus on sequences \(A\_1, A\_2\\) with \(K\_1=2, K\_2=3\\), the answer is \(A\_{1,0} \\times A\_{2,0} + A\_{1,1} \\times A\_{2,1} + A\_{1,0} \\times A\_{2,2} = 53\\).

Sample Explanation 2

Output the answer modulo \(10^9+7\\).

见题面 Input 部分

见题面 Output 部分