무한평면 색칠하기

모든 격자점이 흰색으로 칠해진 좌표평면이 있다. 지호는 서 있는 점에서 $(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 \leq N \leq 1\,000\,000$
• $-10^9 \leq x_i, y_i \leq 10^9$ ($1 \leq i \leq N$)

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

격자점 중 검게 칠해진 점의 비율 $A$는 엄밀히 다음과 같이 정의할 수 있다:

• 모든 $\epsilon>0$에 대해 어떤 양의 정수 $N$이 존재해서, $n > N$인 모든 정수 $n$에 대해 $-n \leq x,y \leq 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$로 정의된다.