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):
def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

def nasu(a, b):
  g = gcd(a, b)
  if g < 0:
    g *= -1
  if b < 0:
    a *= -1
    b *= -1
  return [a // g, b // g]

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

MOD = 10 ** 9 + 7
R = {}

ze = 0
na = 0
su = 0
for a, b in AB:
  if a == 0 and b == 0: 
    ze += 1
    continue
  if b == 0:
    na += 1
  elif a == 0:
    su += 1
  else:
    a, b = nasu(a, b)
    if a in R:
      if b in R[a]:
        R[a][b] += 1
      else:
        R[a][b] = 1
    else:
      R[a] = {}
      R[a][b] = 1

L = []
for i in R.keys():
  for j in R[i].keys():
    a, b = i, j
    x, y = -j, i
    if x < 0 and y < 0:
      x *= -1
      y *= -1
    t = R[i][j]
    if x not in R:
      L.append(pow(2, t, MOD))
      continue
    if y not in R[x]:
      L.append(pow(2, t, MOD))
      continue
    k = R[x][y]
    L.append((pow(2, t) + pow(2, k) - 1) % MOD)
    R[a][b] = 0
    R[x][y] = 0

L.append((pow(2, na) + pow(2, su) - 1) % MOD)

ans = 1
for i in L:
  ans = ans * i % MOD

ans = (ans + ze) % MOD

ans -= 1
if ans < 0:
  ans += MOD
print(ans)

Solution (Python):
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


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


def main():
    N = I()
    zero = 0
    cnts = defaultdict(int)
    used = set()

    for i in range(N):
        a, b = MI()
        if a == 0 and b == 0:
            zero += 1
            continue

        g = gcd(abs(a), abs(b))
        a = a // g
        b = b // g
        if b < 0:
            a = -a
            b = -b
        cnts[(a, b)] += 1

    

    ans = 1
    for key, c in cnts.items():
        if key in used:
            continue
        a, b = key
        if a > 0:
            rev = (-b, a)
        else:
            rev = (b, -a)

        if rev in cnts:
            
            ans *= (pow(2, cnts[key], MOD) - 1) + (pow(2, cnts[rev], MOD) - 1) + 1
            
            ans %= MOD
            used.add(rev)
        else:
            ans *= pow(2, cnts[key], MOD)

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


if __name__ == '__main__':
    main()

Solution (Python):
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


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


def main():
    N = I()
    zero = 0
    cnts = defaultdict(int)
    used = set()

    for i in range(N):
        a, b = MI()
        if a == 0 and b == 0:
            zero += 1
            continue

        g = gcd(abs(a), abs(b))
        a = a // g
        b = b // g
        if b < 0:
            a = -a
            b = -b
        cnts[(a, b)] += 1

    

    ans = 1
    for key, c in cnts.items():
        if key in used:
            continue
        a, b = key
        if a > 0:
            rev = (-b, a)
        else:
            rev = (b, -a)

        if rev in cnts:
            ans *= pow(2, cnts[key], MOD) + pow(2, cnts[rev], MOD) - 1
            
            ans %= MOD
            used.add(rev)
        else:
            ans *= pow(2, cnts[key], MOD)

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

    
    

    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    


if __name__ == '__main__':
    main()

Solution (Python):

from sys import stdin
from collections import defaultdict
from math import gcd

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    MOD = 1000000007
    
    N, *AB = map(int, stdin.buffer.read().split())
    d = defaultdict(int)
    zeros = 0
    for a, b in zip(AB[::2], AB[1::2]):
        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
    for (a, b), n in d.items():
        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)

if __name__ == '__main__':
    main()

Solution (Python):





