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
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1

ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1) % DIV
ans %= DIV


allcnt = 0


for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1) % DIV
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += cnt

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV

ans += zeropair
print((ans - 1) % DIV)

Solution (Python):
from collections import defaultdict
from math import gcd
N = int(input())
mod = 10**9 + 7
D = defaultdict(int)
corner = 0
D[(0,1)]=0
D[(1,0)]=0
for i in range(N):
    x, y = map(int, input().split())
    if x*y != 0:
        x, y = x//gcd(x, y), y//gcd(x, y)
        if y > 0:
            D[(x, y)] += 1
        elif y < 0:
            D[(-x, -y)] += 1
    else:
        if x == 0 and y == 0:
            corner += 1
            continue
        else:
            if x == 0:
                D[(0, 1)] += 1
            elif y == 0:
                D[(1, 0)] += 1
ans = corner

c = 1
sub=[]
for x, y in D.keys():
    if x<0 and y>0:
        if not (y,-x) in D.keys():
            sub.append((y,-x))
for some in sub:
    D[some]=0

K=list(D.keys())
for x, y in K:
    if x > 0 and y > 0:
        a = D[(x, y)]
        b = D[(-y, x)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
    elif y == 0:
        a = D[(1, 0)]
        b = D[(0, 1)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
ans += c-1

print(ans % mod)

Solution (Python):
from collections import defaultdict
from math import gcd
N = int(input())
mod = 10**9 + 7
D = defaultdict(int)
corner = 0
D[(0,1)]=0
D[(1,0)]=0
for i in range(N):
    x, y = map(int, input().split())
    if x*y != 0:
        x, y = x//gcd(x, y), y//gcd(x, y)
        if y > 0:
            D[(x, y)] += 1
        elif y < 0:
            D[(-x, -y)] += 1
    else:
        if x == 0 and y == 0:
            corner += 1
            continue
        else:
            if x == 0:
                D[(0, 1)] += 1
            elif y == 0:
                D[(1, 0)] += 1
ans = corner

c = 1
sub=[]
for x, y in D.keys():
    if x<0 and y>0:
        if not (y,-x) in D.keys():
            sub.append((y,-x))
for some in sub:
    D[some]=0

K=list(D.keys())
for x, y in K:
    if x > 0 and y > 0:
        a = D[(x, y)]
        b = D[(-y, x)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
    elif y == 0:
        a = D[(1, 0)]
        b = D[(0, 1)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
ans += c-1

print(ans % mod)

Solution (Python):
from math import gcd
n=int(input())
mod = 1000000007
z=0
d={}
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    z+=1
    continue
  if a==0:
    d[(0,1)]=d.get((0,1),0)+1
    continue
  if b==0:
    d[(1,0)]=d.get((1,0),0)+1
    continue
  g = gcd(a,b)
  s = a//abs(a)
  a,b = (a//g)*s, (b//g)*s
  d[(a,b)]=d.get((a,b),0)+1

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

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

def input():
    return sys.stdin.readline().rstrip()

MOD = 10**9 + 7
n = int(input())
cnt = {}
zero_cnt = 0
ans = 1

for _ in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))

    a //= g
    b //= g

    rotate = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rotate += 1
    if (a, b) not in cnt:
        cnt[(a, b)] = [0, 0]

    cnt[(a, b)][rotate%2] += 1

for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

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

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

def input():
    return sys.stdin.readline().rstrip()

MOD = 10**9 + 7
n = int(input())
cnt = {}
zero_cnt = 0
ans = 1

for _ in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    if a == 0 or b == 0: g = max(abs(a), abs(b))
    a //= g
    b //= g

    rotate = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rotate += 1
    if (a, b) not in cnt:
        cnt[(a, b)] = [0, 0]

    cnt[(a, b)][rotate%2] += 1

for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

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

Solution (Python):
from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q) in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)])
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1)
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

Solution (Python):
from math import gcd

MOD = 10**9+7
n = int(input())
d = {}
zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1
    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1
ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD) - 1 
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

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

if __name__ == "__main__":
    main()

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

if __name__ == "__main__":
    main()

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

if __name__ == "__main__":
    main()

Solution (Python):
import math

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

MOD = 1000000007

dic1 = {}
a_zero = 0
b_zero = 0
both_zero = 0

