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



Sample input:
3
1 2
-1 1
2 -1


Sample output:
5

Submission status: Runtime Error

Solution code:
from math import gcd
mod=1000000007

n=int(input())
zeros = 0
vec = {}
for _ in range(n):
  a,b=map(int,input().split())
  if a==0 and b==0:
    zeros+=1
    continue
  elif a==0:
    vec[(0,1)]=vec.get((0,1),0)+1
  elif b==0:
    vec[(1,0)]=vec.get((1,0),0)+1
  else:
    g = gcd(a,b)
    a,b= a//g,b//g
    vec[(a,b)]=vec.get((a,b),0)+1
done = set()
total=1
for (a,b),v in vec.items():
  if (-b,a) in done or (b,-a) in done: continue
  done.add((a,b))
  w=vec[(-b,a)]+vec[(b,-a)]
  total *= (pow(2,v,mod)+pow(2,w,mod)-1)
  total %= mod
print((total+zeros-1+mod)%mod)

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
n=int(input())
import collections
c=collections.Counter()
from math import gcd
mod=10**9+7
for _ in range(n):
    a,b=map(int,input().split())
    g=abs(gcd(a,b))
    a//=g
    b//=g
    c[(a,b)]+=1
ans=1
s=set()
for i,j in c:
    if (i,j) not in s:
        s.add((i,j))
        s.add((-i,-j))
        s.add((-j,i))
        s.add((j,-i))
        ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
import collections
c=collections.Counter()
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
mod=10**9+7
for _ in range(n):
    a,b=map(int,input().split())
    g=abs(gcd(a,b))
    a//=g
    b//=g
    c[(a,b)]+=1
ans=1
s=set()
for i,j in c:
    if (i,j) not in s:
        s.add((i,j))
        s.add((-i,-j))
        s.add((-j,i))
        s.add((j,-i))
        ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
print(ans-1)

Submission status: Runtime Error

Solution code:
import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

    return (A//c,B//c)
 
 
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod
 
 
 
def resolve():
    N = int(input())
 
    
    km = dict()
    kp = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())
 
        if A == 0 and B == 0:
            zerozero+=1
            raise
            continue
 

 
        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)
 
 
 
        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    ans = 1

    groups = []
    for (x,y),v in km.items():
        if (-y,x) in kp:
            groups.append((v,kp[(-y,x)]))
            del kp[(-y,x)]
        else:
            groups.append((v,0))

    for v in kp.values():
        groups.append((v,0))


    for i,j in groups:
        ans *= (pow_r(2,i)+pow_r(2,j)-1)%1000000007
        ans %= 1000000007



    print((ans+zerozero-1)%(10**9+7))       

resolve()

Submission status: Runtime Error

Solution code:

import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

    return (A//c,B//c)
 
 
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod
 
 
 
def resolve():
    N = int(input())
 
    
    km = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())
 
        if A == 0 and B == 0:
            zerozero+=1
            raise
            continue
 

 
        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)
 
 
 

        if not xx in km:
            km[xx]=0
        km[xx]+=1
    ans = 1

    for x,y in sorted(km.keys(),key = lambda x: x[1]):

        if km[(x,y)]==0:

            continue
        tmp = pow_r(2,km[(x,y)])
        km[(x,y)] = 0
        rev = (-y,x)
        if rev in km and km[rev]!=0:

            tmp+=pow_r(2,km[rev])-1
            tmp %= 1000000007
            km[rev]=0

        ans *= tmp
        ans %= 1000000007




    print((ans+zerozero-1)%(10**9+7))       

resolve()

Submission status: Runtime Error

Solution code:
from collections import Counter

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

MOD = 1000000007

def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)
    z = 0
    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      a = a//g
      b = b//g
      if a*b<0: a = -abs(a)
      elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if a==b==0:z+=1
        elif b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],  d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0],d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0],d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print(ans-1+z)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

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

MOD = 1000000007

def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)

    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      a = a//g
      b = b//g
      if a*b<0: a = -abs(a)
      elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0],d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0],d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter

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

MOD = 1000000007

def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)

    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      a = a//g
      b = b//g
      if a*b<0:
        a = -abs(a)
        b = abs(b)
      elif a*b > 0:
        a = abs(a)
        b = abs(b)
      
      if a*b == 0:
        if b==0: d[(1,0)] = (d[(1,0)]+1,d[(1,0)])
        elif a==0: d[(1,0)] = (d[(1,0)],d[(1,0)]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0],d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0],d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input()) 
