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

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
d = defaultdict(int)
zeros = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        if a == 0 and b == -1:
            b = 1
        d[(a, b)] += 1


ans = 1
free = 0
keys = sorted(d.keys())
for a, b in keys:
    n = d[(a, b)]
    if b > 0:
        if (b, -a) in d:
            m = d[(b, -a)]
            ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            free += n
    else:
        if (-b, a) not in d:
            free += n

ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Solution (Python):
import math

MOD = 1000000007

def normalize(p):
  if p[0] == 0:
    return (0, 1)
  if p[1] == 0:
    return (1, 0)
  if p[0] < 0:
    p = (-p[0], -p[1])
  g = math.gcd(p[0], abs(p[1]))
  return (p[0] // g, p[1] // g)

def enemy(p):
  return normalize((-p[1], p[0]))

n=int(input())
solo=0
groups=dict() 
for _ in range(n):
  x,y=map(int, input().split())
  if x == 0 and y == 0:
    solo += 1
  else:
    p = normalize((x,y))
    groups[p] = groups.get(p, 0) + 1


ans = 1
done=set()
for p in groups:
  q = enemy(p)
  if p in done or q in done:
    continue
  pcnt, qcnt = groups[p], groups.get(q, 0)
  
  mul = pow(2, pcnt, MOD) + pow(2, qcnt, MOD) + MOD - 1
  ans = ans * mul % MOD
  done.add(p)
  done.add(q)

ans = (ans + solo + MOD - 1) % MOD
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
ab=[list(map(int,input().split())) for i in range(n)]

dic=defaultdict(int)
zero=[0,0]
kasu=0
for i in range(n):
    a,b=ab[i]
    if a==0 and b==0:
        kasu+=1
    elif a==0:
        zero[0]+=1
    elif b==0:
        zero[1]+=1
    else:
        if a<0:
            a,b=-a,-b
        g=gcd(a,b)
        dic[(a//g,b//g)]+=1

anslst=[]
lst=list(dic.items())
ans=1

for i in range(len(lst)):
    iwa,m=lst[i]
    a,b=iwa
    tmp=1
    ll=max(dic[(b,-a)],dic[(-b,a)])
    tmp=pow(2,dic[iwa],mod)-1+pow(2,ll,mod)-1+1
    
    dic[(a,b)]=0
    dic[(b,-a)]=0
    dic[(-b,a)]=0
    ans*=tmp
    ans%=mod
    



ans*=pow(2,zero[0],mod)-1+pow(2,zero[1],mod)-1+1

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

Solution (Python):
N = int(input())
import math
sin_dic = {}
mod = 1000000007

zero_num = 0
for i in range(N):
    a, b = list(map(int, input().split()))
    if a == 0 and b == 0:
        zero_num += 1
        continue
    if a == 0:
        b = -1
    elif b == 0:
        a = 1
    else:
        c = math.gcd(a, b)
        a, b = a//c, b//c
        if a < 0 and b < 0:
            a, b = -a, -b
        elif a < 0 and b > 0:
            a, b = -a, -b
    if (a,b) in sin_dic:
        sin_dic[(a, b)].append(i)
    else:
        sin_dic[(a, b)] = [i]

ans = 1
skip_dic = {}
for (key, _key) , values in sin_dic.items():
    if (key, _key) in skip_dic:
        continue
    oth_len = 0
    norm_len = 0
    norm_len += len(values)
    if (-key, -_key) in sin_dic:
        norm_len += len(sin_dic[(-key, -_key)])
    if (_key, -key) in sin_dic:
        oth_len += len(sin_dic[(_key, -key)])
    if (-_key, key) in sin_dic:
        oth_len += len(sin_dic[(-_key, key)])

    p = pow(2, oth_len, mod) - 1 + pow(2, norm_len, mod)
    ans = (ans * p) % mod
    skip_dic[(key, _key)] = True
    skip_dic[(-key, -_key)] = True
    skip_dic[(_key, -key)] = True
    skip_dic[(-_key, key)] = True
print((ans-1 + zero_num) % mod)

Solution (Python):
import math
MOD = 1000000007
N = int(input())

d_p = dict()
d_m = dict()
ans = 1
zz = 0

for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 0
        b = 0
    elif b==0:
        n_sign = 1
        a = 0

    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      

for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD

ans -= 1
ans += zz
ans %= MOD
print (ans)

Solution (Python):


import math

M = 1000000007

def normalize(v):
    (a, b) = v
    if a * b > 0:
        return (a, b)
    else:
        if a > 0:
            return (-b, a)
        else:
            return (b, -a)
    
def inv(v):
    (a, b) = v
    if a > 0:
        return (-b, a)
    else:
        return (b, -a)
    
    
n = int(input())

vs = {}
zc = 0
azc = 0
bzc = 0

for i in range(n):
    (a, b) = map(int, input().split())
    if b < 0:
        a = -a
        b = -b

    g = math.gcd(a, b)
        
    if a == 0 and b == 0:
        zc += 1
        continue

    if a == 0:
        azc += 1
        continue

    if b == 0:
        bzc += 1
        continue

    (a, b) = (a // g, b // g)
    if (a, b) in vs:
        vs[(a, b)] += 1
    else:
        vs[(a, b)] = 1

wp = set()
for v in vs:
    if inv(v) in vs:
        wp.add(normalize(v))


        
c = 1
if azc == 0 or bzc == 0:
    c = c * pow(2, azc + bzc, M) % M
else:
    c = c * (pow(2, azc, M) - 1 + pow(2, bzc, M) - 1 + 1) % M

r = n - azc - bzc
for p in wp:
    invp = inv(p)
    c = c * (pow(2, vs[p], M) - 1 + pow(2, vs[invp], M) - 1 + 1) % M
    r -= vs[p] + vs[invp]

r -= zc
c = c * pow(2, r, M) % M
c = (c + zc) % M
c = (c - 1) % M

print(c)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin, gcd
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 1000000007

n = I()
D = defaultdict(int)
A = []
B = []
F = []
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

ans = 1
cnt1 = 0
cnt2 = 0
cnt3 = 0
for i in range(n):
    a, b = LI()
    flg = 0
    if a * b < 0:
        flg = 1
    a = abs(a)
    b = abs(b)
    g = gcd(a, b)
    if g:
        a = a // g
        b = b // g
    A += [a]
    B += [b]
    F += [flg]
    if a == 0 and b == 0:
        cnt3 += 1
    elif a == 0:
        cnt1 += 1
    elif b == 0:
        cnt2 += 1
    else:
        D[(flg, a, b)] += 1

visited = defaultdict(int)
for j in range(n):
    fi, ai, bi = F[j], A[j], B[j]
    if ai == 0 or bi == 0:
        continue
    if visited[(fi, ai, bi)]:
        continue
    visited[(fi, ai, bi)] = 1
    visited[(fi ^ 1, bi, ai)] = 1
    ans = ans * (pow2[D[(fi, ai, bi)]] + pow2[D[(fi ^ 1, bi, ai)]] - 1) % mod

print((ans * (pow2[cnt1] + pow2[cnt2] - 1) + cnt3 - 1) % mod)

Solution (Python):
def resolve():
    import math
    from fractions import Fraction
    mod = 10**9 + 7
    n = int(input())
    enpty = 0
    dic1 = {}
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            enpty += 1
        else:
            c = math.gcd(a,b)
            a = a//c
            b = b//c
            if b < 0 or (b==0 and a<0):
                a = -a
                b = -b
            if (a, b) in dic1:
                dic1[(a, b)] += 1
            else:
                dic1[(a,b)] = 1

    ans = 1

    for (a, b), num in dic1.items():
        if (-b, a) in dic1:
            ans = (ans*(pow(2, num, mod)+pow(2, dic1[(-b, a)], mod)-1))%mod
        elif not (b, -a) in dic1:
            ans = (ans*pow(2, num, mod))%mod

    print((ans-1+enpty)%mod)


resolve()

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
d = defaultdict(int)
zeros = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        d[(a, b)] += 1


ans = 1
free = 0
keys = sorted(d.keys())
for a, b in keys:
    n = d[(a, b)]
    if a != 0 and b != 0:
        if b > 0:
            if (b, -a) in d:
                m = d[(b, -a)]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
            else:
                free += n
        else:
            if (-b, a) not in d:
                free += n
x, y, z = d[(0, 1)], d[(1, 0)], d[(0, -1)]
ans = ans * (pow(2, x + z, MOD) + pow(2, y, MOD) - 1) % MOD
ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
d = defaultdict(int)
zeros = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        d[(a, b)] += 1


ans = 1
free = 0
keys = sorted(d.keys())
for a, b in keys:
    n = d[(a, b)]
    if a != 0 and b != 0:
        if b > 0:
            if (b, -a) in d:
                m = d[(b, -a)]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
            else:
                free += n
        else:
            if (-b, a) not in d:
                free += n
x, y, z = d[(0, 1)], d[(1, 0)], d[(0, -1)]
ans = ans * (pow(2, x + z, MOD) + pow(2, y, MOD) - 1) % MOD
ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Solution (Python):
from collections import defaultdict
from math import gcd
mod = 1000000007

n = int(input())
plus = defaultdict(int)
minus = defaultdict(int)
a_0 = 0
b_0 = 0
a_b_0 = 0
xxx = 10 ** 10
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else:
            b_0 += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a * b < 0:
        minus[(abs(a), abs(b))] += 1
    else:
        plus[(abs(b), abs(a))] += 1

total = 0
lst = []
for num, _ in minus.items():
    a1 = minus[num]
    a2 = plus[num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)

Solution (Python):
from math import gcd

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

z = 0
za = 0
zb = 0
d = {}

for _ in range(n):
    a,b = map(int,input().split())
    if a == 0 and b ==0:
        z += 1
    elif a == 0:
        za += 1
    elif b == 0:
        zb += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        if b > 0:
            if (a,b) in d:
                d[(a,b)][0] += 1
            else:
                d[(a,b)] = [1,0]
        else:
            if (-b,a) in d:
                d[(-b,a)][1] += 1
            else:
                d[(-b,a)] = [0,1]

ans = 1
for key in d:
    ans *= (pow(2,d[key][0],mod) + pow(2,d[key][1],mod) - 1) % mod
    ans %= mod
ans *= (pow(2,za,mod) + pow(2,zb,mod) - 1) % mod
ans %= mod
print((ans + z - 1)%mod)

Solution (Python):
from sys import stdin, setrecursionlimit


def gcd(x, y):
    if x % y == 0:
        return y
    return gcd(y, x % y)


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    zz = 0

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            g = gcd(a, b)
            f = b / a
            if b / a < 0:
                m.append(str(abs(a // g)) + ':' + str(abs(b // g)))
            elif f > 0:
                p.append(str(abs((b // g))) + ':' + str(abs((a // g))))
        elif a == 0 and b == 0:
            zz += 1
        elif a == 0:
            m.append(0)
        elif b == 0:
            p.append(0)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans + zz - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Solution (Python):
import sys
from collections import defaultdict
dic1 = defaultdict(int)
dic2 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
def pow(n,p,mod=10**9+7): 
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)
n = int(readline())
zero = 0
for i in range(n):
    a,b= map(int,readline().split())
    if a == b == 0:
        zero += 1
        continue
    plamai = 1 if a*b > 0 else 0
    a,b = to_standard_form(a,b)
    if b <= 0:
        dic2[(a,b)] += 1
    else:
        dic1[(b,-a)] += 1
        dic2[(b,-a)] += 0

ans = zero
k = 1
for key,cnt in dic2.items():
    cnt2 = dic1[key]
    x = pow(2,cnt)+pow(2,cnt2)
    k = k*(x-1)%mod
print((ans+k-1)%mod)

Solution (Python):
import collections

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

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if (a>0 and b>0) or (a<0 and b<0):
      dic[(abs(a)//g,abs(b)//g)]+=1
    elif (a<0 and b>0) or (a>0 and b<0):
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(1,0)]+=1
    elif b==0:
      dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)],mod)
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)],mod)
      ans%=mod
print((ans+cnt-1)%mod)

Solution (Python):

from collections import Counter
import math
import sys
try:
    import typing
    from typing import List, Tuple
except ImportError:
    pass

MOD = 1000000007  


def solve(N: int, A: "List[int]", B: "List[int]"):
    nz = 0
    c = Counter()  
    for Ai, Bi in zip(A, B):
        if Ai == Bi == 0:
            nz += 1
            continue
        g = math.gcd(Ai, Bi)
        Ai //= g
        Bi //= g
        if Ai == 0 and Bi < 0 or Ai < 0:
            Ai *= -1
            Bi *= -1
        c[Ai, Bi] += 1
    dc = dict(c)
    ans = 1
    for Ai, Bi in dc:
        na = dc[Ai, Bi]
        if Bi <= 0:
            if (-Bi, Ai) in dc:
                nb = dc[-Bi, Ai]
                ans = ans * (pow(2, na, MOD) + pow(2, nb, MOD) - 1) % MOD
            else:
                ans = ans * pow(2, na, MOD) % MOD
        else:
            if (Bi, -Ai) not in dc:
                ans = ans * pow(2, na, MOD) % MOD
    ans -= 1
    ans += nz
    ans %= MOD
    print(ans)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]

def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]

def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)


def to_frac(A,B):
    g = math.gcd(A,B)
    A = A//g
    B = B//g
    if A<0:
        A *= -1
        B *= -1

    return (A,B)
N = I()
cnt = {}
pair = {}
bothzero = 0
for i in range(N):
    A,B = MI()
    if A==0 and B==0:
        bothzero += 1
    elif B==0:
        pair[0]=pair.get(0,0)+1
    elif A == 0:
        cnt[0]=cnt.get(0,0)+1
    elif A/B>0:
        frac = to_frac(A,B)
        cnt[frac]=cnt.get(frac,0)+1
    else:
        frac = to_frac(-B,A)
        pair[frac]=pair.get(frac,0)+1
res = N-bothzero
ans = 1
for v in cnt:
    if pair.get(v,0)==0:
        continue
    res -= (cnt[v]+pair[v])
    ans = ans*((pow(2,cnt[v],MOD)+pow(2,pair[v],MOD)-1)%MOD)
    ans = ans%MOD
ans = (ans*pow(2,res,MOD)-1)%MOD
ans = (ans+bothzero)%MOD
print(ans)

Solution (Python):
from math import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases += 1
    elif a * b >=0 and b != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans+zero_cases-1) % MOD)

