We have caught N sardines. The deliciousness and fragrantness of the i-th sardine is A_i and B_i, respectively.

We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.

The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.

In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.

Constraints

* All values in input are integers.
* 1 \leq N \leq 2 \times 10^5
* -10^{18} \leq A_i, B_i \leq 10^{18}

Input

Input is given from Standard Input in the following format:


N
A_1 B_1
:
A_N B_N


Output

Print the count modulo 1000000007.

Examples

Input

3
1 2
-1 1
2 -1


Output

5


Input

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4


Output

479
import sys
from math import gcd
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

N, *AB = map(int, read().split())
mod = 10 ** 9 + 7

ab = []
zero = 0
for A, B in zip(*[iter(AB)] * 2):
    if A == 0 and B == 0:
        zero += 1
        continue
    if A == 0:
        B = -1
    elif B == 0:
        A = 1
    else:
        g = gcd(A, B)
        A //= g
        B //= g
    if A < 0:
        A, B = -A, -B
    ab.append((A, B))

cnt = Counter(ab)
answer = 1
checked = set()
ok = 0

for (i, j), n in cnt.items():
    if (i, j) in checked:
        continue
    if j < 0:
        c, d = -j, i
    else:
        c, d = j, -i
    if (c, d) in cnt:
        m = cnt[(c, d)]
        answer = (answer * (pow(2, n, mod) + pow(2, m, mod) - 1)) % mod
        checked.add((c, d))
    else:
        ok += n

answer *= pow(2, ok, mod)
answer -= 1
answer += zero
answer %= mod
print(answer)
