Problem: 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.

Submission attempts (in order):
from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        if (0, 0) not in d:
            d[(0, 0)] = 1
        else:
            d[(0, 0)] += 1
    else:
        g = gcd(a, b)

        a, b =  a / g, b /g
        if b < 0:
            a, b = -a, -b
        if b == 0:
            a, b =  1, 0
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

print(d)

done_list = []

for k in list(d.keys()):
    if k not in done_list:
        pair_k = (sign(k[0]) * (-1) * k[1], abs(k[0]))
        if pair_k not in d:
            answer *= 2 ** d[k]
            answer = answer % mod
            done_list += [k]
        else:
            answer *= (2 ** d[k]) + (2 ** d[pair_k]) - 1
            answer = answer % mod
            done_list += [k, pair_k]

if (0, 0) in d:
    answer += d[(0, 0)]
    
print((answer - 1) % mod)

from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}

search_list = []

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        if (0, 0) not in d:
            d[(0, 0)] = 1
        else:
            d[(0, 0)] += 1
    else:
        g = gcd(a, b)

        a, b =  a / g, b /g
        if b < 0:
            a, b = -a, -b
        if b == 0:
            a, b =  1, 0
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1



for k in list(d.keys()):
    if k not in done_list and k != (0, 0):
        pair_k = (sign(k[0]) * (-1) * k[1], abs(k[0]))
        if pair_k not in d:
            answer *= (2 ** d[k]) % mod
            answer = answer % mod
            done_list += [k]
        else:
            answer *= ((2 ** d[k]) + (2 ** d[pair_k]) - 1) % mod
            answer = answer % mod
            done_list += [k, pair_k]

if (0, 0) in d:
    answer += d[(0, 0)]
    
print((answer - 1) % mod)

from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1


group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q), v in group:
    invp, invq = (sign(p) * (-1) * q, abs(p))
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)]) % mod
        answer = answer % mod
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1) % mod
        answer = answer % mod
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

if N == 1:
    print(1)
    
d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q) in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if (invp, invq) not in d:
        answer *= (2 ** (d[(p, q)]-1)) % mod
        answer = answer % mod
    else:
        answer *= ((2 ** (d[(p, q)]-1)) + (2 ** (d[(invp, invq)]-1)) - 1) % mod
        answer = answer % mod
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q) in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)])
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1)
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Wrong Answer

Accepted