Solution (Python):
import math
mod = 10**9 + 7
n = int(input())
d = {}
d0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    if g == 0:
        d0 += 1
    else:
        a //= g
        b //= g
        if a < 0:
            a = -a
            b = -b
        elif a == 0 and b < 0:
            b = -b
        if (a,b) in d:
            d[(a,b)] += 1
        else:
            d[(a,b)] = 1
ans = 1
for (a,b) in d.keys():
    if d[(a,b)] > 0:
        t = 2**d[(a,b)]
        if b <= 0:
            a = -a
            b = -b
        if (b,-a) in d:
            t += 2**d[(b,-a)] - 1
            d[(b,-a)] = 0
        ans *= t
        ans %= mod
print((ans+d0-1)%mod)

Solution (Python):

import sys
from math import gcd

N, *AB = map(int, sys.stdin.buffer.read().split())

dict_F = {}
count_0 = 0

def insert(A,B,s): 
  if (A,B) not in dict_F.keys():
    dict_F[(A,B)] = [0,0]
  dict_F[(A,B)][s] += 1

def make_power2(N):
  result = 1
  list_result = [1]
  for _ in range(N):
    result = (2*result)%mod
    list_result.append(result)
  return list_result

for i in range(N):
  A,B = AB[2*i:2*i+2]
  if A==0 and B==0:
    count_0 += 1
    continue
  g = gcd(A,B)
  A //= g
  B //= g
  if A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
