/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
2 次元平面上に x 軸と平行な直線が m 本と y 軸と平行な直線が n 本引いてあります。 x 軸と平行な直線のうち下から i 番目は y = y_i で表せます。 y 軸と平行な直線のうち左から i 番目は x = x_i で表せます。
この中に存在しているすべての長方形についてその面積を求め、 合計を 10^9+7 で割ったあまりを出力してください。
つまり、1\leq i < j\leq n と 1\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
この入力を図にすると、以下のようになります。
長方形 A,B,...,I それぞれの面積を合計すると 60 になります。
入力例 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:
The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.
Sample Input 2
6 5 -790013317 -192321079 95834122 418379342 586260100 802780784 -253230108 193944314 363756450 712662868 735867677
Sample Output 2
835067060