CF611G.New Year and Cake

Limak is a little polar bear. According to some old traditions, his bear family prepared a New Year cake. And Limak likes cakes.

As you may know, a New Year cake is a strictly convex polygon with n vertices.

Parents won't allow Limak to eat more than half of a cake because he would get sick. After some thinking they decided to cut a cake along one of n·(n - 3) / 2 diagonals. Then Limak will get a non-greater piece.

Limak understands rules but he won't be happy if the second piece happens to be much bigger. Limak's disappointment will be equal to the difference between pieces' areas, multiplied by two. It can be proved that it will be integer for the given constraints.

There are n·(n - 3) / 2 possible scenarios. Consider them all and find the sum of values of Limak's disappointment, modulo 109 + 7.

Limak 是一只小北极熊。根据一些古老的传统，他的熊家族准备了一个新年蛋糕。而 Limak 喜欢蛋糕。

如你所知，一个新年蛋糕是一个具有 $n$ 个顶点的严格凸多边形。

由于 Limak 吃得太多会生病，父母不允许他吃掉超过蛋糕一半的部分。经过一番考虑，他们决定沿该多边形的某一条对角线将蛋糕切开。随后，Limak 将得到其中面积不大于另一半的那一块。

Limak 理解这些规则，但如果另一块面积远大于他所得的那一块，他仍会不开心。Limak 的“失望值”定义为两块面积之差乘以 2。可以证明：在本题给定的约束条件下，该失望值必为整数。

共有 $n \cdot (n - 3) / 2$ 种可能的切割方案（即多边形的对角线总数）。请考虑所有这些方案，并求出所有情况下 Limak 失望值的总和，结果对 $10^9 + 7$ 取模。

The first line of the input contains a single integer n (4 ≤ n ≤ 500 000) — the number of vertices in the polygon denoting the cake.

Each of the next n lines contains two integers x__i and y__i (|x__i|, |y__i| ≤ 109) — coordinates of the i-th point.

It's guaranteed that all points are distinct, polygon is strictly convex and points are given in the clockwise order.

输入的第一行包含一个整数 $n$（$4 \leq n \leq 500\,000$），表示表示蛋糕的多边形的顶点数。

接下来的 $n$ 行中，每行包含两个整数 $x_i$ 和 $y_i$（$|x_i|, |y_i| \leq 10^9$），表示第 $i$ 个顶点的坐标。

保证所有顶点互不相同，该多边形为严格凸多边形，且各顶点按顺时针顺序给出。

Print the sum of values of Limak's disappointment over all possible scenarios modulo 109 + 7.

输出 Limak 在所有可能情形下的失望值之和对 $10^9 + 7$ 取模的结果。

In the first sample possible values of Limak's disappointment are 0, 18, 18, 24, 30.

在第一个样例中，Limak 的失望值可能为 $0,\,18,\,18,\,24,\,30$。