G. Silver Fences
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Rand has just won a silver medal in the International Olympiad in Informatics! Being the first silver medalist in the nation's history, he has earned great respect from the king. The king, very delighted, decided to reward Rand with "Trees of the Forbidden Fruit", a.k.a. apple trees.

There are $$$n$$$ apple trees on the nation's land. If we consider the nation as a Cartesian plane, then each tree can be viewed as a point with integral $$$x$$$ and $$$y$$$ coordinates. In addition, no tree is at the point $$$(0, 0)$$$, because that's the location of the king's castle.

"You shall build fences on the land to enclose apple trees," said the king. "After doing it subject to all my rules, all these trees will be awarded to you." The king's rules are as follows:

  1. Each fence is a line segment on the plane. A fence may have zero length.
  2. There should be exactly 4 fences built, 2 of which are made of silver, and the rest are made of wood.
  3. The 4 fences form the sides of a (possibly degenerate) rectangle. The sides should be in this order: silver fence, wooden fence, silver fence, wooden fence; i.e., the opposite sides are made of the same material.
  4. The king's castle, which is at $$$(0, 0)$$$, must be the midpoint of a silver fence.
  5. At least $$$n - 1$$$ trees are inside the rectangle formed by the fences (or on its border).

Since silver fences are very expensive, Rand wants to minimize the total length of silver fences used. Wooden fences, on the other hand, are extremely cheap, so the lengths of wooden fences don't matter. He noticed that if there is a possible way to build fences that satisfy the king's rules, then there must be one that has the minimum total length of silver fences.

As a professional programmer, Rand immediately wrote a program that calculates the minimum total length of silver fences in 3 seconds. However, the program was written in R, and you want to help him by writing another program that outputs the same answer, but using a less cursed programming language. Can you accomplish this task?

Input

The first line contains a positive integer $$$n$$$ ($$$4 \le n \le 4 \times 10^5$$$). Then $$$n$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i, y_i$$$ ($$$-10^8 \le x_i, y_i \le 10^8, (x, y) \ne (0, 0)$$$) describing the coordinates of the $$$i$$$-th apple tree.

Output

If it is impossible to satisfy the king's rules, output -1.

Otherwise, let the answer be $$$x$$$. It can be proven that $$$x^2$$$ is always a rational number. Let $$$x^2 = \frac{p}{q}$$$ where $$$p$$$ is a nonnegative integer, $$$q$$$ is a positive integer, and $$$\gcd(p, q) = 1$$$. Output the result of $$$p \cdot q^{-1}$$$ modulo $$$10^9 + 7$$$, where $$$q^{-1}$$$ denotes the multiplicative inverse of $$$q$$$. (It can also be proven that, for any input satisfying the constraints, $$$q$$$ is never a multiple of $$$10^9 + 7$$$. Try to prove this!)

Scoring
  • Subtask 1 (30 points): $$$n$$$ is even, and $$$(x_i, y_i) = (x_{i+1}, y_{i+1})$$$ for $$$i = 1, 3, 5, \dots, n - 1$$$
  • Subtask 2 (30 points): $$$y_i \ge 0$$$ for $$$i = 1, 2, \dots, n$$$
  • Subtask 3 (40 points): No additional constraints.
Examples
Input
6
2 1
-5 1
-4 3
0 3
-1 2
-3 5
Output
80
Input
6
-1 -1
-1 0
-1 1
1 -1
1 0
1 1
Output
-1
Input
4
1 1
2 2
3 3
2 2
Output
0
Note

In example 1, one of the optimal ways to build fences is:

Each dot denotes a tree, each solid line segment denotes a silver fence, and each dotted line segment denotes a wooden fence.