AtCoder Regular Contest 071

D - 井井井 / ###


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 500

問題文

2 次元平面上に x 軸と平行な直線が m 本と y 軸と平行な直線が n 本引いてあります。 x 軸と平行な直線のうち下から i 番目は y = y_i で表せます。 y 軸と平行な直線のうち左から i 番目は x = x_i で表せます。

この中に存在しているすべての長方形についてその面積を求め、 合計を 10^9+7 で割ったあまりを出力してください。

つまり、1\leq i < j\leq n1\leq k < l\leq m を満たすすべての組 (i,j,k,l) について、 直線 x=x_i, x=x_j, y=y_k, y=y_l で囲まれる 長方形の面積を求め、合計を 10^9+7 で割ったあまりを出力してください。

制約

  • 2 \leq n,m \leq 10^5
  • -10^9 \leq x_1 < ... < x_n \leq 10^9
  • -10^9 \leq y_1 < ... < y_m \leq 10^9
  • x_i, y_i は整数である。

入力

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

n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

出力

長方形の面積の合計を 10^9+7 で割ったあまりを 1 行に出力せよ。


入力例 1

3 3
1 3 4
1 3 6

出力例 1

60

この入力を図にすると、以下のようになります。

sample1-1

長方形 A,B,...,I それぞれの面積を合計すると 60 になります。

sample1-2


入力例 2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

出力例 2

835067060

Score : 500 points

Problem Statement

On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis. Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i. Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.

For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.

That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.

Constraints

  • 2 \leq n,m \leq 10^5
  • -10^9 \leq x_1 < ... < x_n \leq 10^9
  • -10^9 \leq y_1 < ... < y_m \leq 10^9
  • x_i and y_i are integers.

Input

Input is given from Standard Input in the following format:

n m
x_1 x_2 ... x_n
y_1 y_2 ... y_m

Output

Print the total area of the rectangles, modulo 10^9+7.


Sample Input 1

3 3
1 3 4
1 3 6

Sample Output 1

60

The following figure illustrates this input:

sample1-1

The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.

sample1-2


Sample Input 2

6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677

Sample Output 2

835067060

Submit提出する