← 返回题目列表

AtCoder · arc071_b

D. 三个井号

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

在二维平面上,有 m 平行于 x 轴,以及 n 平行于 y 轴。 在与 平行的直线中 x 轴, i从底部开始的第一个表示为 y = y_i。 同样,在平行于 y 轴, i左起第一个表示为 x = x_i.

对于由这些线形成的每个矩形,找到其面积,并打印总面积模 10^9+7.

也就是说,对于每个四元组 (i,j,k,l) 满意 1\leq i < j\leq n 和 1\leq k < l\leq m,求直线形成的矩形的面积 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

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