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 collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
L = defaultdict(lambda: [0,0])
zero = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A==0: d=B
    elif B==0: d=A
    else: d=gcd(A,B)
    if d != 0:
        A, B = A//d, B//d
        if A<0: A, B = -A, -B
        if B>0: L[(A,B)][0] += 1
        else: L[(-B,A)][1] += 1
    else: zero += 1
print(L)
res = 1

for x,y in L.values():
    res *= pow(2,x,MOD) + pow(2,y,MOD) -1
    res %= MOD
print((res+zero-1)%MOD)



N = int(input())
mod = 10 **9 + 7

def equal(item0, item1, delta = 10 ** (-24)):
    if abs(item0 - item1) < delta:
        return True
    else:
        return False
def bigger(item0, item1, delta = 10** (-24)):
    if item0 -item1 > delta:
        return True
    else:
        return False

ab = []
ba = []
zero = 0
from bisect import insort
for _ in range(N):
    A, B = map(int, input().split())
    if A*B == 0:
        if A == 0 and B == 0:
            zero += 1
        elif A == 0 and B != 0:
            ab = [0] + ab
        else:
            ba = [0] + ba
    elif A*B > 0:
        insort(ab, A/B)
    else:
        insort(ba, -B/A)
def make_count(list):
    k = 0
    lis = []
    while k < len(list):
        cnt = 1
        while k+1 < len(list):
            if equal(list[k],list[k+1]):
                cnt += 1
                k += 1
                continue
            else:
                break
        lis.append([list[k], cnt])
        k += 1
    return lis

ab = make_count(ab)
ba = make_count(ba)
from collections import deque
ab = deque(ab)
ba = deque(ba)
ans = 1 #all pattern
flag = True
pair = []
if len(ab) == 0:
    print(pow(2, N-zero, mod)+zero-1)
    exit()
if len(ba) == 0:
    print(pow(2, N-zero, mod)+ zero -1)
    exit()


while True:
    if flag:
        a = ab.popleft()
        b = ba.popleft()
    flag = False
    if equal(a[0], b[0]):
        pair.append([a[1], b[1]])
        if ab:
            a = ab.popleft()
        else:
            a = [-1, 0]
        if ba:
            b = ba.popleft()
        else:
            b = [-1, 0]
        if a[0] == b[0] == -1:
            break
    elif bigger(a[0], b[0]):
        if ba:
            pair.append([0,b[1]])
            b = ba.popleft()
            continue
        elif ab:
            pair.append([a[1],0])
            a = ab.popleft()
            b = [-1, 0]
            continue
        else:
            if a[0] != -1:
                pair.append([a[1], 0])
            if b[0]!= -1:
                pair.append([0, b[1]])
            break
    else:
        if ab:
            pair.append([a[1], 0])
            a = ab.popleft()
            continue
        elif ba:
            pair.append([0, b[1]])
            b = ba.popleft()
            a = [-1, 0]
        else:
            if a[0] != -1:
                pair.append([a[1], 0])
            if b[0]!= -1:
                pair.append([0, b[1]])
            break
ans = 1
print(pair)
for item in pair:
    ans *= pow(2, item[0], mod) + pow(2, item[1], mod) -1
    ans %= mod
ans += zero-1
ans %= mod
print(ans)




from collections import defaultdict
from math import gcd
N = int(input())
MOD = 10**9 + 7
L = defaultdict(lambda: [0,0])
zero = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A==0: d=B
    elif B==0: d=A
    else: d=gcd(A,B)
    if d != 0:
        A, B = A//d, B//d
        if A<0: A, B = -A, -B
        if B>0: L[(A,B)][0] += 1
        else: L[(-B,A)][1] += 1
    else: zero += 1

res = 1

for x,y in L.values():
    res *= pow(2,x,MOD) + pow(2,y,MOD) -1
    res %= MOD
print((res+zero-1)%MOD)



Verdicts: Wrong Answer

Wrong Answer

Accepted