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:
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?
The first line contains a positive integer $n$ ($4 <= n <= 4 times 10^5$). Then $n$ lines follow. The $i$-th line contains two integers $x_i, y_i$ ($-10^8 <= x_i, y_i <= 10^8, (x, y) != (0, 0)$) describing the coordinates of the $i$-th apple tree.
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 dot.op 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!)
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.
## Input
The first line contains a positive integer $n$ ($4 <= n <= 4 times 10^5$). Then $n$ lines follow. The $i$-th line contains two integers $x_i, y_i$ ($-10^8 <= x_i, y_i <= 10^8, (x, y) != (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 dot.op 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!)
[samples]
## 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 >= 0$ for $i = 1, 2, \\dots, n$ Subtask 3 (40 points): No additional constraints.
## 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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ denote the number of people.
- Let $ A_k = (a_{k,1}, a_{k,2}, \dots, a_{k,n_k}) $ be the sequence of distinct integers observed, where $ a_{k,i} \in [1, n_k] $.
**Constraints**
1. $ 1 \le T \le 10 $
2. For each $ k \in \{1, \dots, T\} $:
- $ 1 \le n_k \le 100 $
- $ A_k $ is a permutation of a contiguous subsequence of $ \{1, 2, \dots, n_k\} $, but not necessarily complete.
- All elements in $ A_k $ are distinct and lie in $ [1, n_k] $.
**Objective**
Determine whether $ A_k $ is a contiguous arc (in cyclic order) of the full cycle $ (1, 2, \dots, n_k) $, either in clockwise or counterclockwise direction.
That is, check if there exists a starting point $ s \in [1, n_k] $ and a direction $ d \in \{+1, -1\} $ such that $ A_k $ equals:
$$
(s, s + d, s + 2d, \dots) \mod n_k \quad \text{(with residues in } [1, n_k]\text{)}
$$
for $ n_k $ consecutive terms.