Group = {}
zero = 0
import math
for _ in range(N): 
    a,b = list(map(int,input().split())) 
    if a*a + b*b == 0:
        zero += 1
        continue
    g = math.gcd(a,b)
    a //= g
    b //= g
    if b < 0: 
        a = -1*a 
        b = -1*b 
    elif (b == 0)*(a < 0):
        a = -1*a 
        
    if (a <= 0)*(b > 0): 
        ratio = -a/b
        if ratio in Group:
            Group[ratio][0] += 1
        else:
            Group[ratio] = [1,0]
    else: 
        ratio = b/a
        if ratio in Group:
            Group[ratio][1] += 1
        else:
            Group[ratio] = [0,1]
            
ans = 1
for i in Group:
    n,p = Group[i]
    now = 1
    now += math.pow(2,n) - 1
    now += math.pow(2,p) - 1
    ans *= now
    if ans > 1000000007:
        ans = ans % 1000000007
ans += zero -1
print(int(ans))

Submission status: Runtime Error

Solution code:
N = int(input()) 
Group = {}
zero = 0
import math
for _ in range(N): 
    a,b = list(map(int,input().split())) 
    if a*a + b*b == 0:
        zero += 1
        continue
    g = math.gcd(a,b)
    a //= g
    b //= g
    if b < 0: 
        a = -1*a 
        b = -1*b 
    elif (b == 0)*(a < 0):
        a = -1*a 
        
    if (a <= 0)*(b > 0): 
        ratio = -a/b
        if ratio in Group:
            Group[ratio][0] += 1
        else:
            Group[ratio] = [1,0]
    else: 
        ratio = b/a
        if ratio in Group:
            Group[ratio][1] += 1
        else:
            Group[ratio] = [0,1]
            
ans = 1
for i in Group:
    n,p = Group[i]
    now = 1
    now += math.pow(2,n) - 1
    now += math.pow(2,p) - 1
    ans *= now
ans += zero -1
print(int(ans))

Submission status: Runtime Error

Solution code:
N = int(input()) 
Group = {}
zero = 0
import math
for _ in range(N): 
    a,b = list(map(int,input().split())) 
    if a*a + b*b == 0:
        zero += 1
        continue
    if b < 0: 
        a = -1*a 
        b = -1*b 
    elif (b == 0)*(a < 0):
        a = -1*a 
        
    if (a <= 0)*(b > 0): 
        ratio = -a/b
        if ratio in Group:
            Group[ratio][0] += 1
        else:
            Group[ratio] = [1,0]
    else: 
        ratio = b/a
        if ratio in Group:
            Group[ratio][1] += 1
        else:
            Group[ratio] = [0,1]
            
ans = 1
for i in Group:
    n,p = Group[i]
    now = 1
    now += math.pow(2,n) - 1
    now += math.pow(2,p) - 1
    ans *= now
ans += zero -1
print(int(ans))

Submission status: Runtime Error

Solution code:
N = int(input()) 
Pos = [] 
Neg = [] 
Group = {}
import math 
zero = 0
for _ in range(N): 
    a,b = list(map(int,input().split())) 
    if a*a + b*b == 0:
        zero += 1
        continue
    if b < 0: 
        a = -1*a 
        b = -1*b 
    elif (b == 0)*(a < 0):
        a = -1*a 
    if (a <= 0)*(b > 0): 
        Neg.append([a,b]) 
        ratio = -a/b
        if ratio in Group:
            Group[ratio][0] += 1
        else:
            Group[ratio] = [1,0]
    else: 
        Pos.append([a,b]) 
        ratio = b/a
        if ratio in Group:
            Group[ratio][1] += 1
        else:
            Group[ratio] = [0,1]
ans = 1
for i in Group:
    n,p = Group[i]
    now = 1
    now += math.pow(2,n) - 1
    now += math.pow(2,p) - 1
    ans *= now
ans += zero -1
print(int(ans))

Submission status: Runtime Error

Solution code:
import math
n = int(input())
mod_num = 1000000007

vList = []
cList = []
num_zero = 0
num_b_zero = 0
num_free = 0


def combo(x: int) -> int:
    '''
    :param x:
    :param y:
    :return: int
    '''
    return 2**x % mod_num


for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        num_zero += 1
    else:
        g = math.gcd(a, b)
        a, b = a/g, b/g
        if b == 0:
            num_b_zero += 1
        else:
            K_value = a/b
            # already exist
            if vList.count(K_value):
                index = vList.index(K_value)
                cList[index] += 1
            # new value
            else:
                vList.append(K_value)
                cList.append(1)
