Problem:
 Score: 500 points    Problem Statement  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 .        Sample Input 1 3
1 2
-1 1
2 -1      Sample Output 1 5  There are five ways to choose the set of sardines, as follows:   The 1 -st  The 1 -st and 2 -nd  The 2 -nd  The 2 -nd and 3 -rd  The 3 -rd        Sample Input 2 10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4      Sample Output 2 479

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def solve(N: int, A: "List[int]", B: "List[int]"):
    s = {}
    for i in range(N):
        if A[i] == 0 and B[i] == 0:
            a, b = 0, 0
        elif A[i] == 0:
            a, b = 0, 1
        elif B[i] == 0:
            a, b = 1, 0
        else:
            g = gcd(A[i], B[i])
            a, b = A[i] // g, B[i] // g
        k = (a, b)
        if not k in s:
            s[k] = 0
        s[k] += 1
    count = 0
    checked = set()
    cums = []
    
    for (a, b), cnt in s.items():
        if (a, b) in checked:
            continue
        checked.add((a, b))
        tmp = 0
        if a == 0 and b == 0:
            count += cnt
            
            
            
            continue
        if (-b, a) in s and (-b, a) not in checked:
            tmp += s[(-b, a)]
            checked.add((-b, a))
        if (b, -a) in s and (b, -a) not in checked:
            tmp += s[(b, -a)]
            checked.add((b, -a))
        if tmp > 0:
            cum = pow(2, cnt, MOD) + pow(2, tmp, MOD) - 1
            cum %= MOD
            cums.append(cum)
            count += cnt + tmp
    
    ret = pow(2, (N - count), MOD)
    for cum in cums:
        ret *= cum
        ret %= MOD
    if (0, 0) in s:
        ret += s[(0, 0)]
    ret -= 1
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import collections
import sys
import math
from fractions import Fraction

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 1000000007  


