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 math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni //= 2
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a < 0 and (b < 0 or abs(a) > abs(b)):
        a = -a
        b = -b
    g = math.gcd(abs(a),abs(b))
    if a == 0 and b == 0:
        continue
    elif a == -b:
        if "1 -1" in d:
            d["1 -1"] += 1
        else:
            d["1 -1"] = 1
    elif a == b:
        if "1 1" in d:
            d["1 1"] += 1
        else:
            d["1 1"] = 1
    else:
        p1 = str(a//g)+" "+str(b//g)
        p2 = str(b//g)+" "+str(a//g)
        if p1 in d:
            d[p1] += 1
            d[p2] += 1
        else:
            d[p1] = 1
            d[p2] = 1
print(d)

for i in d.keys():
    i0, i1 = map(int,i.split())
    if abs(i0) < abs(i1):
        continue
    elif str(i0)+" "+str(-i1) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i0)+" "+str(-i1)],mod)+twoxxn(d[i],mod)-1)%mod
        print(i,aaa)
        ans = (ans*aaa)%mod
        d[str(i0)+" "+str(-i1)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod
ans = (ans-1)%mod

print(max(1,ans))


import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni //= 2
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a < 0 :
        a = -a
        b = -b
        g = math.gcd(abs(a),abs(b))
    if a == 0 and b == 0:
        continue
    else:
        if a == 0:
            b = 1
            g = 1
        elif b == 0:
            a = 1
            g = 1
        p1 = str(a//g)+" "+str(b//g)
        if p1 in d:
            d[p1] += 1
        else:
            d[p1] = 1

for i in d.keys():
    i0, i1 = map(int,i.split())
    if str(i1)+" "+str(-i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i1)+" "+str(-i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(i1)+" "+str(-i0)] = 0
    elif str(-i1)+" "+str(i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(-i1)+" "+str(i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(-i1)+" "+str(i0)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod

if ans == 1:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)


import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        print(aaa)
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(iw0)
    exit()

ans = (i0+ans-1)%mod
print(ans)


import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
i0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        i0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        print(aaa)
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(i0)
    exit()

ans = (ans-1)%mod
print(ans)


import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1
done = []
for (i0,i1), din in d.items():
    if d.get((-i1,i0),1) == 0 or d.get((i1,-i0),1) == 0:
        continue
    w = d.get((i1,-i0),0) + d.get((-i1,i0),0)
    aaa = (twoxxn(w,mod)+twoxxn(din,mod)-1)%mod
    ans = (ans*aaa)%mod
    d[(i0,i1)] = 0

if len(d.keys()) == 0:
    print(iw0)
    exit()

ans = (iw0+ans+mod-1)%mod
print(ans)


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Accepted