for a, b in AB:
    if a == 0 and b != 0:
        a_zero += 1
    elif a != 0 and b == 0:
        b_zero += 1
    elif a == 0 and b == 0:
        both_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g

        if b < 0:
            a, b = -a, -b

        if (a, b) in dic1:
            dic1[(a, b)] += 1
        else:
            dic1[(a, b)] = 1

pair = []
used = set()

for key, val in dic1.items():
    if key in used:
        continue

    a, b = key
    used.add((a, b))
    cnt = 0

    if a < 0:
        c, d = -b, -a
    else:
        c, d = b, a

    if (-c, d) in dic1:
        cnt += dic1.get((-c, d), 0)
        used.add((-c, d))

    pair.append((val, cnt))


all_cnt = 1
for cnt1, cnt2 in pair:
    all_cnt *= pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    all_cnt %= MOD

all_cnt *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
all_cnt %= MOD

all_cnt += both_zero
all_cnt %= MOD

print((all_cnt - 1) % MOD)

Solution (Python):
import math

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

MOD = 1000000007

dic1 = {}
a_zero = 0
b_zero = 0
both_zero = 0

for a, b in AB:
    if a == 0 and b != 0:
        a_zero += 1
    elif a != 0 and b == 0:
        b_zero += 1
    elif a == 0 and b == 0:
        both_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g

        if b < 0:
            a, b = -a, -b

        if (a, b) in dic1:
            dic1[(a, b)] += 1
        else:
            dic1[(a, b)] = 1

pair = []
used = set()

for key, val in dic1.items():
    if key in used:
        continue

    a, b = key
    used.add((a, b))
    cnt = 0

    if a < 0:
        c, d = -b, -a
    else:
        c, d = b, a

    if (-c, d) in dic1:
        cnt += dic1.get((-c, d), 0)
        used.add((-c, d))

    pair.append((val, cnt))


all_cnt = 1
for cnt1, cnt2 in pair:
    all_cnt *= pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    all_cnt %= MOD

if a_zero != 0 or b_zero != 0:
    all_cnt *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
    all_cnt %= MOD

all_cnt += both_zero
all_cnt %= MOD

print((all_cnt - 1) % MOD)

Solution (Python):
import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

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

            continue
        
        if A == 0:
            B = -abs(B)
        if B == 0:
            A = abs(A)

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

    ans = 1

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

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


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



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

resolve()

Solution (Python):
import math
N=int(input())
MOD=10**9+7
fish={}
ans=1
a=0
b=0
w=0
for i in range(N):
    A,B=map(int,input().split())
    if A==0 and B==0:
        w+=1
    elif A==0:
        a+=1
    elif B==0:
        b+=1
    else:
        c=math.gcd(A,B)
        A=A//c
        B=B//c
        if B<0:
            A,B=-A,-B
        k=(A,B)
        if not k in fish:
            fish[k]=0
        fish[k]+=1
group=set()
for (p,q),v in fish.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))
for p,q in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    t=2**fish[p,q]
    if (invp,invq) in fish:
        t+=2**fish[invp,invq]-1
    ans=(ans*t)%MOD
ans*=2**a+2**b-1
ans=ans+w-1
print(ans%MOD)

Solution (Python):
from collections import Counter

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

MOD = 1000000007


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

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

if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

MOD = 1000000007

def inv(a, b):
    if a < 0:
        a, b = -a, -b
    return (-b, a)

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

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

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

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

        x //= g
        y //= g

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

        elif x == 0 and y < 0:
            y *= -1

        self.x = x
        self.y = y

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

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

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

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

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

        if x == 0 and y == 0:
            n -= 1
            zeros += 1
            continue

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

    MOD = 10 ** 9 + 7

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

    ans = 1
    tot = 0

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

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

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

    print(ans)
main()

Solution (Python):
n = int(input())
ab=[list(map(int,input().split())) for i in range(n)]
import math
from collections import defaultdict
d = defaultdict(int)
zerozero=0
azero=0
bzero=0
for tmp in ab:
    a,b=tmp

    if a==0 and b==0:
        zerozero+=1
        continue
    if a==0:
        azero+=1
        continue
    if b==0:
        bzero+=1
        continue

    absa=abs(a)
    absb=abs(b)
    gcd = math.gcd(absa,absb)

    absa//=gcd
    absb//=gcd

    if a*b >0:
        d[(absa,absb)]+=1
    else:
        d[(absa,-absb)]+=1