def solve(N: int, A: "List[int]", B: "List[int]"):
    ab = collections.defaultdict(lambda: [0, 0])  
    zeros = 0
    for i in range(N):
        if A[i] == B[i] == 0:
            zeros += 1
        elif A[i] == 0:
            ab[0][1] += 1
        elif B[i] == 0:
            ab[0][0] += 1
        elif A[i] * B[i] >= 0:
            v = math.gcd(A[i], B[i])
            ab[(abs(B[i]) // v, abs(A[i]) // v)][0] += 1
        else:
            v = math.gcd(A[i], B[i])
            ab[(abs(A[i]) // v, abs(B[i]) // v)][1] += 1

    
    ans = 1
    for x, y in ab.values():
        pattern = 1  
        pattern += 2 ** x - 1
        pattern += 2 ** y - 1
        ans = ans * pattern % MOD
    print((ans - 1) % MOD + zeros)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
from math import gcd
n=N()
mod=10**9+7
az=0
bz=0
zz=0
l=LL(n)
ans=1
import collections
d=collections.defaultdict(int)
for a,b in l:
    if a==0 and b==0:
        zz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
    elif a<0 and b<0:
        a=-a
        b=-b
        x=gcd(a,b)
        d[(a//x,b//x)]+=1
    elif a<0:
        a=-a
        x=gcd(a,b)
        d[(-a//x,b//x)]+=1
    elif b<0:
        b=-b
        x=gcd(a,b)
        d[(-a//x,b//x)]+=1
    else:
        x=gcd(a,b)
        d[(a//x,b//x)]+=1
pow2=[1]*(n+1)
t=1
for i in range(1,n+1):
    t*=2
    t%=mod
    pow2[i]=t
ans*=(1+(pow2[az]-1)+(pow2[bz]-1))
for a,b in list(d.keys()):
    if a>0 and b>0:
        x=d[(a,b)]
        y=d[(-b,a)]
        ans*=(1+(pow2[x]-1)+(pow2[y]-1))
        ans%=mod
    else:
        if not (b,-a) in d:
            ans*=pow2[d[(a,b)]]
            ans%=mod
print((ans+zz-1)%mod)

Solution (Python):
mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
ca = 0
cb = 0
cc = 0
for i in range(N):
    a,b = AB[i]
    if a==0 and b!=0:
        ca += 1
        continue
    elif a!=0 and b==0:
        cb += 1
        continue
    elif a==0 and b==0:
        cc += 1
        continue
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    if d != 0:
        a //= d
        b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = pow(2,ca)+pow(2,cb)-1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += cc
ans %= mod
print(ans)

Solution (Python):
import sys
from collections import defaultdict
readline = sys.stdin.readline

N = int(readline())
AB = [list(map(int, readline().split())) for i in range(N)]

C = [(a,b) for a,b in AB if (a==0 and b==0)]
AB = [(a,b) for a,b in AB if not (a==0 and b==0)]
P = 1000000007
def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def gcd(_a,_b):
    a,b = abs(_a), abs(_b)
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    while a % b != 0:
        a, b = b, a % b
    
    return b

def norm(a,b):
    g = gcd(a,b)
    a,b = a//g, b//g
    if a < 0:
        a,b = -a, -b
    if a == 0 and b < 0:
        b = -b
    return a,b

dic = defaultdict(int)
for a,b in AB:
    a,b = norm(a,b)
    dic[(a,b)] += 1

ans = len(C)
keys = list(dic.keys())

x = 1
for a,b in keys:
    n = dic[(a,b)]
    if n != 0:
        p,q = norm(b, -a)
        m = dic[(p,q)]
        x = x * (mod_pow(2, n) + mod_pow(2, m) - 1)
        x %= P
        dic[(p,q)] = 0
        dic[(a,b)] = 0
x -= 1
ans += x
ans %= P
print(ans)

Solution (Python):
import math
import sys
from collections import defaultdict



MOD = 1000000007

def get_pair(val):
    a, b = val
    paired_a = -b
    paired_b = a
    if paired_a < 0 or (paired_a == 0 and paired_b < 0):
        paired_a = -paired_a
        paired_b = -paired_b
    return (paired_a, paired_b)


def main():
    N = int(input())
    lines = sys.stdin.read().split('\n')
    vals = [0] * N
    zero_count = 0
    for ix, line in enumerate(lines):
        if not line:
            continue
        a, b = map(int, line.split(' '))
        if a == 0 and b == 0:
            zero_count += 1
            vals[ix] = (0, 0)
            continue
        gcd = math.gcd(a, b)
        if (a < 0 or (a == 0 and b < 0)):
            gcd = -gcd
        a //= gcd
        b //= gcd
        vals[ix] = (a,b)

    vals_set = defaultdict(int)
    for val in vals:
        if val == (0, 0):
            continue
        vals_set[val] += 1

    processed_set = set()
    result = 1
    for val, count in vals_set.items():
        if val in processed_set:
            continue
        
        processed_set.add(val)
        
        pair = get_pair(val)
        mult = pow(2, count, MOD)
        if pair in vals_set:
            
            processed_set.add(pair)
            mult += pow(2, vals_set[pair], MOD) - 1 
        
        result = (result * mult) % MOD

    result = (result - 1 + zero_count + MOD) % MOD
    
    print(result)




if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict
from math import gcd
MOD = 1000000007
inpl = lambda: list(map(int,input().split()))
groups = defaultdict(int)
null = 0
N = int(input())
for _ in range(N):
    A, B = inpl()
    if A == 0 and B == 0:
        null += 1
    elif A == 0:
        groups[(0,1)] += 1
    elif B == 0:
        groups[(1,0)] += 1
    else:
        g = gcd(A,B)
        A //= g
        B //= g
        if A < 0:
            A *= -1
            B *= -1
        groups[(A, B)] += 1
ans = 1
for k in list(groups.keys()):
    A, B = k
    if B <= 0:
        C, D = -B, A
    else:
        C, D = B, -A
    groups[(C,D)]
for k, v in groups.items():
    A, B = k
    if B <= 0:
        continue
    u = groups[(B,-A)]
    p = pow(2,v,MOD) + pow(2,u,MOD) - 1
    ans *= p
    ans %= MOD
ans -= 1
ans += null
print(ans % MOD)

Solution (Python):
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g
    rotate = 0
    while not (a >= 0 and b > 0):
        a,b = -b,a
        rotate += 1
    if (a,b) not in cnt:
        cnt[(a,b)] = [0,0]

    cnt[(a,b)][rotate % 2] += 1

ans = 1
    
for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1
print(ans % MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def gcd(a, b):
    while b: a, b = b, a % b
    return a

def main():
    md = 1000000007
    n = II()
    cnt = {}
    cnt[(0, 0)] = [0, 0]
    zero = 0
    for _ in range(n):
        a, b = MI()
        if a * b == 0:
            if a == b == 0:
                zero += 1
            elif a == 0:
                cnt[(0, 0)][0] += 1
            else:
                cnt[(0, 0)][1] += 1
            continue
        par = a * b > 0
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        a //= g
        b //= g
        if par:
            cnt.setdefault((a, b), [0, 0])
            cnt[(a, b)][1] += 1
        else:
            cnt.setdefault((b, a), [0, 0])
            cnt[(b, a)][0] += 1
    
    ans = 1
    for x, y in cnt.values():
        cur = pow(2, x, md) + pow(2, y, md) - 1
        ans = ans * cur % md
    ans += zero
    ans = (ans - 1) % md
    print(ans)

main()

Solution (Python):
from math import gcd
n = int(input())
ab = {}
ans = 0
mod = 10 ** 9 + 7


def go(a, b):
    if a == 0 and b == 0:
        return 0, 0
    elif a == 0:
        return 0, 1
    elif b == 0:
        return 1, 0
    c = gcd(a, b)
    a, b = a // c, b // c
    if a < 0:
        a *= - 1
        b *= - 1
    return a, b


def la(a, b):
    r = max((a, b), go(b, -a))
    if r == (a, b):
        return r, 0
    else:
        return r, 1


zero = 0
for i in range(n):
    a, b = [int(i) for i in input().split()]
    a, b = go(a, b)
    if a == b == 0:
        zero += 1
    else:
        l, ind = la(a, b)
        if l in ab:
            ab[l][ind] += 1
        else:
            ab[l] = [0, 0]
            ab[l][ind] += 1
ans = 1
for i in ab:
    ans *= pow(2, ab[i][0], mod) + pow(2, ab[i][1], mod)-1
    ans %= mod
print((ans + zero-1)%mod)

Solution (Python):
from math import gcd
import sys

input=sys.stdin.readline

N=int(input())
dicplus={}
dicminus={}
dicinf=0
diczero=0
dicnan=0
for i in range(N):
    a,b=map(int,input().split())
    g=gcd(a,b)
    if a==0 and b==0:
        dicnan+=1
    elif a==0:
        diczero+=1
    elif b==0:
        dicinf+=1
    else:
        A=a//g
        B=b//g
        if A*B>0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicplus:
                dicplus[(A,B)]=0
            dicplus[(A,B)]+=1
        elif A*B<0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicminus:
                dicminus[(A,B)]=0
            dicminus[(A,B)]+=1


ans=1
mod=10**9+7
for a,b in dicplus:
    if (b,a) in dicminus:
        ans*=(pow(2,dicplus[(a,b)],mod)-1+pow(2,dicminus[(b,a)],mod)-1+1)
        ans%=mod
    else:
        ans*=pow(2,dicplus[(a,b)],mod)
        ans%=mod

for a,b in dicminus:
    if (b,a) not in dicplus:
        ans*=pow(2,dicminus[(a,b)],mod)
        ans%=mod

ans*=(pow(2,dicinf,mod)-1+pow(2,diczero,mod)-1+1)
ans%=mod
ans=ans-1+dicnan
ans%=mod

print(ans)

Solution (Python):
from collections import Counter, defaultdict, deque
from math import gcd

MOD = 1000000007
(N,) = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for i in range(N)]

count00 = 0
badTerms = defaultdict(lambda: list([0, 0]))
for i, (a, b) in enumerate(AB):
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            count00 += 1
        elif a == 0:
            badTerms[0][0] += 1
        else:
            assert b == 0
            badTerms[0][1] += 1

    else:

        assert a * b != 0
        isNeg = a * b < 0

        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0 and b < 0:
            a *= -1
            b *= -1
        if a < 0 or b < 0:
            a, b = -b, a
        if a < 0 and b < 0:
            a *= -1
            b *= -1
        assert a > 0 and b > 0

        if isNeg:
            badTerms[(a, b)][0] += 1
        else:
            badTerms[(a, b)][1] += 1

ways = 1

for key, (negCount, posCount) in badTerms.items():
    ways *= pow(2, negCount, MOD) + pow(2, posCount, MOD) - 1
    ways %= MOD

if count00:
    
    ways += count00


print((ways - 1) % MOD)

Solution (Python):
N = int(input())
D = {}

def gcd(x,y):
    if x>y: x,y=y,x
    while x:
        x,y=y%x,x
    return y

for _ in range(N):
    A, B = map(int, input().split())
    if   A==0 and B==0: key=(0,0)
    elif A==0: key=(0,1)
    elif B==0: key=(1,0)
    else:
        if A<0:
            A=-A
            B=-B
        g = gcd(A,abs(B))
        key = (A//g, B//g)

    if key not in D: D[key]=0
    D[key]+=1

mod = 10**9+7

ans = 1
n00 = 0
for k1, v1 in D.items():
    if k1==(0,0):
        n00+=v1
        continue
    if v1==0: continue
        
    k2 = (k1[1], -k1[0]) if k1[1]>0 else (-k1[1], k1[0])
    if k2 not in D:
        ans = ans * pow(2, v1, mod) % mod
    else:
        v2 = D[k2]
        m = (pow(2, v1, mod) + pow(2, v2, mod) - 1) % mod
        ans = ans * m % mod
        D[k2]=0
        
print((ans+n00-1)%mod)

Solution (Python):

from math import gcd
import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
indet = 0
d = {}
for i in range(n):
    a, b = [int(x) for x in input().split()]
    if b < 0:
        a *= -1
        b *= -1
    if a == 0 and b == 0:
        indet += 1
        continue
    elif a == 0:
        p = (0, 1)
    elif b == 0:
        p = (-1, 0)
    else:
        g = gcd(a, b)
        p = (a // g, b // g)
    d[p] = d.get(p, 0) + 1

sizes = []
ignore = set()
for p, size in d.items():
    if p not in ignore:
        a, b = -p[1], p[0]
        if b < 0:
            a *= -1
            b *= -1
        if (a, b) in d:
            ignore.add((a, b))
            sizes.append((size, d[(a, b)]))
        else:
            sizes.append((size, 0))
M = 10**9 + 7
ans = 1
for n1, n2 in sizes:
    ans *= (pow(2, n1, M) + pow(2, n2, M) - 1)
    ans %= M
print((indet + ans - 1) % M)

Solution (Python):
from math import gcd
n = int(input())
plus = {}
minus = {}
mod = 10**9 + 7
gen = pow(10,19)
zero = 0 
for i in range(n):
    a,b = map(int,input().split())
    if a == b == 0:
        zero += 1
        continue
    if a < 0:a,b = -a,-b
    elif a == 0 and b < 0:b = -b
    g = gcd(a,b)
    a //= g
    b //= g
    key = a*gen + b
    if b > 0:
        if key not in plus.keys():plus[key] = 0
        plus[key] += 1
    else:
        if key not in minus.keys():minus[key] = 0
        minus[key] += 1
ans = pow(2,n-zero,mod)
for k,v in plus.items():
    a = k//gen
    b = k%gen
    opo = b*gen - a
    if opo in minus.keys():
        o = minus[opo]
        ans = ans*pow(2,v*(mod-2)%(mod-1),mod) + ans*pow(2,o*(mod-2)%(mod-1),mod) - ans*pow(2,(v+o)*(mod-2)%(mod-1),mod)
        ans %= mod
print((ans + zero - 1)%mod)

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    zz = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            zz += 1
            continue
        if a < 0:
            a = -a
            b = -b
        elif a == 0:
            if b < 0:
                b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print((ans + zz)%mod)


if __name__ == '__main__':
    main()

Solution (Python):
import math
N = int(input())

dic = {}
zz = 0
az = 0
bz = 0

for i in range(N):

    A,B = map(int,input().split())

    if A == B == 0:
        zz += 1
    elif A == 0:
        az += 1
    elif B == 0:
        bz += 1
    else:

        g = math.gcd(A,B)
        A //= g
        B //= g

        if A*B > 0:
            now = (A,B)
            ind = 0
        else:
            now = (-1*B,A)
            ind = 1

        if now[0] < 0:
            now = (-1 * now[0] , -1 * now[1])
            

        if now not in dic:
            dic[now] = [0,0]
        dic[now][ind] += 1

mod = 10**9+7
ans = pow(2,az,mod) + pow(2,bz,mod) - 1

for i in dic:

    aa,bb = dic[i]
    now = pow(2,aa,mod) + pow(2,bb,mod) - 1
    ans *= now
    ans %= mod

print ((ans - 1 + zz) % mod)

Solution (Python):


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


n,*ab = [int(i) for i in read().split()]

M = iter(ab)
d = {}

zero = 0
from math import gcd
for a,b in zip(M,M):
    if a==b==0:
        zero += 1
        continue
    g = gcd(a,b)
    a//=g
    b//=g
    if b < 0:
        a = -a
        b = -b
    if b==0 and a == -1:
        a = 1
    
    if a > 0:
        if (a,b) in d:
            d[(a,b)][0] += 1
        else:
            d[(a,b)] = [1,0]
    else:
        if (b,-a) in d:
            d[(b,-a)][1] += 1
        else:
            d[(b,-a)] = [0,1]
        


MOD = 1000000007
ans = 1

pow2 = [1]
for _ in range(200005):
    pow2.append(pow2[-1]*2%MOD)


for (a,b),(k,l) in d.items():
    ans *= pow2[k]+pow2[l]-1
    ans %= MOD


ans += zero-1
print(ans%MOD)

Solution (Python):
import sys
input = sys.stdin.readline

def gcd(x, y):
    x = abs(x)
    y = abs(y)

    if x < y:
        x, y = y, x

    while y:
        x, y = y, x%y
        
    return x

N = int(input())
seen = dict()
zeroes = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeroes += 1
        continue
    
    if a < 0 or a == 0 and b < 0:
        a, b = -a,-b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0
    g = gcd(a,b)
    a//=g
    b//=g
    if (a,b) not in seen:
        seen[(a,b)] = [0,0]
    
    seen[(a,b)][flip] += 1

MOD = 10 ** 9 + 7
    
out = 1
for v in seen:
    a, b = seen[v]
    out *= (pow(2,a,MOD) + pow(2,b,MOD) - 1)
    out %= MOD
out -= 1

out += zeroes
out %= MOD
print(out)

Solution (Python):
import sys
from functools import cmp_to_key

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

mod = 1000000007
n = ni()
co = []
z = 0
for i in range(n):
    x = na()
    if x[0] == 0 and x[1] == 0:
        z += 1
    else:
        co.append(x)
n = len(co)

for c in co:
    if c[1] < 0 or c[1] == 0 and c[0] < 0:
        c[1] = -c[1]
        c[0] = -c[0]

mod = 1000000007
ans = 1

co.sort(key=cmp_to_key(lambda x,y: -(x[0]*y[1]-y[0]*x[1])))

p = 0
while p < n and co[p][0] > 0:
    p += 1

col = []
i = 0
rem = n
while i < n:
    if co[i][0] <= 0:
        break
    while p < n and co[i][0]*co[p][0]+co[i][1]*co[p][1] > 0:
        p += 1

    op = p
    while p < n and co[i][0]*co[p][0]+co[i][1]*co[p][1] == 0:
        p += 1

    oi = i
    while i < n and co[i][0]*co[oi][1]-co[i][1]*co[oi][0] == 0:
        i += 1

    if p-op > 0:
        ans = ans * (pow(2, i-oi, mod) + pow(2, p-op, mod) - 1) % mod
        rem -= (p-op) + (i-oi)

ans = ans * pow(2, rem, mod) % mod
print((ans+z+mod-1)%mod)