# print(vList)
# print(cList)
counter = 0
para = 0
oList = []
# (0,0)
counter += num_zero % mod_num
# (a,0) and (0,b)
if vList.count(0):
    vList.index(0)
    # print('(0,b) has ', cList[index])
    para += combo(cList[index])
if num_b_zero:
    para += combo(num_b_zero)
else:
    para = 1
# print('half 0 has ', para)
oList.append(para)
# normal
solved = []
for value, count in zip(vList, cList):
    if value not in solved:
        upside = -1/value
        # anti exist
        if vList.count(upside):
            solved.append(upside)
            index = vList.index(upside)
            # print(value, 'has anti ', upside, 'number', count, '-', cList[index])
            para = combo(count) + combo(cList[index])-1
            oList.append(para)
        # free value
        else:
            num_free += count
            # print(value, 'is free,now has free fish :', num_free)

oList.append(combo(num_free))
# print('count:')

result = 1
for i in oList:
    result *= i
result += counter
result -= 1
print(result % mod_num)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
mod_num = 1000000007

vList = []
cList = []
num_zero = 0
num_b_zero = 0
num_free = 0


def combo(x: int) -> int:
    '''
    :param x:
    :param y:
    :return: int
    '''
    return 2**x % mod_num


for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        num_zero += 1
    g = math.gcd(a, b)
    a, b = a/g, b/g
    if b == 0:
        num_b_zero += 1
    else:
        K_value = a/b
        # already exist
        if vList.count(K_value):
            index = vList.index(K_value)
            cList[index] += 1
        # new value
        else:
            vList.append(K_value)
            cList.append(1)
# print(vList)
# print(cList)
counter = 0
para = 0
oList = []
# (0,0)
counter += num_zero % mod_num
# (a,0) and (0,b)
if vList.count(0):
    vList.index(0)
    # print('(0,b) has ', cList[index])
    para += combo(cList[index])
if num_b_zero:
    para += combo(num_b_zero)
else:
    para = 1
# print('half 0 has ', para)
oList.append(para)
# normal
solved = []
for value, count in zip(vList, cList):
    if value not in solved:
        upside = -1/value
        # anti exist
        if vList.count(upside):
            solved.append(upside)
            index = vList.index(upside)
            # print(value, 'has anti ', upside, 'number', count, '-', cList[index])
            para = combo(count) + combo(cList[index])-1
            oList.append(para)
        # free value
        else:
            num_free += count
            # print(value, 'is free,now has free fish :', num_free)

oList.append(combo(num_free))
# print('count:')

result = 1
for i in oList:
    result *= i
result += counter
result -= 1
print(result % mod_num)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
mod_num = 1000000007

vList = []
cList = []
num_zero = 0
num_b_zero = 0
num_free = 0


def combo(x: int) -> int:
    '''
    :param x:
    :param y:
    :return: int
    '''
    return 2**x


for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        num_zero += 1
    g = math.gcd(a, b)
    a, b = a/g, b/g
    if b == 0:
        num_b_zero += 1
    else:
        K_value = a/b
        # already exist
        if vList.count(K_value):
            index = vList.index(K_value)
            cList[index] += 1
        # new value
        else:
            vList.append(K_value)
            cList.append(1)
# print(vList)
# print(cList)
counter = 0
para = 0
oList = []
# (0,0)
counter += num_zero % mod_num
# (a,0) and (0,b)
if vList.count(0):
    vList.index(0)
    # print('(0,b) has ', cList[index])
    para += combo(cList[index])
if num_b_zero:
    para += combo(num_b_zero)
else:
    para = 1
# print('half 0 has ', para)
oList.append(para)
# normal
solved = []
for value, count in zip(vList, cList):
    if value not in solved:
        upside = -1/value
        # anti exist
        if vList.count(upside):
            solved.append(upside)
            index = vList.index(upside)
            # print(value, 'has anti ', upside, 'number', count, '-', cList[index])
            para = combo(count) + combo(cList[index])-1
            oList.append(para)
        # free value
        else:
            num_free += count
            # print(value, 'is free,now has free fish :', num_free)

oList.append(combo(num_free))
# print('count:')

result = 1
for i in oList:
    result *= i
result += counter
result -= 1
print(result % mod_num)

Submission status: Runtime Error

Solution code:
import math
n = int(input())
mod_num = 1000000007

vList = []
cList = []
num_zero = 0
num_b_zero = 0
num_free = 0


def combo(x: int) -> int:
    '''
    :param x:
    :param y:
    :return: int
    '''
    return 2**x


