무한평면 색칠하기

모든 격자점이 흰색으로 칠해진 좌표평면이 있다. 지호는 서 있는 점에서 $(x\_i, y\_i)$만큼 혹은 $(-x\_i, -y\_i)$만큼 움직일 수 있다.

원점 $(0, 0)$에서 출발하여 지호가 도달할 수 있는 점을 모두 검은색으로 칠하자.

예를 들어, 지호가 $(2,0)$, $(2,2)$, $(0,2)$만큼 이동할 수 있는 경우는 다음과 같다.

빨간 점은 원점이고, 파란 점은 원점에서 바로 이동할 수 있는 점이다. $(-x\_i, -y\_i)$만큼 이동하는 것도 가능하므로 녹색 점 또한 원점에서 바로 이동할 수 있다. 여러 번 이동해서 도달할 수 있는 점은 검은색으로 칠해진다. 흰색으로 칠해진 점을 제외하면, 모든 점은 원점에서 도달할 수 있다.

모든 격자점 중 칠해진 점의 비율은 유리수로 나타낼 수 있다. 위 예시에서는 좌표가 모두 짝수인 점만 칠해지므로 칠해진 점의 비율은 $1/4$이다.

이 유리수를 기약분수 $\frac{a}{b}$로 나타낼 때, $(a \cdot b^{-1}) \bmod 1\,000\,000\,007$을 출력하여라. 여기서 $1\,000\,000\,007$은 소수이다.

비율이 $0$이면 $0$을, $1$이면 $1$을 출력하면 된다. 비율은 항상 유리수로 나타낼 수 있으며, 기약분수 $\frac{a}{b}$에서 $b$가 $1\,000\,000\,007$의 배수인 테스트케이스는 주어지지 않는다. 즉, 답은 항상 존재한다.

첫 번째 줄에 $N$이 주어진다. 두 번째 줄부터 $N$개의 줄이 주어지며, $i$번째 줄에는 공백으로 구분된 $x\_i$와 $y\_i$가 주어진다.

첫 번째 줄에 답을 출력하여라.

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

점 $(x,y)$에서 $(x',y')$만큼 움직이면 점 $(x+x', y+y')$으로 이동한다.

검은색 점의 비율 $A$는 다음과 같이 엄밀하게 정의한다. 모든 $\epsilon>0$에 대해, 어떤 양의 정수 $N$이 존재하여 $n > N$인 모든 정수 $n$에 대해, $-n \le x,y \le n$ 범위의 모든 격자점 $(x,y)$ 중 칠해진 점의 비율과 $A$의 차이가 $\epsilon$ 미만이다. 본 문제에서는 $A$가 항상 존재하고 유리수임을 보장한다.

소수 $p$와 정수 $a,b$에 대해 $\gcd(b,p)=1$이면, $(a \cdot b^{-1}) \bmod p$는 $bx \equiv a \pmod{p}$를 만족하는 가장 작은 음이 아닌 정수 $x$이다.