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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, atan2
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
AB = [LIST() for _ in range(N)]

zero = 0
tmp = []
dic = defaultdict(lambda: [0, 0])

for x, y in AB:
	if x == 0 and y == 0:
		zero += 1
	else:
		g = gcd(x, y)
		x //= g
		y //= g
		if y < 0: x *= -1; y *= -1
		if y == 0 and x < 0: x *= -1; y *= -1

		rot90 = (x <= 0)
		if rot90:
			x, y = y, -x
		if rot90:
			dic[(x, y)][0] += 1
		else:
			dic[(x, y)][1] += 1

ans = 1
for l in dic.values():
	ans *= (pow(2, l[0], mod)-1 + pow(2, l[1], mod)-1 + 1)
	ans %= mod

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

Solution (Python):
import math


n = int(input())
mod = 1000000007
ab = [list(map(int,input().split())) for _ in range(n)]
dic = {}
z = 0
nz,zn = 0,0
for a,b in ab:
    if a == 0 and b == 0:
        z += 1
        continue
    elif a == 0:
        zn += 1
        continue
    elif b == 0:
        nz += 1
    if a< 0:
        a = -a
        b = -b
    g = math.gcd(a,b)
    tp = (a//g,b//g)
    if tp not in dic:
        dic[tp] = 1
    else:
        dic[tp] += 1
    
ans = 1
nn = n - z - zn - nz
for tp,v in dic.items():
    if v == 0:
        continue
    vt = (tp[1],-1*tp[0])
    if vt in dic:
        w = dic[vt]
        
        e = pow(2,v,mod) + pow(2,w,mod) - 1
        ans *= e
        ans %= mod
        nn -= v + w 
        dic[tp] = 0
        dic[vt] = 0
ans *= pow(2,nn,mod)
if zn == 0:
    ans *= pow(2,nz,mod)
elif nz == 0:
    ans *= pow(2,zn,mod)
else:
    ans *= pow(2,nz,mod) + pow(2,zn,mod) - 1
ans += z - 1
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(300000)
from fractions import gcd
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
d = defaultdict(int)
zero = 0
for i in range(N):
    a, b = MI()
    if a == 0 and b == 0:
        zero += 1
        continue
    g = gcd(a, b)
    a, b = a // g, b // g
    minus = (-1) ** ((a < 0) + (b < 0))
    d[(minus * abs(a), abs(b))] += 1

ans = 1
seen = set()
for a, b in d:
    if (a, b) not in seen:
        if (a, b) in [(1, 0), (0, 1)]:
            ainv, binv = b, a
        else:
            ainv, binv = b * (1 if a < 0 else -1), abs(a)
        lans = (2 ** d[(a, b)] - 1)
        lans += (2 ** d[(ainv, binv)] - 1) if d.get((ainv, binv)) is not None else 0
        lans += 1
        ans = ans * lans % MOD
        seen.add((a, b))
        seen.add((ainv, binv))
ans = (ans + zero) % MOD
print((ans + MOD - 1) % MOD)

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

mod = 10 ** 9 + 7

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

d = {}
z = 0

pow_2 = [1]

for i in range(n):
    pow_2.append(pow_2[-1] * 2 % mod)

for a, b in ab:
    if a == 0 and b == 0:
        z += 1
        continue

    if a == 0 and b != 0:
        key = (0, 1)
    elif a * b > 0:
        g = gcd(a, b)
        key = (abs(a // g), abs(b // g))
    else:
        continue

    if key not in d:
        d[key] = [0, 0]
    d[key][0] += 1

for a, b in ab:
    if a != 0 and b == 0:
        key = (0, 1)
    elif a * b < 0:
        g = gcd(a, b)
        key = (abs(b // g), abs(a // g))
    else:
        continue
    
    if key in d:
        d[key][1] += 1


lo = n - z

ans = 1

for x, xi in d.values():
    if x * xi > 0:
        ans *= ((pow_2[x] - 1) + (pow_2[xi] - 1) + 1)
        ans %= mod
        lo -= x + xi

ans = (ans * pow_2[lo] + z - 1) % mod   

print(ans)

Solution (Python):
from math import gcd

n = int(input())
ab = [map(int, input().split()) for _ in range(n)]
mod = 1000000007

pair = []
d = {}
d[0] = {}
d[0][0] = 0

for a, b in ab:
   x = gcd(a, b)
   if x != 0:
      a //= x
      b //= x
   pair.append((a, b))

   d.setdefault(a, {})
   d[a].setdefault(b, 0)
   d[a][b] += 1
used = set()
ans = 1
for a, b in pair:
   if (a, b) in used:
      continue
   used.add((a, b))

   if a == 0 and b == 0:
      continue

   i = d[a][b]
   j, k, l = 0, 0, 0
   if -a in d and -b in d[-a]:
      j = d[-a][-b]
      used.add((-a, -b))
   if -b in d and a in d[-b]:
      k = d[-b][a]
      used.add((-b, a))
   if b in d and -a in d[b]:
      l = d[b][-a]
      used.add((b, -a))

   ans *= pow(2, i+j, mod) + pow(2, k+l, mod) - 1
   ans %= mod

ans += d[0][0] - 1
ans %= mod
print(ans)

Solution (Python):
import sys
from collections import defaultdict
from math import gcd
def input(): return sys.stdin.readline().strip()
mod = 1000000007

def main():
    N = int(input())
    fish = defaultdict(int)

    """
    b / aで値を管理するのは浮動小数点誤差が怖いので、
    g = gcd(a, b) として(a//g, b//g)のタプルで管理するのが良い。
    """

    zero = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0 and b == 0: zero += 1
        elif a == 0: fish[(0, 1)] += 1
        elif b == 0: fish[(1, 0)] += 1
        else:
            g = gcd(a, b)
            if a < 0: a, b = -a, -b
            fish[(a // g, b // g)] += 1
    
    
    """
    仲の悪い組を(S1, T1), (S2, T2),...とすれば(Si, Ti)からの魚の選び方と
    (Sj, Tj)からの魚の選び方は独立じゃん。
    なぜ気づかなかったのか。。。
    """
    
    ans = 1
    finished = set([])
    for a, b in fish:
        if (a, b) in finished: continue
        finished.add((a, b))
        s = fish[(a, b)]
        if b > 0:
            t = fish[(b, -a)] if (b, -a) in fish else 0
            finished.add((b, -a))
        else:
            t = fish[(-b, a)] if (-b, a) in fish else 0
            finished.add((-b, a))
        ans *= pow(2, s, mod) + pow(2, t, mod) - 1
        ans %= mod
        
    print((ans + zero - 1) % mod)



if __name__ == "__main__":
    main()

Solution (Python):

import sys
from collections import defaultdict
from math import gcd

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())





d_S = defaultdict(int)
d_T = defaultdict(int)

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

pow2_mod = [1] + [0] * (N + 10)
for i in range(1, N + 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    
    
    if A == 0 and B == 0:
        zeros += 1
    
    
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        if A < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            
        else:
            d_S[(-B, A)] += 0
            d_T[(A, B)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 
    tmp += pow2_mod[t_cnt] - 1 
    tmp += 1 
    ans = (ans * tmp)%MOD

ans -= 1 
ans += zeros 

print(ans%MOD)

Solution (Python):
from math import gcd

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

d = dict()
zeros=0
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    zeros+=1
    continue
  if all((a,b)):
    g = gcd(a,b)*(a//abs(a))
  elif a: g = a
  else: g = b
  
  p = a//g,b//g
  d[p] = d.get(p,0)+1

ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v,mod)+pow(2,w,mod)-1)
  ans %= mod
print((ans+zeros-1+mod)%mod)

Solution (Python):

import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())





d_S = defaultdict(int)
d_T = defaultdict(int)

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

pow2_mod = [1] + [0] * (N + 10)
for i in range(1, N + 10):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    
    
    if A == 0 and B == 0:
        zeros += 1
    
    
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            
        
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 
    tmp += pow2_mod[t_cnt] - 1 
    tmp += 1 
    ans = (ans * tmp)%MOD

ans -= 1 
ans += zeros 

print(ans%MOD)

Solution (Python):

import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())





d_S = defaultdict(int)
d_T = defaultdict(int)

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

pow2_mod = [1] + [0] * (N * 2)
for i in range(1, N * 2):
    pow2_mod[i] = pow2_mod[i-1] * 2 % MOD

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    
    
    if A == 0 and B == 0:
        zeros += 1
    
    
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow2_mod[s_cnt] - 1 
    tmp += pow2_mod[t_cnt] - 1 
    tmp += 1 
    ans = (ans * tmp)%MOD

ans -= 1 
ans += zeros 

print(ans%MOD)

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


def normal(x, y):
    if x == 0:
        return (0, 1)
    elif y == 0:
        return (1, 0)
    g = gcd(x, y)
    x, y = x // g, y // g
    if x < 0:
        x, y = -x, -y
    return (x, y)


def orthogonal(T):
    if T[0] == 0:
        return (1, 0)
    elif T[1] == 0:
        return (0, 1)
    if T[1] > 0:
        return (T[1], -T[0])
    else:
        return (-T[1], T[0])


N = int(input())
C = defaultdict(int)
z = 0
for i in range(N):
    Ai, Bi = map(int, input().split())
    if Ai == Bi == 0:
        z += 1
        continue
    n = normal(Ai, Bi)
    C[n] += 1

MOD = 1000000007
B = [1] * (N + 1)
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 % MOD

ans = 1
calc = set()
for n, c in C.items():
    if n in calc:
        continue
    a = B[c]
    calc.add(n)
    no = orthogonal(n)
    if no in C:
        co = C[no]
        a += B[co] - 1
        calc.add(no)
    ans *= a
    ans %= MOD
print((ans - 1 + z) % MOD)

Solution (Python):

import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())





d_S = defaultdict(int)
d_T = defaultdict(int)

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

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    
    
    if A == 0 and B == 0:
        zeros += 1
    
    
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow(2, s_cnt, MOD) - 1
    tmp += pow(2, t_cnt, MOD) - 1
    tmp += 1
    ans = (ans * tmp)%MOD

ans -= 1
ans += zeros

print(ans%MOD)

Solution (Python):
import math
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
    n = int(input())
    mod = 10 ** 9 + 7
    h = {}
    zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zero += 1
            continue
        m = (0, 0)
        if b == 0:
            m = (1, 0)
        elif b > 0:
            g = math.gcd(a, b)
            m = (a // g, b // g)
        else:
            g = math.gcd(a, b)
            m = (-1 * (a // g), -1 * (b // g))
        if m not in h:
            h[m] = set()
        h[m].add(i)
    h2 = {}
    for m in h:
        mi1 = (-1 * m[1], m[0])
        if mi1 in h and mi1 not in h2:
            h2[m] = mi1
        mi2 = (m[1], -1 * m[0])
        if mi2 in h and mi2 not in h2:
            h2[m] = mi2
    ans = 1
    left = n - zero
    for k, v in h2.items():
        s1 = len(h[k])
        s2 = len(h[v])
        
        r = (pow(2, s1 + s2, mod) - (pow(2, s1, mod) - 1) * (pow(2, s2, mod) - 1)) % mod
        ans *= r
        ans %= mod
        left -= (s1 + s2)
    ans *= pow(2, left, mod)
    ans -= 1
    ans += zero
    print(ans % mod)

if __name__ == '__main__':
    main()

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

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

d = defaultdict(int)
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = gcd(a,b)
        grad = 1 if a * b > 0 else -1
        a //= num_gcd
        b //= num_gcd
        d[(grad, abs(a), abs(b))] += 1

ans = 1
for k in d.keys():
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in d:
        
        
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0


ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD


ans += cnt_00

ans -= 1

ans %= MOD

print(ans)

Solution (Python):
import math
import copy

def main():
    N=int(input())
    zero_fish=0

    Pair={}

    for i in range(N):
        A,B=map(int,input().split())

        if A==0 and B==0:
            zero_fish+=1
            continue
        if B==0:
            bunsi=1
            bunbo=0
        elif B>0:
            bunsi=A//math.gcd(A,B)
            bunbo=B//math.gcd(A,B)
        else:
            bunsi=-1*A//math.gcd(A,B)
            bunbo=-1*B//math.gcd(A,B)

        key = str(bunsi) + "/" + str(bunbo)

        if bunsi == 0 or bunbo == 0:
            rev_bunsi = bunbo
            rev_bunbo = bunsi
        elif bunsi < 0:
            rev_bunsi = bunbo
            rev_bunbo = -1 * bunsi
        else:
            rev_bunsi = -1 * bunbo
            rev_bunbo = bunsi
        rev_key = str(rev_bunsi) + "/" + str(rev_bunbo)

        if (key in Pair.keys()):
            Pair[key][0]+=1
        elif (rev_key in Pair.keys()):
            Pair[rev_key][1]+=1
        else:
            Pair[key]=[1,0]

    res=1
    mod=1000000007
    for p in Pair.values():
        if p[1]==0:
            temp=pow(2,p[0],mod)
        else:
            temp=(pow(2,p[0],mod)+pow(2,p[1],mod)-1)%mod
        res=(res*temp)%mod
    res+=zero_fish-1

    print(res%mod)

if __name__=="__main__":
    main()

Solution (Python):
import sys
import math
from math import gcd

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
zero = 0
mp = {}
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())

    if a == 0 and b == 0:
        zero += 1
        continue
 
    g = gcd(a, b)
    a = a // g
    b = b // g
 
    if b < 0:
        a = -a
        b = -b
    if b == 0 and a < 0:
        a = -a
    if a <= 0:
        a, b = b, -a
        if (a, b) in mp:
            mp[(a, b)][0] += 1
        else:
            mp[(a, b)] = [1, 0]
    else:
        if (a, b) in mp:
            mp[(a, b)][1] += 1
        else:
            mp[(a, b)] = [0, 1]
 
ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, mod) + pow(2, t, mod) - 1
    ans %= mod
print((zero - 1 + ans) % mod)

Solution (Python):
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 
a_b = [] 
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) 
key_list = list(c.keys())

d = defaultdict(list) 
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: 
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 
used_cnt = double_zero_cnt 
for key in d.keys():
    if d[key] == []: 
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod 
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) 
ans += double_zero_cnt 
ans -= 1 
ans %= mod
print(ans)

Solution (Python):
import math
mod = 10**9+7
N = int(input())

iwashi01 = 0
iwashi10 = 0
iwashi00 = 0
iwashi = dict()
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        iwashi00 += 1
    elif a == 0:
        iwashi01 += 1
    elif b == 0:
        iwashi10 += 1            
    else:
        g = math.gcd(abs(a), abs(b))
        a //= g; b //= g
        if a*b > 0:
            if a < 0 and b < 0:
                a *= -1
                b *= -1
            iwashi.setdefault((a, b), [0, 0])
            iwashi[(a, b)][0] += 1
        if a*b < 0:
            if a < 0 and b > 0:
                a *= -1
                b *= -1
            a, b = -b, a
            iwashi.setdefault((a, b), [0, 0])
            iwashi[(a, b)][1] += 1

r = 2**iwashi01 % mod - 1 + 2**iwashi10 % mod - 1 + 1
for s, t in iwashi.values():
    r *= 2**s % mod -1 + 2**t % mod -1 + 1
    r %= mod
print((r + iwashi00 - 1) % mod)

Solution (Python):
from math import gcd
n = int(input())
P = [tuple(map(int, input().split())) for i in range(n)]
C = {}
for x, y in P:
    if x == 0 and y == 0:
        x0, y0 = 0, 0
    elif x != 0 and y == 0:
        x0, y0 = 1, 0
    elif x == 0 and y != 0:
        x0, y0 = 0, 1
    else:
        g = gcd(x, y)
        x0, y0 = x // g, y // g
    if y0 < 0:
        x0, y0 = -x0, -y0
    try:
        C[(x0, y0)] += 1
    except KeyError:
        C[(x0, y0)] = 1
D = []
for x, y in C.keys():
    if x <= 0:
        try:
            C[(y, -x)]
        except KeyError:
            D.append((y, -x))
for x, y in D:
    C[(x, y)] = 0
ans = 1
p = 10**9 + 7
for x, y in C.keys():
    if x > 0:
        a = C[(x, y)]
        try:
            b = C[(-y, x)]
        except KeyError:
            b = 0
        ans *= pow(2, a, p) + pow(2, b, p) - 1
        ans %= p
try:
    ans += C[(0, 0)] - 1
except KeyError:
    ans -= 1
print(ans % p)

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

def main():
  p = 1000000007
  N = int(readline().strip())
  A = {}
  ans = 0
  for i in range(N):
    s = ''
    ai, bi = map(int, readline().split())
    if ai == 0 and bi == 0:
      ans += 1
      ans %= p
      continue
    gi = math.gcd(ai, bi)
    ai //= gi
    bi //= gi
    if ai != 0 and bi != 0:
      if ai < 0 and bi < 0:
        ai *= -1
        bi *= -1
      elif ai < 0:
        ai *= -1
        s = '-'
      elif bi < 0:
        bi *= -1
        s = '-'
    elif ai == 0 and bi != 0:
      ai = 0
      bi = 1
    elif bi == 0 and ai != 0:
      ai = 1
      bi = 0
      s = '-'
    xi = s + str(ai) + '/' + str(bi)
    if s == '':
      s = '-'
    else:
      s = ''
    yi = s + str(bi) + '/' + str(ai)
    if xi in A:
      A[xi][0] += 1
      A[xi][0] %= p
    elif yi in A:
      A[yi][1] += 1
      A[yi][1] %= p
    else:
      A[xi] = [1, 0]
  r = 1
  for i in A:
    r *= (pow(2, A[i][0], p) + pow(2, A[i][1], p) -1)
    r %= p
  ans += r - 1
  ans %= p
  print(ans)

if __name__ == '__main__':
  main()

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

n=int(input())
abd=defaultdict(int)
mod=10**9+7
wzero=0
azero=0
bzero=0
for i in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        wzero+=1
    elif a==0 and b!=0:
        azero+=1
    elif a!=0 and b==0:
        bzero+=1
    else:
        g=gcd(a,b)
        a=a//g
        b=b//g
        abd[(a,b)]+=1

liskey=list(abd.keys())
ans=1
for k in liskey:
    if abd[k] != 0:
        a,b=k
        x=abd[(a,b)]+abd[(-a,-b)]
        y=abd[(-b,a)]+abd[(b,-a)]
        abd[(a,b)]=0
        abd[(-a,-b)]=0
        abd[(-b,a)]=0
        abd[(b,-a)]=0
        ans*=(2**x+2**y-1+mod)%mod
        ans%=mod

ans*=(2**azero+2**bzero-1)
ans%=mod
ans=(ans+wzero)%mod
ans=(ans+mod-1)%mod
print(ans)

Solution (Python):
from collections import defaultdict
import math
import sys
input=sys.stdin.readline
MOD=10**9+7
N=int(input())

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

ratio_dic=defaultdict(int)
zero2_num=0

for i in range(N):
  A,B=map(int,input().split())
  if A==0 and B==0:
    zero2_num+=1
  elif A==0:
    ratio_dic[(0,1)]+=1
  elif B==0:
    ratio_dic[(1,0)]+=1
  elif B>0:
    AB_gcd=math.gcd(A,B)
    Arat=A//AB_gcd
    Brat=B//AB_gcd
    
    ratio_dic[(Arat,Brat)]+=1
  else:
    AB_gcd=math.gcd(A,B)
    Arat=-A//AB_gcd
    Brat=-B//AB_gcd    
    
    ratio_dic[(Arat,Brat)]+=1


answer=1
checked_set=set()
for k,v in list(ratio_dic.items()):
  if k in checked_set:
    continue
  
  a,b=k
  
  if a>0:
    ainv,binv=-b,a
  else:
    ainv,binv=b,-a
    
  num_k1=ratio_dic[(a,b)]
  num_k2=ratio_dic[(ainv,binv)]
  answer*=powmod(2,num_k1)+powmod(2,num_k2)-1
  answer%=MOD
  
  
  checked_set.add((a,b))
  checked_set.add((ainv,binv))
  
print((zero2_num+answer-1)%MOD)

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

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7


"""
愚直解
・全イワシの組み合わせを考える：2^N
・それぞれのイワシについて、仲が悪いかどうか確認する：nCk(2^x, 2)
間に合うはずがない

そもそも、仲の悪いイワシの条件が分かっているので、仲の悪いやつらをグループにする。で、仲の悪いやつの一方が選ばれるときは、もう一方は選ばれない、みたいにする。
(a,b)に対し、(-m*b, m*a)や(m*b, -m*a)は選べないので、これらを約分して、正の傾きと負の傾きで分けて数え上げる。
「正のグループから一つ以上選ぶ場合の数」＋「負のグループから一つ以上」＋「どちらも選ばない」が、このグループの選び方。
(a,0), (0,b)は約分できないので、分けて取る。
また、(0,0)は他のイワシと必ず仲が悪いのでこれは別に数える
最後に、何も選ばない場合を引いて終わり。

Fraction使ってやってみたが、間に合わない＆REでた。
gcdが間に合うのは意外だった（A,B <= |10**18|なので、きっと間に合わないと思ってた。）
"""

d = defaultdict(int)
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = gcd(a,b)
        grad = 1 if a * b > 0 else -1
        a //= num_gcd
        b //= num_gcd
        d[(grad, abs(a), abs(b))] += 1



ans = 1
for k in d.keys():
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in d:
        
        
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0


ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD


ans += cnt_00

ans -= 1

ans %= MOD

print(ans)

Solution (Python):


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    from math import gcd
    from collections import defaultdict
    dd = defaultdict(int)
    temp0=0

    for i in range(N):
        a,b=MI()
        if (a,b)==(0,0):
            temp0+=1
            continue
        
        if a<0:
            a*=-1
            b*=-1
        
        
        if a*b!=0:
            g=gcd(a,b)
            a=a//g
            b=b//g
            if a*b>0:
                dd[(a,b)]+=1
                dd[b,-a]+=0
                
            else:
                dd[(a,b)]+=1
                dd[(-b,a)]+=0
            
        elif (a,b)!=(0,0):
            
            if a==0:
                b=1
            else:
                a=1
                
            dd[(a,b)]+=1
            dd[(b,a)]+=0
        

    ans=1
    
    for k,v in dd.items():
        a,b=k
        if b<=0:
            continue
        
        
        if a*b!=0:
            v=dd[k]
            v2=dd[(b,-a)]
        else:
            v=dd[k]
            v2=dd[(b,a)]
        temp=pow(2,v,mod)+pow(2,v2,mod)-1
        
        ans=(ans*temp)%mod

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

main()

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

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

d = defaultdict(int)
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = gcd(a,b)
        grad = 1 if a * b > 0 else -1
        a //= num_gcd
        b //= num_gcd
        d[(grad, abs(a), abs(b))] += 1



ans = 1
for k in d.keys():
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in d:
        
        
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0


ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD


ans += cnt_00

ans -= 1

ans %= MOD

print(ans)

Solution (Python):
import math, collections
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N)]
mod = 10**9 + 7
C = collections.Counter()
gcd = math.gcd
a0 = 0
for a, b in AB:
    if a == b == 0:
        a0 += 1
    elif a == 0:
        C[0, -1] += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        C[a, b] += 1
ans = 1
for a, b in C:
    if C[b, -a]:
        continue
    elif C[-b, a]:
        ans *= (pow(2, C[a, b], mod) + pow(2, C[-b, a], mod) - 1) % mod
        ans %= mod
    else:
        ans *= pow(2, C[a, b], mod)
        ans %= mod
ans += a0 - 1
ans %= mod
print(ans)

Solution (Python):
import math
from collections import defaultdict
n = int(input())
p = defaultdict(int)
mod = 10 ** 9 + 7
ori = 0
for _ in range(n):
    a,b = map(int,input().split())
    if a == b == 0:
        ori += 1
        continue
    elif b < 0:
        a *= -1
        b *= -1
    elif b == 0 and a < 0:
        a *= -1
    if a == 0:
        p[(0,1)] += 1
    elif b == 0:
        p[(1,0)] += 1
    else:
        g = math.gcd(a,b)
        p[(a//g, b//g)] += 1

k = n - ori
ans = ori-1
tmp = 1
l = k
for q,num in sorted(p.items(), reverse=True):
    x,y = q
    if x <= 0:
        break
    if p[(-y, x)] >= 1:
        a,b = p[(x,y)], p[(-y, x)]
        tmp *= pow(2,a,mod) + pow(2,b,mod) - 1
        l -= a+b
tmp *= pow(2,l,mod)
print((ans+tmp) % mod)

Solution (Python):
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def mod_P(x):
    if x < 0:
        x += P
    high = x >> 127
    low = x & P
    x = low + high
    if x >= P:
        x -= P
    return x

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        q, r = divmod(b, a)
        a, b = r, a
        u, v = v - q * u, u
    if b < 0:
        v = -v
    if v < 0:
        v += P
    return v

pair_key = {0:-1, -1:0}

def to_key(a, b):
    if a == 0:
        return -1
    if b == 0:
        return 0
    
    x = mod_P(inv_mod(a) * abs(b))
    if b < 0:
        x = P - x
    y = P - mod_P(inv_mod(b) * abs(a))
    if a < 0:
        y = P - y
    pair_key[x] = y
    return x

  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key[key]
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Solution (Python):
from collections import defaultdict 
import sys
input = sys.stdin.readline
from math import gcd

MOD = 1000000007

dic1 = defaultdict(int)

All_zero = 0

S = set()
N = int(input())
ans = 0 
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0: 
        All_zero += 1
    elif a == 0:
        S.add((0, 1))
        dic1[(0, 1)] += 1
    elif b == 0:
        S.add((1, 0))
        dic1[(1, 0)] += 1
    else:
        GCD = gcd(a, b)
        a //= GCD
        b //= GCD
        if a < 0: 
            a *= -1
            b *= -1
        S.add((a, b))
        dic1[(a, b)] += 1
        
lst = []
for a, b in S:
    tmp11 = dic1[(a, b)]
    A = a
    B = b
    if B <= 0:
        B *= -1
        A *= -1
    tmp2 = dic1[(B, -A)]
    
    dic1[(B, -A)] = 0
    if tmp11 > 0:
        lst.append((tmp11, tmp2))



ans = 1
for a, b in lst:
    tmp = (pow(2, a, MOD) - 1) + (pow(2, b, MOD) - 1) + 1 
    ans *= tmp
    ans %= MOD

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