found = defaultdict(int)
d[(0,1)]=azero
d[(1,0)]=bzero

ans=1
mod=1000000007
for k in list(d.keys()):
    num = d[k]
    a,b=k

    if b>0:
        bad_ab = (b,-a)
    else:
        bad_ab = (-b,a)

    if found[k]!=0:
        continue
    found[bad_ab] = 1

    bm=d[bad_ab]

    if bm == 0:
        mul = pow(2,num,mod)
    if k==bad_ab:
        mul = num+1
    else:
        mul = pow(2,num,mod) + pow(2,bm,mod) -1
    ans*=mul

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

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
    plus_Ai_Bi = defaultdict(int)
    minus_Bj_Aj = defaultdict(int)
    zero_cnt = 0
    used = set()

    for i in range(N):
        a, b = MI()

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

        gcdab = gcd(abs(a), abs(b))
        a = a // gcdab
        b = b // gcdab

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

    
    
    ans = 1

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

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

            if a > 0 and b > 0:
                
                used.add((-b, a))
            elif a > 0 and b < 0:
                
                used.add((-b, a))
            elif a < 0 and b > 0:
                
                used.add((b, -a))
            elif a == 0:
                used.add((abs(b), a))
            elif b == 0:
                used.add((b, abs(a)))
            else:
                
                used.add((b, -a))
            
        else:
            ans *= pow(2, cnt1, MOD)
            ans %= MOD

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


if __name__ == '__main__':
    main()

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


def sign(x):
    if x < 0:
        return -1
    if x > 0:
        return +1
    return 0


def power(a, b, m):
    res = 1
    base = a
    while b:
        if b & 1:
            res = res * base % m
        base = base * base % m
        b = b >> 1
    return res


N = int(input())
M = 1000000007
cnt = defaultdict(int)
case00 = 0

for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:  
        case00 += 1
        continue

    s = sign(a) * sign(b)
    a, b = abs(a), abs(b)
    g = gcd(a, b)
    a, b = a // g, b // g
    cnt[s, a, b] += 1


ans = 1  
vis = set()
for (s, a, b) in cnt.keys():
    if (s, a, b) in vis:
        continue

    if (-s, b, a) in cnt:
        mul = 1  
        mul += power(2, cnt[s, a, b], M) - 1  
        mul += power(2, cnt[-s, b, a], M) - 1  
        ans = ans * (mul % M) % M
        vis.add((-s, b, a))
    else:
        ans = ans * power(2, cnt[s, a, b], M) % M

ans = (ans - 1 + M) % M  
ans = (ans + case00) % M  
print(ans)

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


    mod = 10 ** 9 + 7
    n = int(input())
    fishes = defaultdict(int)
    zero_zero = 0
    zero = 0
    inf = 0

    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zero_zero += 1

        elif a == 0:
            zero += 1

        elif b == 0:
            inf += 1

        else:
            div = gcd(a, b)
            a //= div
            b //= div
            if b < 0:
                a *= -1
                b *= -1
            key = (a, b)
            fishes[key] += 1


    def get_bad_pair(fish):
        a, b = fish
        if a < 0:
            a *= -1
            b *= -1
        return (-b, a)


    ans = 1
    counted_key = set()
    for fish_key, count in fishes.items():
        if fish_key in counted_key:
            continue

        bad_pair = get_bad_pair(fish_key)
        if bad_pair in fishes:
            pair_count = fishes[bad_pair]
            pattern = pow(2, count, mod) + pow(2, pair_count, mod) - 1
            counted_key.add(bad_pair)

        else:
            pattern = pow(2, count, mod)

        ans = ans * pattern % mod

    ans *= pow(2, zero, mod) + pow(2, inf, mod) - 1
    if zero_zero:
        ans += zero_zero

    ans -= 1
    print(ans % mod)

if __name__ == "__main__":
    main()

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

mod = 10 ** 9 + 7
n = int(input())
fishes = defaultdict(int)
zero_zero = 0
zero = 0
inf = 0

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero += 1

    elif a == 0:
        zero += 1

    elif b == 0:
        inf += 1

    else:
        div = gcd(a, b)
        a //= div
        b //= div
        if b < 0:
            a *= -1
            b *= -1
        key = (a, b)
        fishes[key] += 1