for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        num_zero += 1
    g = math.gcd(a, b)
    a, b = a/g, b/g
    if b == 0:
        num_b_zero += 1
    else:
        K_value = a/b
        # already exist
        if vList.count(K_value):
            index = vList.index(K_value)
            cList[index] += 1
        # new value
        else:
            vList.append(K_value)
            cList.append(1)
# print(vList)
# print(cList)
counter = 0
para = 0
oList = []
# (0,0)
counter += num_zero % mod_num
# (a,0) and (0,b)
if vList.count(0):
    vList.index(0)
    # print('(0,b) has ', cList[index])
    para += combo(cList[index])
if num_b_zero:
    para += combo(num_b_zero)
else:
    para = 1
# print('half 0 has ', para)
oList.append(para)
# normal
solved = []
for value, count in zip(vList, cList):
    if value not in solved:
        upside = -1/value
        # anti exist
        if vList.count(upside):
            solved.append(upside)
            index = vList.index(upside)
            # print(value, 'has anti ', upside, 'number', count, '-', cList[index])
            para = combo(count) + combo(cList[index])-1
            oList.append(para)
        # free value
        else:
            num_free += count
            # print(value, 'is free,now has free fish :', num_free)

oList.append(combo(num_free))
# print('count:')

result = 1
for i in oList:
    result *= i
result += counter
result -= 1
print(result)

Submission status: Runtime Error

Solution code:
from math import gcd

MOD = 1000000007

def solve(n, a, b):
    zero = 0
    D = {}
    for i in range(n):
        p, q = a[i], b[i]
        if (p == 0) and (q == 0):
            zero += 1
        else:
            if p < 0 and q < 0:
                p, q = -p, -q
            if p == 0:
                r = abs(q)
            elif q == 0:
                r = abs(p)
            else:
                r = gcd(p, q)
            k = (p // r, q // r)
            if not k in D:
                D[k] = 0
            D[k] += 1
    group = {}
    for (p, q), v in D.items():
        if (q, -p) in group:
            group[q, -p] += v                                                                                                            elif (-q, p) in group:                                                                                                               group[-q, p] += v
        else:                                                                                                                                group[p, q] = v                                                                                                          pow2 = [0] * (n+1)        
    pow2[0] = 1                                                                                                                      for i in range(n):                                                                                                                   pow2[i+1] = (pow2[i] * 2) % MOD
    ans = 1                                                                                                                          for (p, q), v in group.items():                                                                                                      t = pow2[D[p,q]]                  
        hit = False                                                                                                                      if (q, -p) in D:                                                                                                                     hit = True                            
            t += pow2[D[q, -p]]                                                                                                          if (-q, p) in D:                                                                                                                     hit = True                                    
            t += pow2[D[-q, p]]                                                                                                          ans = (ans * (t-hit)) % MOD                                                                                                  return (ans + zero - 1) % MOD                                     

n = int(input())
a = [0] * n                                                                       
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())                                                
print(solve(n, a, b))

Submission status: Runtime Error

Solution code:
import sys
from collections import namedtuple, defaultdict
from math import gcd
input = sys.stdin.readline

class Point:
    def __init__(self, x, y):
        g = gcd(abs(x), abs(y))

        x //= g
        y //= g

        if x < 0:
            x *= -1
            y *= -1

        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f'({self.x}, {self.y})'

def main():
    n = int(input())
    
    p = []
    d = defaultdict(lambda: 0)

    for _ in range(n):
        x, y = map(int, input().split())


        p.append(Point(x, y))
        d[p[-1]] += 1

    # print(d)

    MOD = 10 ** 9 + 7

    pw = [ pow(2, i, MOD) for i in range(n + 1) ]

    ans = 1
    tot = 0

    # pair = 0
    # for x in range(n):
    #     for y in range(x + 1, n):
    #         if p[x].x * p[y].x + p[x].y * p[y].y == 0:
    #             pair += 1

    # print(f'pairs = {pair}')

    for x in d.keys():
        if x.x > 0 and x.y >= 0 and x in d and Point(-x.y, x.x) in d:
            s = d[x]
            t = d[Point(-x.y, x.x)]

            # print(s, t)

            tot += s + t
            value = (pw[s] + pw[t] - 1 + MOD) % MOD
            ans = ans * value % MOD

    # print(f'tot={tot}, n={n}')

    ans = ans * pw[n - tot] % MOD
    ans = (ans - 1 + MOD) % MOD

    print(ans)
main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


