← 返回题目列表

Codeforces · 611/G

G. 新年和蛋糕

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

Limak 是一只小北极熊。按照一些古老的传统,他的熊家准备了年糕。利马克喜欢蛋糕。

如您所知,年糕是一个有 n 个顶点的严格凸多边形。

父母不允许 Limak 吃超过一半的蛋糕,因为他会生病。经过一番思考,他们决定沿着 n·(n - 3) / 2 条对角线之一切蛋糕。然后利马克将得到一块不更大的棋子。

Limak 理解规则,但如果第二块碰巧更大,他不会高兴。利马克的失望将等于棋子面积之差乘以二。可以证明对于给定的约束它是整数。

有 n·(n - 3) / 2 种可能的情况。考虑所有这些并找到 Limak 失望值的总和,模 109 + 7。

输入

输入的第一行包含一个整数 n (4 ≤ n ≤ 500 000) - 表示蛋糕的多边形中的顶点数。

接下来的 n 行中的每一行都包含两个整数 xi 和 yi (|xi|, |yi| ≤ 109)——第 i 个点的坐标。

保证所有点都是不同的,多边形是严格凸的,并且点按顺时针顺序给出。

输出

打印 Limak 对所有可能情况的失望值模 109 + 7 的总和。

示例

输入 #1

5
2 4
2 7
5 7
5 4
3 -2

输出 #1

90

输入 #2

4
-1000000000 -5000000
0 1234567
1 1
-5 -100000000

输出 #2

525185196

输入 #3

8
-10 0
-6 6
0 10
6 6
10 0
6 -6
0 -10
-6 -6

输出 #3

5216

注意

在第一个样本中,Limak 的失望可能值为 0、18、18、24、30。