Coloring the Infinite Plane

Every lattice point on the coordinate plane is painted white. Jiho stands on a point and can move by $(x\_i, y\_i)$ or by $(-x\_i, -y\_i)$ from that point.

Starting from the origin $(0, 0)$, color black every point that Jiho can reach.

For example, suppose Jiho can move by $(2,0)$, $(2,2)$, and $(0,2)$. The figure below shows this case.

The red point is the origin, and the blue points are the points Jiho can reach from the origin in one move. Since Jiho can also move by $(-x\_i, -y\_i)$, the green points are also reachable from the origin in one move. Points reachable after several moves are colored black. Every point except the white ones can be reached from the origin.

The fraction of lattice points that are black is a rational number. In the example above, only points with both coordinates even are colored, so the fraction is $1/4$.

Write this rational number as an irreducible fraction $\frac{a}{b}$, and print $(a \cdot b^{-1}) \bmod 1\,000\,000\,007$. Here $1\,000\,000\,007$ is prime.

If the fraction is $0$, print $0$. If it is $1$, print $1$. The fraction is always rational, and no test case has a denominator $b$ that is a multiple of $1\,000\,000\,007$. In other words, the answer always exists.

The first line contains $N$. Each of the next $N$ lines contains $x\_i$ and $y\_i$ separated by a space, for $1 \le i \le N$.

Print the answer on the first line.

• $2 \le N \le 1\,000\,000$
• $-10^9 \le x\_i, y\_i \le 10^9$ ($1 \le i \le N$)

Moving from a point $(x,y)$ by $(x',y')$ takes you to the point $(x+x', y+y')$.

The black ratio $A$ is defined precisely as follows. For every $\epsilon>0$, there is a positive integer $N$ such that for every integer $n > N$, the fraction of colored points among all lattice points $(x,y)$ with $-n \le x,y \le n$ differs from $A$ by less than $\epsilon$. The problem guarantees that $A$ always exists and is rational.

For a prime $p$ and integers $a,b$ with $\gcd(b,p)=1$, $(a \cdot b^{-1}) \bmod p$ is the smallest nonnegative integer $x$ that satisfies $bx \equiv a \pmod{p}$.