def get_bad_pair(fish):
    a, b = fish
    if a < 0:
        a *= -1
        b *= -1
    return (-b, a)


ans = 1
counted_key = set()
for fish_key, count in fishes.items():
    if fish_key in counted_key:
        continue

    bad_pair = get_bad_pair(fish_key)
    if bad_pair in fishes:
        pair_count = fishes[bad_pair]
        pattern = pow(2, count, mod) + pow(2, pair_count, mod) - 1
        counted_key.add(bad_pair)

    else:
        pattern = pow(2, count, mod)

    ans = ans * pattern % mod

ans *= pow(2, zero, mod) + pow(2, inf, mod) - 1
if zero_zero:
    ans += zero_zero

ans -= 1
print(ans % mod)

Solution (Python):
from collections import defaultdict
MOD = 10**9+7
from math import gcd


n = int(input())
ans = 1
C = defaultdict(int)
z = 0
r = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        r += 1
    elif b == 0:
        z += 1
    elif a == 0:
        C[0] += 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        C[(a, b)] += 1
D = tuple(C.items())
used = {0}
for c, v in D:
    if c in used:
        continue
    a, b = c
    if b > 0:
        d, e = b, -a
    else:
        d, e = -b, a
    ans *= pow(2, v, MOD)+pow(2, C[(d, e)], MOD)-1
    ans %= MOD
    used.add((d, e))
ans *= pow(2, C[0], MOD)+pow(2, z, MOD)-1
ans += r
ans -= 1
ans %= MOD
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp



class UnionFindEx:
    def __init__(self, size):
        
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    from fractions import Fraction
    N=ii()
    zero = 0
    d = defaultdict(lambda : [0, 0])
    for _ in range(N):
        x, y = mis()
        if x == y == 0:
            zero += 1
            continue
        if y < 0 or (y==0 and x < 0):
            x, y = -x, -y
        g = gcd(x, y)
        x //= g
        y //= g
        if x<=0:
            rot = True
            c = (y, -x)
        else:
            rot = False
            c = (x, y)
        d[c][rot] += 1
    
    N -= zero
    ans = 1
    for (q1, q2) in d.values():
        ans *= (pow(2, q1, N1097) - 1) + (pow(2, q2, N1097) - 1) + 1
        ans %= N1097
    ans -= 1
    ans %= N1097
    print(ans + zero)






main()

Solution (Python):
N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if a==0:
    if b==0:
      k=(0,0)
    else:
      k=(0,1)
  elif b==0:
    k=(1,0)
  else:
    if a<0:
      a,b=-a,-b
    if b<0:
      a,b=a//x,-((-b)//x)
    else:
      a,b=a//x,b//x
    k=(a,b)
  d[k]+=1

ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if a==b==0:
    continue
  if b<=0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans[0]*=pow(2,d[(a,b)])
  else:
    if ind[_k]==0:
      _ans.append(pow(2,d[(a,b)],MOD))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=pow(2,d[(a,b)],MOD)-1
ans=1
for a in _ans:
  ans=ans*a%MOD
print((d[(0,0)]+ans-1+MOD)%MOD)

Solution (Python):
import math

MOD = 10**9 + 7
n = int(input())
mp = {}
ans1 = 0


def process(lst):
	a = lst[0]
	b = lst[1]
	gcd = math.gcd(a, b)
	a //= gcd
	b //= gcd
	if b < 0:
		a *= -1
		b *= -1
	a = abs(a) if b == 0 else a
	b = abs(b) if a == 0 else b
	lst[0] = a
	lst[1] = b
	return lst


for _ in range(n):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		ans1 += 1
		continue

	a, b = process([a, b])
	mp.setdefault((a, b), 0)
	mp[(a, b)] += 1

	a, b = process([-b, a])
	y = mp.setdefault( (a, b), 0)

ans = 1

taken = {}

for a, b in mp:
	if taken.get((a, b), 0):
		continue
	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	x = mp.get( (a, b), 0)

	
	a, b = process([-b, a])
	y = mp.get( (a, b), 0)

	taken.setdefault((a, b), 0)
	taken[(a, b)] = 1

	
	ans = (ans * ( pow(2, x, MOD) + pow(2, y, MOD) - 1 + MOD) % MOD ) % MOD
	


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