Problem:
 Score: 500 points    Problem Statement  We have caught N sardines. The deliciousness and fragrantness of the i -th sardine is A_i and B_i , respectively.  We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.  The i -th and j -th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0 .  In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007 .      Constraints   All values in input are integers.  1 \leq N \leq 2 \times 10^5  -10^{18} \leq A_i, B_i \leq 10^{18}         Input  Input is given from Standard Input in the following format:  N  A_1  B_1  :  A_N  B_N       Output  Print the count modulo 1000000007 .        Sample Input 1 3
1 2
-1 1
2 -1      Sample Output 1 5  There are five ways to choose the set of sardines, as follows:   The 1 -st  The 1 -st and 2 -nd  The 2 -nd  The 2 -nd and 3 -rd  The 3 -rd        Sample Input 2 10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4      Sample Output 2 479

Solution (Python):
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter1 = defaultdict(int)
    counter2 = defaultdict(int)
    for _ in range(n):
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            zeroes += 1
            continue

        denominator = math.gcd(x, y)
        x, y = x // denominator, y // denominator

        if y < 0:
            
            x, y = -x, -y

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

    ans = 1
    for k, v in counter1.items():
        now = 1
        now += pow(2, v, mod) - 1
        now += pow(2, counter2[k], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  
    return ans % mod


if __name__ == '__main__':
    print(main())

Solution (Python):
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter = defaultdict(lambda: defaultdict(int))
    for _ in range(n):
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            zeroes += 1
            continue

        denominator = math.gcd(x, y)
        x, y = x // denominator, y // denominator

        if y < 0:
            
            x, y = -x, -y

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

    ans = 1
    for v in counter.values():
        now = 1
        now += pow(2, v[0], mod) - 1
        now += pow(2, v[1], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  
    return ans % mod


if __name__ == '__main__':
    print(main())

Solution (Python):
from collections import defaultdict
import math


def ggg(a, b):
    """規約分数を作る。n/0, 0/n は n=1,-1 にして返す。"""
    if a == b == 0:
        return 0, 0

    denominator = math.gcd(a, b)
    x, y = a // denominator, b // denominator
    return x, y


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter = defaultdict(lambda: defaultdict(int))
    for _ in range(n):
        a, b = [int(x) for x in input().split()]
        x, y = ggg(a, b)

        if x == y == 0:
            zeroes += 1
            continue
        if y < 0:
            
            x, y = -x, -y

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

    ans = 1
    for v in counter.values():
        now = 1
        now += pow(2, v[0], mod) - 1
        now += pow(2, v[1], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  
    return ans % mod


if __name__ == '__main__':
    print(main())

Solution (Python):
from collections import defaultdict
from math import gcd
N,*L = map(int, open(0).read().split())
dic = defaultdict(int)
ans = 0
MOD = 10**9+7
S = set()
for a,b in zip(*[iter(L)]*2):
  if a==0 and b==0:
    ans += 1
    continue
  g = gcd(a,b)
  if b>0:
    dic[(a//g,b//g)] += 1
    S.add((a//g,b//g))
  elif b<0:
    dic[(-a//g,-b//g)] += 1
    S.add((-a//g,-b//g))
  else:
    dic[(1,0)] += 1
    S.add((1,0))
m = 1
for a,b in S:
  if a<=0:
    if dic[(b,-a)]==0:
      m *= pow(2,dic[(a,b)],MOD)
      m %= MOD
      continue
  else:
    if dic[(-b,a)]==0:
      m *= pow(2,dic[(a,b)],MOD)
      m %= MOD
      continue
    c = pow(2,dic[(a,b)],MOD)+pow(2,dic[(-b,a)],MOD)-1
    m *= c
    m %= MOD
ans = (m-1+ans)%MOD
print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

def gcd(a, b):
    while b != 0:
        a, b = b, a % b

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    a, b = a // abs(gcd(a, b)), b // abs(gcd(a, b))

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    elif b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    elif (a < 0) ^ (b < 0):
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

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

Solution (Python):
import functools
MOD=10**9+7

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

def gcd(nums):
  return functools.reduce(euclid, nums)

n=int(input())
t=[]
for i in range(n):
    a,b=map(int,input().split())
    t.append((a,b))
z=0
y={}
for i in range(n):
    if t[i][0]==0 and t[i][1]==0:
        z+=1
    else:
        g=abs(gcd([t[i][0],t[i][1]]))
        if t[i][1]==0:
            a=(1,0)
        elif t[i][1]>0:
            a=(t[i][0]//g , t[i][1]//g)
        else:
            a=(-t[i][0]//g , -t[i][1]//g)
        if a not in y:
            y[a]=1
        else:
            y[a]+=1

cnt=0
x=1
for i in y:
    if (-i[1],i[0]) in y:
        x  *= pow(2,y[(-i[1],i[0])],MOD) + pow(2,y[(i[0],i[1])],MOD)-1
        cnt+= y[(-i[1],i[0])] + y[(i[0],i[1])]

ans = pow(2,n-z-cnt,MOD) *x -1
print((ans+z)%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):
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
d={}
mod=10**9+7
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y
z=0
for i in range(n):
    a,b=ab[i]
    if a==0 and b==0:
        z+=1
        continue
    if a==0:
        b=1
        y=(a,b)
        if y in d:
            d[y]+=1
        else:
            d[y]=1
        continue
    if b==0:
        a=1
        y=(a,b)
        if y in d:
            d[y]+=1
        else:
            d[y]=1
        continue
    x=gcd(a,b)
    a//=x
    b//=x
    if a<0:
        a*=-1
        b*=-1
    y=(a,b)
    if y in d:
        d[y]+=1
    else:
        d[y]=1
ans=1
re={}
for t,v in d.items():
    if t in re:
        continue
    a,b=t
    c=0
    if (b,-a) in d:
        c+=d[(b,-a)]
        re[(b,-a)]=1
    if (-b,a) in d:
        c+=d[(-b,a)]
        re[(-b,a)]=1
    ans*=(2**v-1+2**c-1+1)
    ans%=mod
ans-=1
ans+=z
ans%=mod
print(ans)

Solution (Python):
from math import gcd

N = int(input())

zero = 0
d = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    
    g = gcd(a, b)
    a //= g
    b //= g
    
    if b < 0:
        a = -a
        b = -b
    if b == 0 and a == -1:
        a = 1

    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        if (b, -a) in d:
            d[(b, -a)][1] += 1
        else:
            d[(b, -a)] = [0, 1]
MOD = 10**9+7
ans = 1
for (a, b), (k, l) in d.items():
    ans *= (pow(2, k, MOD)-1) + (pow(2, l, MOD)-1) + 1
    ans %= MOD
ans += zero
ans -= 1
print(ans%MOD)

Solution (Python):
from sys import stdin
from math import gcd
def main():
    
    readline=stdin.readline
    n=int(readline())
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=map(int,readline().split())

    mod=1000000007
    d=dict()
    d[(1,0)]=[0,0]
    ans=1
    zeros=0
    for i in range(n):
        up=a[i]
        down=b[i]
        if up==0 and down==0:
            zeros+=1
        else:
            g=gcd(up,down)
            up//=g
            down//=g
            if up==0:
                down=1
            elif down==0:
                up==1
            elif down<0:
                down*=-1
                up*=-1

            if up==1 and down==0:
                d[(1,0)][0]+=1
            elif up==0 and down==1:
                d[(1,0)][1]+=1
            elif up>0:
                if (up,down) not in d and (-down,up) not in d:
                    d[(up,down)]=[1,0]
                elif (up,down) in d:
                    d[(up,down)][0]+=1
                else:
                    d[(-down,up)][1]+=1
            elif up<0:
                if (up,down) not in d and (down,-up) not in d:
                    d[(up,down)]=[1,0]
                elif (up,down) in d:
                    d[(up,down)][0]+=1
                else:
                    d[(down,-up)][1]+=1

    for v in d.values():
        ans*=pow(2,v[0])+pow(2,v[1])-1
        ans%=mod
    ans-=1
    ans+=zeros
    ans%=mod
    print(ans)
    
if __name__=="__main__":
    main()

Solution (Python):


import sys
from collections import defaultdict
from math import gcd

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai * bi < 0
        if ai < 0:
            ai, bi = -ai ,-bi
        elif ai == 0:
            bi = -1
            t = 1

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    z1 = 0
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v, mod) + pow(2, v2, mod) - 1
            ans %= mod
        else:
            z1 += v

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        z1 += v
    ans *= pow(2, z1, mod)

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



if __name__ == "__main__":
    resolve()

Solution (Python):


import sys
from collections import defaultdict
from math import gcd

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai * bi < 0
        if ai < 0:
            ai, bi = -ai ,-bi
        elif ai == 0:
            bi = -1
            t = 1

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v, mod) + pow(2, v2, mod) - 1
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        ans *= pow(2, v, mod)
        ans %= mod

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



if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd

def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    x0,y0,xy0 = 0,0,0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0 and y==0:
            xy0 += 1
        elif x==0 and y!=0:
            x0 += 1
        elif y==0:
            y0 += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    ans = pow(2,x0,mod)+pow(2,y0,mod)-1
    other = N-x0-y0-xy0
    for k,v in dplus.items():
        ans *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans *= pow(2,other,mod)
    ans += xy0-1
    ans %= mod
    return ans
print(solve())

Solution (Python):
n = int(input())
zeros = 0
ab = {}
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    if a == b == 0:
        zeros += 1
    elif a == 0 or b == 0:
        if None not in ab:
            ab[None] = [0, 0]
        if a == 0:
            ab[None][0] += 1
        else:
            ab[None][1] += 1
    else:
        x = 1 if a * b > 0 else -1
        c = max(abs(a) * 10 ** 100 // abs(b) * x,
                abs(b) * 10 ** 100 // abs(a) * (-x))
        if c not in ab:
            ab[c] = [0, 0]
        if a * b > 0:
            ab[c][0] += 1
        else:
            ab[c][1] += 1
ans = 1
mod = 10 ** 9 + 7
for _, v in ab.items():
    ans *= pow(2, v[0], mod) + pow(2, v[1], mod) - 1
    ans %= mod
ans += zeros - 1
print(ans % mod)

Solution (Python):
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd

def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero,yzero,xyzero = 0,0,0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            if y==0:
                xyzero += 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    ans = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero-xyzero
    for k,v in dplus.items():
        ans *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans *= pow(2,other,mod)
    ans += xyzero-1
    ans %= mod
    return ans
print(solve())

Solution (Python):
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd
def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero = 0
    yzero = 0
    xyzero = 0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            if y==0:
                xyzero += 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    pattern = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero-xyzero
    for k,v in dplus.items():
        pattern *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans = pattern * pow(2,other,mod) - 1
    ans += xyzero
    ans %= mod
    return ans
print(solve())

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

Solution (Python):
import math
import collections

n = int(input())
iwashi = []
sub_ans = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        sub_ans += 1
    else:
        if b == 0:
            iwashi.append('1/0')
        elif b > 0:
            c = math.gcd(a, b)
            iwashi.append('{}/{}'.format(a//c, b//c))
        else:
            c = math.gcd(a, b)
            iwashi.append('{}/{}'.format(-a//c, -b//c))

iwashi = collections.Counter(iwashi)
k_list = list(iwashi.keys())
v = list(iwashi.values())


mod = 1000000007
ans = 1
for k in k_list:
    a = iwashi[k]
    if k == '1/0':
        anti_k = '0/1'
    elif k == '0/1':
        anti_k = '1/0'
    else:
        c, d = k.split('/')
        if int(c) < 0:
            anti_k = '{}/{}'.format(d, -int(c))
        else:
            anti_k = '{}/{}'.format(-int(d), c)

    b = iwashi[anti_k]
    if a*b != 0:
        ans *= (pow(2, a, mod) + pow(2, b, mod) -1)
    else:
        ans *= pow(2, a, mod)
    iwashi[k] = 0
    iwashi[anti_k] = 0
    
    ans %= mod
print((ans+sub_ans-1)%mod)

Solution (Python):
from math import gcd
mod_val = 1000000007
def simplify(A, B):
  a = A//gcd(A,B)
  b = B//gcd(A,B)
  if b<0:
    return (-a, -b)
  return (a, b)
n = int(input())
count_simple_fish = dict()
bad_fish = 0
for _ in range(n):
  A, B = map(int, input().split())
  if A == B == 0:
    bad_fish = (bad_fish + 1)%mod_val
    continue
  if B == 0:
    if (1, 0) in count_simple_fish:
      count_simple_fish[(1, 0)][1] += 1
    else:
      count_simple_fish[(1, 0)] = [0, 1]
  elif A == 0:
    if (1, 0) in count_simple_fish:
      count_simple_fish[(1, 0)][0] += 1
    else:
      count_simple_fish[(1, 0)] = [1, 0]
  else:
    a, b = simplify(A, B)
    if a>0:
      if (a, b) in count_simple_fish:
        count_simple_fish[(a, b)][1] += 1
      else:
        count_simple_fish[(a, b)] = [0, 1]
    else:
      if (b, -a) in count_simple_fish:
        count_simple_fish[(b, -a)][0] += 1
      else:
        count_simple_fish[(b, -a)] = [1, 0]
big_total = 1
for simple_fish, count_leftright in count_simple_fish.items():
  group_pair_combos = 1
  group_pair_combos = (group_pair_combos + pow(2, count_leftright[1], mod_val) - 1)%mod_val
  group_pair_combos = (group_pair_combos + pow(2, count_leftright[0], mod_val) - 1)%mod_val
  big_total = (big_total * group_pair_combos)%mod_val
big_total = (big_total + bad_fish - 1)%mod_val
print(big_total)

Solution (Python):
import sys
input=sys.stdin.buffer.readline
mod=10**9+7
n=int(input())
d={}
z=0
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f
        if x<0:x*=-1;y*=-1
        if x==0 and y<0:y=-y
        if (x,y)not in d:d[(x,y)]=1
        else:d[(x,y)]+=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)

Solution (Python):
mod=10**9+7
n=int(input())
from collections import defaultdict
d=defaultdict(int)
z=0
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f
        if x<0:x*=-1;y*=-1
        if x==0 and y<0:y=-y
        d[(x,y)]+=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)

Solution (Python):
import math
N=int(input())
A={}
mod=10**9+7
AZ,BZ,ZZ=0,0,0
for i in range(N):
  a,b=map(int, input().split())
  if a==b and a==0:
    ZZ+=1
  elif a==0:
    AZ+=1
    if (0,-1) not in A:
      A[(0,-1)]=1
    else:
      A[(0,-1)]+=1
  elif b==0:
    BZ+=1
    if (1,0) not in A:
      A[(1,0)]=1
    else:
      A[(1,0)]+=1
  else:
    if a<0:
      a*=-1
      b*=-1
    d=math.gcd(abs(a),abs(b))
    a//=d
    b//=d
    if (a,b) not in A:
      A[(a,b)]=1
    else:
      A[(a,b)]+=1
c=0
D=[]
for x,y in A:
  if (y,-x) in A:
    D.append((A[(x,y)],A[(y,-x)]))
    c+=A[(x,y)]+A[(y,-x)]
n=N-c-ZZ
p=pow(2,n,mod)
ans=p
for a,b in D:
  f=pow(2,a+b,mod)-(pow(2,a,mod)-1)*(pow(2,b,mod)-1)
  ans*=f
ans-=1
print((ans+ZZ)%mod)

Solution (Python):
import sys
import math
mod = 1000000007
 
n = int(sys.stdin.readline().rstrip())
ab = {}
for i in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().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 = -a
            b = -b
    ab.setdefault((a,b),0)
    ab[(a,b)]+=1
ans = 0
pairs=[]
s = set(ab.keys())
for i in ab.keys():
    a = i[0];b = i[1]
    if a == 0 and b == 0:
        ans = ab[(0,0)]
        n -= ans
    else:
        if (-b, a) in s:
            pairs.append([ab[(a,b)],ab[(-b,a)]])
select = 1
for pair in pairs:
    select*= (pow(2,pair[0],mod) + pow(2,pair[1],mod) -1)
    n -= (pair[0]+pair[1])
all_ans = (pow(2,n,mod) * select) % mod + ans -1
all_ans %= mod
print(all_ans)

Solution (Python):
from fractions import gcd

N=int(input())
d={}

MOD = 1000000007
nz=0
for _ in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        nz+=1
        
        continue
    elif a==0:
        p=(0,1)
    elif b==0:
        p=(1,0)
    else:
        c=gcd(a,b)
        a,b=a//c,b//c
        if b > 0:
            p=(a,b)
        else: 
            p=(-a,-b)
    
    
    if p in d:
        d[p]+=1
    else:
        d[p] = 1

ans=1

while len(d) > 0:
    p,np=d.popitem()
    if p==(1,0):
        q=(0,1)
    elif p==(0,1):
        q=(1,0)
    else:
        pa,pb=p
        if pa > 0:
            q=(-pb,pa)
        else: 
            q=(pb,-pa)
    if q in d:
        nq=d.pop(q)
    else:
        nq=0
    
    ans *= ((2**np + 2**nq - 1) % MOD)
    ans %= MOD

ans -= 1
ans += nz
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
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
from math import gcd
from collections import Counter
MOD = 10**9 + 7
def main():
    input = sys.stdin.readline
    N = int(input())
    V = []
    z = 0
    for _ in range(N):
        A, B = map(int, input().split())
        g = gcd(A, B)
        if g == 0:
            z += 1
            continue
        A, B = A // g, B // g
        if A == 0: V.append((0, 1))
        elif A < 0: V.append((-A, -B))
        else: V.append((A, B))
    C = Counter(V)
    ans = Mint(1)
    used = set()
    for k, V in C.items():
        if k in used: continue
        a, b = k
        v = (0, 1) if b == 0 else (b, -a) if b > 0 else (-b, a)
        t = Mint(1)
        t += pow(2, V, MOD) - 1
        t += pow(2, C[v], MOD) - 1
        ans *= t
        used.add(v)
    print(ans - 1 + z)

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self

    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self

    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj

    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self

    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self

    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj

    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque 


from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush




def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

class modint():
    def __init__(self,x,mod=1000000007): self.x, self.mod=x, mod
    def add(self,a): self.x=(self.x+a%self.mod)%self.mod
    def mul(self,c): self.x=(self.x*(c%self.mod))%self.mod
    def pow(self,p): self.x=pow(self.x,p,self.mod)
    def div(self,d):
        u,v,a,b=1,0,d,self.mod
        while b:
            t=a//b
            a-=t*b
            a,b,u,v=b,a,v,u-t*v
        if a!=1: print("not 素")
        self.x=(self.x*(u%self.mod))%self.mod

def main():
    mod = 1000000007
    

    N = int(input())
    
    
    
    

    d=dict()
    m=10**18+100
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        elif A==0:
            d[0]=d.get(0,0)+1
        else:
            sa=sb=1
            if A<0:
                sa=-1
                A*=-1
            if B<0:
                sb=-1
                B*=-1

            g=math.gcd(A,B)
            A=A//g
            B=B//g
            if sa==-1 and sb==-1:
                t=(A,B)
            elif sb==-1:
                t=(-A,B)
            else:
                t=(sa*A,sb*B)
            d[t]=d.get(t,0)+1
    
        
    
    ks=set(d.keys())
    alis=[]
    tot=modint(1)
    for i, k in enumerate(ks):
        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        if k==m:
            ik=0
        elif k==0:    
            ik=m
        elif k[0]<0:
            ik=(k[1],-k[0])
        else:
            ik=(-k[1],k[0])
        
        if ik in ks:
            d1,d2=d[k],d[ik]
            tot.mul((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)
            d[ik]=-1

        else:
            tot.mul(pow(2,d[k],mod))

    tot.add(-1)
    tot.add(d.get(-m,0))
    
    print(tot.x)




if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd

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

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
t = set(t)
if (0, 0) in t:
    t.remove((0, 0))

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    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))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)