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):
import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import Counter
from fractions import Fraction

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

S=[tuple(map(int,input().split())) for i in range(N)]

def main():
    C=Counter()
    PLUS=0
    for a,b in S:
        if a==0 and b==0:
            PLUS+=1
        elif b!=0:
            C[Fraction(a,b)]+=1
        else:
            C[float("inf")]+=1
        
    ANS=1

    for x in list(C.keys()):
        if x!=float("inf") and x!=Fraction(0,1):
            n=x.numerator
            d=x.denominator

            ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

            C[x]=0
            C[Fraction(-d,n)]=0
            
        else:
            ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

            C[float("inf")]=0
            C[Fraction(0,1)]=0

    print((ANS-1+PLUS)%mod)

main()
    


import sys
input = sys.stdin.readline

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

S=[tuple(map(int,input().split())) for i in range(N)]

from collections import Counter
from fractions import Fraction
C=Counter()

for a,b in S:
    if a==0 and b==0:
        continue
    if b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=1
print(C)
for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

        C[x]=0
        C[Fraction(-d,n)]=0
        
    else:
        ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

        C[float("inf")]=0
        C[Fraction(0,1)]=0

print((ANS-1)%mod)

import sys
input = sys.stdin.readline
from collections import Counter
from fractions import Fraction
from math import gcd

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

S=[tuple(map(int,input().split())) for i in range(N)]

def main():
    C=Counter()
    PLUS=0
    for a,b in S:
        if a==0 and b==0:
            PLUS+=1
        elif a==0:
            C[(0,1)]+=1
        elif b!=0 and a>0:
            C[(a//gcd(a,b),b//gcd(a,b))]+=1
        elif b!=0 and a<0:
            C[(-a//gcd(a,b),-b//gcd(a,b))]+=1
            
        else:
            C[float("inf")]+=1
        
    ANS=1

    #print(C)

    for x in list(C.keys()):
        if x!=float("inf") and x!=(0,1):

            a,b=x

            if b>0:
                ANS=ANS*(pow(2,C[x],mod)+pow(2,C[(b,-a)],mod)-1)%mod
                C[(b,-a)]=0
            else:
                ANS=ANS*(pow(2,C[x],mod)+pow(2,C[(-b,a)],mod)-1)%mod
                C[(-b,a)]=0
                
            C[x]=0

            
        else:
            ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[(0,1)],mod)-1)%mod

            C[float("inf")]=0
            C[(0,1)]=0

    print((ANS-1+PLUS)%mod)

main()
    


Verdicts: Time Limit Exceeded

Wrong Answer

Accepted