import sys
import heapq

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

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    
    zAns = 2 ** (len(zpList) + len(znList)) % modVal + 2 ** (len(pzList) + len(nzList)) % modVal - 1
    zAns = zAns % modVal
    ans = zAns

    
    ratioDict = {}
    for i in ppList:
        gcdVal = gcd(i[0], i[1])
        ratio = (i[0] // gcdVal, i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        gcdVal = gcd(-i[0], -i[1])
        ratio = (-i[0] // gcdVal, -i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):
import math
import collections
from collections import defaultdict
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=10**9+7

L=[]
ct0=0
for i in range(n):
  if l[i][0]==0 and l[i][1]==0:
    ct0+=1
  elif l[i][0]==0:
    L.append((0,1))
  elif l[i][1]==0:
    L.append((1,0))
  elif l[i][0]<0:
    L.append((-l[i][0]//math.gcd(l[i][0],l[i][1]),-l[i][1]//math.gcd(l[i][0],l[i][1])))
  else:
    L.append((l[i][0]//math.gcd(l[i][0],l[i][1]),l[i][1]//math.gcd(l[i][0],l[i][1])))

ans=1
d=set()
c=collections.Counter(L)
for i in c.keys():
  if i[0]==0:
    x=(1,0)
  elif i[1]==0:
    x=(0,1)
  elif i[1]<0:
    x=(-i[1],i[0])
  else:
    x=(i[1],-i[0])
  if i not in d:
    ans*=pow(2,c[i],mod)+pow(2,c[x],mod)-1
    ans%=mod
    d.add(x)
print((ans-1+ct0)%mod)

Solution (Python):
from collections import Counter
import math
n = int(input())
pp = []
a0 = 0
b0 = 0
z = 0

for i in range(n):
  a,b = map(int,input().split())
  if a==0 and b==0:
    z += 1
  elif a==0:
    a0 += 1
  elif b==0:
    b0 += 1
  else:
    gomi = math.gcd(a,b)
    if a < 0:
      a *= -1
      b *= -1
    pp.append((a//gomi,b//gomi))
    
mod = 10**9+7
a0 %= mod
b0 %= mod
z %= mod
p = Counter(pp)
r = 1
s = set()

for i,j in p.keys():
  if (i,j) in s:
    continue
  ans = p[(i,j)]
  if j < 0:
    f = (-j,i)
  else:
    f = (j,-i)
  chk = p[f]
  r *= (pow(2,ans,mod)+pow(2,chk,mod)-1)%mod
  r %= mod
  s.add(f)
r *= (pow(2,a0,mod)+pow(2,b0,mod)-1)%mod
r %= mod
print((r+z-1)%mod)

Solution (Python):
from math import gcd

mod = 10 ** 9 + 7
n = int(input())
iwashi = dict()
origin_iwashi = 0
for _ in range(n):
  a, b = map(int, input().split())
  if a == b == 0:
    origin_iwashi += 1
  elif a == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][1] += 1
    else:
      iwashi[(1, 0)] = [0, 1]
  elif b == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][0] += 1
    else:
      iwashi[(1, 0)] = [1, 0]
  else:
    if b < 0:
      a, b = -a, -b
    g = gcd(a, b)
    a //= g
    b //= g
    if a > 0:
      if (a, b) in iwashi:
        iwashi[(a, b)][0] += 1
      else:
        iwashi[(a, b)] = [1, 0]
    else:
      if (b, -a) in iwashi:
        iwashi[(b, -a)][1] += 1
      else:
        iwashi[(b, -a)] = [0, 1]
count = 1
for i, j in iwashi.values():
  tmp = pow(2, i, mod) + pow(2, j, mod) - 1
  count = count * tmp % mod
count = (count + origin_iwashi - 1) % mod
print(count)

Solution (Python):
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        
        if a != 0 and b != 0:
            g = gcd(a, b) * a // abs(a)
        elif a != 0:
            g = a
        else:
            g = b
        pair[(a // g, b // g)] += 1  

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  
        done.add((a, b))

        
        w = pair[(b, -a)] + pair[(-b, a)]
        
        
        
        
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Solution (Python):


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


N = int(input())
AB = [LI() for _ in range(N)]

MOD = 10 ** 9 + 7


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


def create_pairs():
    z = 0
    d = {}
    for a, b in AB:
        
        if a == 0 and b == 0:
            z += 1
            continue
        if a == 0:
            b = 1
        elif b == 0:
            a = 1
        else:
            m = abs(gcd(a, b))
            a, b = a // m, b // m
        
        
        if b < 0:
            a, b = -a, -b

        if a > 0:
            t = (a, b)
            i = 0
        else:
            t = (b, -a)
            i = 1
        if t in d:
            d[t][i] += 1
        else:
            d[t] = [0, 0]
            d[t][i] += 1
    
    return d, z


def main():
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(1, N + 1):
        p2[i] = p2[i - 1] * 2 % MOD
    
    d, z = create_pairs()
    ans = 1
    for x, y in d.values():
        v = p2[x] + p2[y] - 1
        ans = ans * v % MOD

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

if __name__ == "__main__":
    main()

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

MOD = 10**9+7
N = int(input())
d = defaultdict(int)
zero = [0, 0, 0]
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero[0] += 1
        continue
    if a == 0:
        zero[1] += 1
        continue
    if b == 0:
        zero[2] += 1
        continue

    s = -1 if (a*b) < 0 else 1
    g = gcd(a, b)
    a //= g
    b //= g

    d[(s, abs(a), abs(b))] += 1

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

ans *= pow(2, zero[1], MOD)+pow(2, zero[2], MOD)-1
ans %= MOD

ans += zero[0]
ans -= 1
ans %= MOD

print(ans)

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

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

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

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

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

Solution (Python):
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        left_zero += 1
    elif b == 0:
        right_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a,b] += 1
done = set()
ans = 1
for a,b in dic:
    k = (a, b)
    if k in done: continue
    rk = (-b, a)
    rk2 = (b, -a)
    done.add(k)
    done.add(rk)
    done.add(rk2)
    c = pow(2, dic[k], MOD)-1
    if rk in dic:
        c += pow(2, dic[rk], MOD)-1
    if rk2 in dic:
        c += pow(2, dic[rk2], MOD)-1
    c += 1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
print((ans-1)%MOD)

Solution (Python):
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        left_zero += 1
    elif b == 0:
        right_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a,b] += 1
done = set()
ans = 1
for a,b in dic:
    k = (a, b)
    if k in done: continue
    rk = (-b, a)
    rk2 = (b, -a)
    done.add(k)
    done.add(rk)
    done.add(rk2)
    c = pow(2, dic[k], MOD)-1
    if rk in dic:
        c += pow(2, dic[rk], MOD)-1
    if rk2 in dic:
        c += pow(2, dic[rk2], MOD)-1
    c += 1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
print((ans-1)%MOD)

Solution (Python):
import math

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

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (pow(2, num2, mod) + pow(2, num3, mod) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= pow(2, n, mod)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)

Solution (Python):
import sys
import math
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[str(Fraction(a, b))] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = str(Fraction(a, b))
    if done[k]: continue
    rk = str(Fraction(-b, a))
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)

Solution (Python):
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 1 ;count = 0 ;pro = 1
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

n = int(input())
def make_key0(a,b):
  if a == 0 and b != 0:
    return(0,1)
  elif a != 0 and b == 0:
    return(1,0)
  if (a < 0 and b > 0) or (a > 0 and b < 0):hugou = 1
  else: hugou = -1
  a = abs(a)
  b = abs(b)
  G = gcd(a,b)
  return (hugou*(abs(a)//G),abs(b)//G)

C0 = collections.Counter()

for i in range(n):
  a,b = map(int,input().split())
  if (a,b) == (0,0) :count += 1
  else:
    a0,b0 = make_key0(a,b)
    C0[(a0,b0)] += 1

S = set()
for key,val in C0.items():
  a0,b0 = key
  S.add((a0,b0))
  a1,b1 = make_key0(b0,a0)
  if (a1,b1) in S:continue
  ans *= pow(2,val,mod) + pow(2,C0[(a1,b1)],mod) -1
  ans %= mod
ans += count 
print((ans-1)%mod)

Solution (Python):
from math import gcd

n = int(input())
MOD = 10**9+7
p_map = {}
n_map = {}

p_zero_map = 0
n_zero_map = 0
z_map = 0
for _ in range(n):
    ab = list(map(int, input().split()))
    ab_gcd = gcd(ab[0], ab[1])
    if ab_gcd == 0:
        ab_gcd = 1
    a = ab[0]//ab_gcd
    b = ab[1]//ab_gcd

    if (a > 0 and b > 0) or (a < 0 and b < 0):
        if a < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in p_map:
            p_map[key] = 1
        else:
            p_map[key] += 1
    elif a == 0 and b == 0:
        z_map += 1
    elif a == 0 and b != 0:
        n_zero_map += 1
    elif b == 0 and a != 0:
        p_zero_map += 1
    else:
        if b < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in n_map:
            n_map[key] = 1
        else:
            n_map[key] += 1

ans = 1
for k, v in p_map.items():
    a = int(k.split("_")[0])
    b = int(k.split("_")[1])
    n_num = 0
    key_a = "{}_{}".format(-b, a)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    res = 0
    res += pow(2, v, MOD)-1
    if n_num > 0:
        res += pow(2, n_num, MOD)-1
    res += 1
    ans *= res
    ans %= MOD

n_num = sum(n_map.values())
if n_num > 0:
    ans *= pow(2, n_num, MOD)
    ans %= MOD

res = 0
if p_zero_map > 0 and n_zero_map > 0:
    res = pow(2, p_zero_map, MOD)-1 + pow(2, n_zero_map, MOD)-1
    res += 1
    res %= MOD
elif p_zero_map > 0 and n_zero_map == 0:
    res = pow(2, p_zero_map, MOD)
elif p_zero_map == 0 and n_zero_map > 0:
    res = pow(2, n_zero_map, MOD)
if res > 0:
    ans *= res
    ans %= MOD


if z_map > 0:
    ans += z_map
ans -= 1
ans %= MOD
print(ans)

Solution (Python):
import math

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

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
bin_n = [2]
for i in range(len(bin(n)) - 3):
    temp = bin_n[-1]
    temp = temp ** 2
    temp %= mod
    bin_n.append(temp)
def beki2(n):
    num = bin(n)
    temp = 1
    for i in range(len(num) - 2):
        if num[-i-1] == "1":
            temp *= bin_n[i]
            temp %= mod
    return temp

ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (beki2(num2) + beki2(num3) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= beki2(n)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)

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

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

MOD = 10 ** 9 + 7

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

rest = N
zero = 0
zero_left, zero_right = 0, 0
tmp = []
for a, b in AB:
    if a == b == 0:
        zero += 1
        rest -= 1
    elif a == 0:
        zero_left += 1
    elif b == 0:
        zero_right += 1
    else:
        gcd_ab = gcd(abs(a), abs(b))
        a, b = a // gcd_ab,  b // gcd_ab
        if a < 0: a, b = -a, -b
        tmp.append([a, b])
AB = tmp

cnt = defaultdict(int)
for a, b in AB:
    cnt[(a, b)] += 1

answer = 1
answer *= pow(2, zero_left + zero_right, MOD) - (pow(2, zero_left, MOD) - 1) * (pow(2, zero_right, MOD) - 1)
answer %= MOD
rest -= zero_right + zero_left


check = defaultdict(int)
for a, b in AB:
    if b > 0 and check[(a, b)] == 0:
        check[(a, b)] = 1
        answer *= pow(2, cnt[(a, b)] + cnt[(b, -a)], MOD) - (pow(2, cnt[(a, b)], MOD) - 1) * (pow(2, cnt[(b, -a)], MOD) - 1) 
        answer %= MOD
        rest -= cnt[(a, b)] + cnt[(b, -a)]

answer *= pow(2, rest, MOD)
answer += zero - 1
answer %= MOD
print(answer)

Solution (Python):
from fractions import gcd
from collections import Counter
slope=Counter()
slope_zero=0
slope_inf=0
both_zero=0
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        both_zero+=1
    else:
        if a==0:
            slope_zero+=1
        elif b==0:
            slope_inf+=1
        else:
            sign=(a//abs(a))*(b//abs(b))
            a=abs(a)
            b=abs(b)
            gc=gcd(a,b)
            a//=gc
            b//=gc
            if sign==1:
                slope[(a,b)]+=1
            else:
                slope[(-a,b)]+=1
ans=1
mod=10**9+7
for a,b in slope.keys():
    if slope[(a,b)]>0:
        aa=-b
        bb=a
        if bb<0:
            bb*=-1
            aa*=-1
        if slope[(aa,bb)]>0:
            ans*=(pow(2,slope[(a,b)],mod)+pow(2,slope[(aa,bb)],mod)-1+mod)%mod
            ans%=mod
            slope[(aa,bb)]=0
        else:
            ans*=(pow(2,slope[(a,b)],mod))%mod
            ans%=mod
ans*=(pow(2,slope_zero,mod)+pow(2,slope_inf,mod)-1+mod)%mod
ans%=mod
ans+=both_zero
if ans>=mod:
    ans%=mod
print((ans-1+mod)%mod)

Solution (Python):
from math import gcd
import sys
input = sys.stdin.readline
n=int(input())
dic={}
z=0
mod=10**9+7
for i in range(n):
    a,b=map(int,input().split())
    if a==b==0:
        z+=1
        continue
    k=gcd(a,b)
    a//=k
    b//=k
    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 dic:
            dic[(a,b)][0]+=1
        else:
            dic[(a,b)]=[1,0]
    else:
        if (a,b) in dic:
            dic[(a,b)][1]+=1
        else:
            dic[(a,b)]=[0,1]
ans=1
for x in dic:
    v=dic[x]
    s = v[0]
    t = v[1]
    ans*=pow(2,s,mod)+pow(2,t,mod)-1
    ans%=mod
print((z-1+ans)%mod)

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a*b == 0:
        if a == 0 and b != 0:
            azero += 1
        elif a != 0 and b == 0:
            bzero += 1
        else:
            allzero += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a<0:
            a *= -1
            b *= -1
        before = cnd.get((a,b),False)
        if b > 0:
            check = cnd.get((b,-a),False)
        else:
            check = cnd.get((-b,a),False)
        if before:
            cnd[(a,b)] = [before[0]+1,before[1]]
        elif check:
            if b > 0:
                cnd[(b,-a)] = [check[0],check[1]+1]
            else:
                cnd[(-b,a)] = [check[0],check[1]+1]
        else:
            cnd[(a,b)] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1

for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]+2**item[1]-1)
        ans %= mod
print((ans*((2**noreg)%mod)-1+allzero)%mod)

Solution (Python):
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    
    
    a=fish[i][0]
    b=fish[i][1]
    g=ggcd(a,b)
    if g!=0:        
        a=a//g
        b=b//g
    
    if b<0:     
        a=-a
        b=-b
    if (a!=0)or(b!=0):          
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
        fishcomp.append([a, b])
    else:                       
        both0=both0+1


fishcomp=list(map(list,set(map(tuple,fishcomp))))   

length=N-both0                                      

sets=[]





for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]               
            sets.append([val1,val2])    
            length=length-(val2+val1)   

pro=1
for i in sets:
    
    
    
    
    
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p

print((pow(2,length,p)*pro-1+both0)%p)