def main():
    N = I()
    zero = 0
    plus_Ai_Bi = defaultdict(int)
    minus_Bj_Aj = defaultdict(int)
    zero_cnt = 0
    used = set()

    for i in range(N):
        a, b = MI()
        gcdab = gcd(abs(a), abs(b))
        a = a // gcdab
        b = b // gcdab
        n = 1

        if a == 0 and b == 0:
            zero_cnt += 1
            continue

        if a > 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a > 0 and b < 0:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a < 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(b, -a)] += 1
        else:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(b, -a)] += 1

    ans = 1

    for pair, cnt1 in plus_Ai_Bi.items():
        a, b = pair
        if pair in used:
            continue

        if pair in minus_Bj_Aj:
            cnt2 = minus_Bj_Aj[pair]
            group1 = pow(2, cnt1, MOD) - 1
            group2 = pow(2, cnt2, MOD) - 1
            ans *= group1 + group2 + 1
            ans %= MOD

            # avoid double count
            if a > 0:
                used.add((-b, a))
            else:
                used.add((b, -a))
        else:
            ans *= pow(2, cnt1, MOD)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


def main():
    N = I()
    zero = 0
    plus_Ai_Bi = defaultdict(int)
    minus_Bj_Aj = defaultdict(int)
    zero_cnt = 0
    used = set()

    for i in range(N):
        a, b = MI()
        gcdab = gcd(abs(a), abs(b))
        a = a // gcdab
        b = b // gcdab
        n = 1

        if a == 0 or b == 0:
            zero_cnt += 1
            continue

        if a > 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a > 0 and b < 0:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(-b, a)] += 1
        elif a < 0 and b > 0:
            plus_Ai_Bi[(a, b)] += 1
            minus_Bj_Aj[(b, -a)] += 1
        else:
            plus_Ai_Bi[(-a, -b)] += 1
            minus_Bj_Aj[(b, -a)] += 1

    ans = 1

    for pair, cnt1 in plus_Ai_Bi.items():
        a, b = pair
        if pair in used:
            continue

        if pair in minus_Bj_Aj:
            cnt2 = minus_Bj_Aj[pair]
            group1 = pow(2, cnt1, MOD) - 1
            group2 = pow(2, cnt2, MOD) - 1
            ans *= group1 + group2 + 1
            ans %= MOD

            # avoid double count
            if a > 0:
                used.add((-b, a))
            else:
                used.add((b, -a))
        else:
            ans *= pow(2, cnt1, MOD)

    print(ans - 1 + zero_cnt)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
from collections import Counter

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

I = []
zz = 0
sz = 0
tz = 0
for _ in range(N):
    a,b = map(int, input().split())

    # (a, b) = (0, 0)
    if a == 0 and b == 0:
        zero += 1
        continue
    # (a, b) = (0, #)
    if a == 0:
        sz += 1
        continue
    # (a, b) = (#, 0)
    if b == 0:
        tz += 1
        continue

    gcd = math.gcd(a, b)
    if b < 0:
        a *= -1
        b *= -1
    I.append((a//gcd,b//gcd))

S = []
T = []
C = Counter(I)
for a, b in C.keys():
    if a > 0:
        S.append(C[(a,b)])
        T.append(C[(-b,a)])
    else:
        if C[(b,-a)] == 0:
            S.append(0)
            T.append(C[(a,b)])

ans = 1
ans *= 2**sz + 2**tz - 1
ans %= MOD
for i in range(len(S)):
    ans *= 2**S[i] + 2**T[i] - 1
    ans %= MOD
ans += zz  # (0, 0)
ans -= 1
print(ans % MOD)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter

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

I = []
zz = 0
sz = 0
tz = 0
for _ in range(N):
    a,b = map(int, input().split())

    # (a, b) = (0, 0)
    if a == 0 and b == 0:
        zero += 1
        continue
    # (a, b) = (0, #)
    if a == 0:
        sz += 1
        continue
    # (a, b) = (#, 0)
    if b == 0:
        tz += 1
        continue

    gcd = math.gcd(a, b)
    if b < 0:
        a *= -1
        b *= -1
    I.append((a//gcd,b//gcd))

S = []
T = []
C = Counter(I)
for a, b in C.keys():
    if a > 0:
        S.append(C[(a,b)])
        T.append(C[(-b,a)])
    else:
        if C[(b,-a)] == 0:
            S.append(0)
            T.append(C[(a,b)])

ans = 1
ans *= 2**sz + 2**tz - 1
for i in range(len(S)):
    ans *= 2**S[i] + 2**T[i] - 1
ans += zz  # (0, 0)
ans -= 1
print(ans)