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。