power2 = make_power2(N)
answer = 1

for A,B in dict_F.values():
  answer = (answer*(power2[A]+power2[B]-1))%mod
answer = (answer+count_0-1)%mod

print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
import math

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    if g == 0:
        Empty += 1
        continue
    x, y = x//g, y//g
    if y < 0 or (y==0 and x < 0):
        y = -y
        x = -x
    if (x, y) in As:
        As[(x, y)] += 1
    else:
        As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1+Empty)%mod)

Solution (Python):
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
d = dict()
zeros = 0
for _ in range(N):
    a, b = tuple(map(int, input().split()))
    if not any((a, b)):
        zeros += 1
        continue
    g = gcd(a, b) * (a // abs(a)) if all((a, b)) else a if a else b
    p = a // g, b // g
    d[p] = d.get(p, 0) + 1
counts = dict()
for (a, b), v in d.items():
    if counts.get((b, -a), False) or counts.get((-b, a), False):
        continue
    counts[(a, b)] = v, d.get((b, -a), 0) + d.get((-b, a), 0)
total = 1
for a, b in counts.values():
    total = (total * (pow(2, a, MOD) + pow(2, b, MOD) - 1)) % MOD
print((total + zeros + MOD - 1) % MOD)

Solution (Python):
import math
from collections import Counter

mod = 10**9+7
n = int(input())
c = Counter()
cc = Counter()

for _ in range(n):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        c[-1] += 1
        continue
    elif a != 0 and b == 0:
        a, b = 1, 0
    elif a == 0 and b != 0:
        a, b = 0, 1
    else:
        a, b = a//math.gcd(a, b), b//math.gcd(a, b)

    c[(a, b)] += 1
    cc[(a, b)] += 1

l = []

for r in cc.keys():
    if r == -1:
        continue
    ra = c[r]

    a, b = r
    if a == 0:
        r_inv = (1, 0)
    elif b == 0:
        r_inv = (0, 1)
    elif a > 0:
        r_inv = (-b, a)
    else:
        r_inv = (b, -a)
    rb = c[r_inv]

    if ra >= 0 and rb >= 0:
        l.append([ra, rb])
        c[r] -= 10**9
        c[r_inv] -= 10**9

ans = 1
for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1
    ans %= mod

ans = (ans-1) + c[-1]
ans %= mod

print(ans)

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

mod=10**9+7
n=int(input())
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a*b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
print((ans+cnt-1)%mod)

Solution (Python):
import math
MOD =1000000007


def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}

a_zero_cnt = 0
b_zero_cnt = 0
ab_zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 and b!=0:
        a_zero_cnt += 1
    elif  a!=0 and b==0:
        b_zero_cnt += 1
    elif a == 0 and b == 0:
        ab_zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += v



ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

zero_m = max(pow_k(2,a_zero_cnt) + pow_k(2,b_zero_cnt) -1, 1)
ans *= zero_m
ans += ab_zero_cnt
ans -= 1
print(ans%MOD)

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

mod=10**9+7
n=int(input())
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if (a>0 and b>0) or (a<0 and b<0):
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    elif (a<0 and b>0) or (a>0 and b<0):
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)],mod)
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)],mod)
      ans%=mod
print((ans+cnt-1)%mod)