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):
MOD = 10**9 + 7
P = 7 ** 21 + 52


def F(a, b):
    return (a * pow(b, P-2, P)) % P


def main():
    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    T = [[int(i) for i in input().split()] for j in range(N)]
    cnt_zero = [0, 0]  
    p = 0  
    cA = Counter()
    B = []
    used = set()
    for a, b in T:
        if a == 0 and b == 0:
            p += 1
        elif a == 0:
            cnt_zero[0] += 1
        elif b == 0:
            cnt_zero[1] += 1
        else:
            x = F(a, b)
            y = -F(b, a) % P
            cA[x] += 1
            if x not in used and y not in used:
                B.append((x, y))
                used.add(x)
                used.add(y)

    ans = 1
    ans *= pow(2, cnt_zero[0], MOD) - 1 + pow(2, cnt_zero[1], MOD) - 1 + 1
    for a, b in B:
        ans *= pow(2, cA[a], MOD) - 1 + pow(2, cA[b], MOD) - 1 + 1
        ans %= MOD
    print((ans + p - 1) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

def gcd(x, y):
    r = x % y
    while r:
        x, y, r = y, r, y%r
    return y
    
def main():
    n = int(input())
    mod = 1000000007
    p = defaultdict(lambda: 0)
    bad = dict()
    zeros = 0
    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zeros += 1
        else:
            if a == 0:
                p["0"] += 1
                bad["0"] = "INF"
            elif b == 0:
                p["INF"] += 1
                bad["INF"] = "0"
            else:
                g = gcd(b, a)
                a //= g
                b //= g
                sp = f"{a}_{b}"
                if b < 0:
                    b *= -1
                    a *= -1
                sm = f"{b}_{-a}"
                p[sp] += 1
                bad[sp] = sm
    done = set()
    good = 0
    ans = 1
    for key, num in p.items():
        if key in done:
            continue
        b = p.get(bad[key])
        done.add(bad[key])
        if b:
            ans *= pow(2, b, mod)+pow(2, num, mod)-1
            ans %= mod
        else:
            good += num
    ans *= pow(2, good, mod)
    ans += zeros
    ans -= 1
    ans %= mod
    print(ans)
        
        

if __name__ == "__main__":
    main()

Solution (Python):


from math import gcd
from collections import Counter
mod = 10**9 + 7
N,*AB = map(int,open(0).read().split())

def std(a,b):
    """
    a,bを既約にする
    """
    if a == 0:
        return(0,int(b!=0))
    g = gcd(a,b)
    a,b = a// g, b//g
    return(a,b) if a > 0 else (-a,-b)

C = Counter(std(a, b) for a, b in zip(*[iter(AB)] * 2))
def resolve():
    ans = 1
    cnt = 0
    for (a,b), v in C.items():
        if b > 0:
            if (b,-a) in C:
                ans *= -1 + pow(2,v,mod) + pow(2,C[(b,-a)], mod) 
                ans %= mod
            else:
                cnt += v
        elif (-b,a) not in C:
            cnt += v
    ans *= pow(2,cnt,mod)
    ans += C[(0,0)] - 1
    print(ans%mod)
resolve()

Solution (Python):
n = int(input())
MOD = 10**9+7
from math import gcd
zero = 0
cnt = {}
for i 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*=-1
        b*=-1
    if b==0 and a<0:
        a *= -1
    if a<=0:
        a,b = b,-a
        if (a,b) in cnt:
            cnt[(a,b)][0] += 1
        else:
            cnt[(a,b)] = [1,0]
    else:
        if (a,b) in cnt:
            cnt[(a,b)][1] += 1
        else:
            cnt[(a,b)] = [0,1]
ans = 1
for i,v in cnt.items():
    ans *= 1 + pow(2,v[0],MOD)-1 + pow(2,v[1],MOD)-1
    ans %= MOD
print((zero-1+ans)%MOD)

Solution (Python):


N = int(input().strip())
AB_list = [list(map(int, input().rstrip().split())) for i in range(N)]


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


fish = {}
cnt_A0_B0 = 0
cnt_A0_Bj = 0
cnt_Ai_B0 = 0
mod = 10**9 + 7


for a,b in AB_list:
    if a == b == 0:
        cnt_A0_B0 += 1
    
    elif (a == 0):
        cnt_A0_Bj += 1
    
    elif (b == 0):
        cnt_Ai_B0 += 1
    
    else:
        g = gcd( abs(a) , abs(b) )
        
        a //= g
        b //= g
        
        if a < 0:
            a *= (-1)
            b *= (-1)
        
        fish.setdefault( (a,b) , 0 )
        fish[ (a,b) ] += 1


ans = 1
used = set()


for key_a, key_b in fish:
    if (key_a, key_b) not in used:
        
        if key_b >= 0:
            key_reverse = (key_b, -key_a)
        else:
            key_reverse = (-key_b, key_a)
        
        if key_reverse in fish:
            ans *= ( (pow(2, fish[(key_a, key_b)], mod) - 1) + (pow(2, fish[key_reverse], mod) - 1) + 1 ) % mod
            ans %= mod
            
            used.add( key_reverse )
        
        else:
            ans *= ( pow(2, fish[(key_a, key_b)], mod) )
            ans %= mod



ans *= ( (2**cnt_A0_Bj - 1) + (2**cnt_Ai_B0 - 1) + 1 ) % mod
ans %= mod


ans += cnt_A0_B0
ans %= mod


ans -= 1

ans = (ans + mod) % mod
print(ans)

Solution (Python):
from math import gcd
MOD=10**9+7
n=int(input())
zero=0
cnt={}
for i 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*=-1
        b*=-1
    
    if b==0 and a<0:
        a*=-1
    
    
    
    if a<=0:
        a,b=b,-a
        if (a,b) in cnt:
            cnt[(a,b)][0]+=1
        else:
            cnt[(a,b)]=[1,0]
    else:
        if (a,b) in cnt:
            cnt[(a,b)][1]+=1
        else:
            cnt[(a,b)]=[0,1]
ans=1
for i,v in cnt.items():
    
    ans*= 1 + (pow(2,v[0],MOD) - 1) + (pow(2,v[1],MOD) - 1)
    ans%=MOD
print((zero-1+ans)%MOD)

Solution (Python):
from math import gcd
MOD = 1000_000_007

N = int(input())

Fish = {}
zeros = 0

for i in range(N):
  A, B = map(int,input().split()) 
  if A == 0 and B == 0:
    zeros += 1
    continue
  
  G = gcd(abs(A), abs(B))
  A, B = A // G, B // G
  if A < 0:
    A *= -1
    B *= -1
  elif A == 0:
    B = 1
    
  if (A, B) not in Fish:
    Fish[(A, B)] = 1
  else:
    Fish[(A, B)] += 1


done_set = set()

ans = 1
for (a, b) in Fish.keys():
  
  if b > 0:
    c = b
    d = -a
  elif b == 0:
    c = 0
    d = 1
  else: 
    c, d = -b, a
  
  
  
  if (a, b) in done_set or (c, d) in done_set: 
    continue
  
  
  if (c, d) not in Fish.keys():
    
    ans *= pow(2, Fish[(a,b)], MOD)
  else:
    ans *= (1 + (pow(2, Fish[(a,b)], MOD)-1) + (pow(2, Fish[(c,d)], MOD)-1))  
    done_set.add((c,d))
  ans %= MOD
  
  
  done_set.add((a,b))
  
ans += zeros
ans -= 1
ans %= MOD

print(ans)

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


def main():
    mod = 10 ** 9 + 7
    worst_iwashi_count = 0
    ans = 1
    d = defaultdict(int)
    N = int(input())
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            worst_iwashi_count += 1
        elif a == 0:
            d[(0, -1)] += 1
        elif b == 0:
            d[(1, 0)] += 1
        else:
            g = gcd(abs(a), abs(b))
            if a * b > 0:
                d[(abs(a // g), abs(b // g))] += 1
            else:
                d[(abs(a // g), -abs(b // g))] += 1
    done_set = set()
    for a, b in list(d):
        if (a, b) in done_set:
            continue
        x = d[(a, b)]
        done_set.add((a, b))
        if b >= 0:
            y = d[(b, -a)]
            done_set.add((b, -a))
        else:
            y = d[(-b, a)]
            done_set.add((-b, a))
        ans *= 2 ** x + 2 ** y - 1
        ans %= mod
    ans += worst_iwashi_count - 1
    print(ans % mod)


if __name__ == '__main__':
    main()

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

zero_zero_num = 0
fishes = defaultdict(int)
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero_num += 1
    elif a == 0:
        fishes[(0, -1)] += 1
    elif b == 0:
        fishes[(1, 0)] += 1
    else:
        g = gcd(a, b)
        a, b = a // g, b // g
        if (a > 0 and b > 0) or (a < 0 and b < 0):
            fishes[(abs(a), abs(b))] += 1
        else:
            a, b = (-a, -b) if a < 0 else (a, b)
            fishes[(a, b)] += 1


ans = 1
keys = list(fishes.keys())
visited = set()
for (kai, kbi) in keys:
    if kbi >= 0:
        kaj, kbj = kbi, -kai
    else:
        kaj, kbj = -kbi, kai

    if ((kai, kbi) in visited) or ((kaj, kbj) in visited):
        continue

    ans *= (1 + (pow(2, fishes[(kai, kbi)], MOD) - 1) + (pow(2, fishes[(kaj, kbj)], MOD) - 1))
    ans %= MOD
    visited.add((kai, kbi))
    visited.add((kaj, kbj))

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

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





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




from math import gcd
from collections import defaultdict

def main():
	n=II()
	mod=10**9+7

	ans=1
	cnt=0
	d=defaultdict(int)

	for _ in range(n):
		a,b=MI()
		if a==b==0:
			cnt+=1
		elif a==0:
			d[(1,0)]+=1
		elif b==0:
			d[(0,-1)]+=1
		else:
			g=gcd(abs(a),abs(b))
			if a*b>0:
				d[(abs(a//g),abs(b//g))]+=1
			else:
				d[(abs(a//g),-abs(b//g))]+=1


	s=set()

	for a,b in list(d):
		
		if (a,b) in s:
			continue
		if b>=0:
			x=d[(a,b)]
			y=d[(b,-a)]
			s.add((a,b))
			s.add((b,-a))
		else:
			x=d[(a,b)]
			y=d[(-b,a)]
			s.add((a,b))
			s.add((-b,a))
		ans*=2**x+2**y-1
		ans%=mod
	ans+=cnt-1
	print(ans%mod)

if __name__ == "__main__":
	main()

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





def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




from math import gcd
from collections import defaultdict

def main():
	n=II()
	mod=10**9+7

	ans=1
	cnt=0
	d=defaultdict(int)

	for _ in range(n):
		a,b=MI()
		if a==b==0:
			cnt+=1
		elif a==0:
			d[(1,0)]+=1
		elif b==0:
			d[(0,-1)]+=1
		else:
			g=gcd(abs(a),abs(b))
			if a*b>0:
				d[(abs(a//g),abs(b//g))]+=1
			else:
				d[(abs(a//g),-abs(b//g))]+=1


	s=set()

	for a,b in list(d):
		
		if (a,b) in s:
			continue
		if b>=0:
			x=d[(a,b)]
			y=d[(b,-a)]
			s.add((a,b))
			s.add((b,-a))
		else:
			x=d[(a,b)]
			y=d[(-b,a)]
			s.add((a,b))
			s.add((-b,a))
		ans*=2**x+2**y-1
		ans%=mod
	ans+=cnt-1
	print(ans%mod)

if __name__ == "__main__":
	main()

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

MOD = 10 ** 9 + 7

n = int(input())
d = defaultdict(int)
tmp = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        tmp += 1
    else:
        if b < 0 or (b == 0 and a <= 0):
            a = -a
            b = -b
        g = gcd(a, b)
        a = a // g
        b = b // g
        d[(a, b)] += 1
        if a <= 0:
            d[(b, -a)]
        else:
            d[(-b, a)]
ans = 1
for k, v in d.items():
    a, b = k
    if a <= 0:
        continue
    c = d[(-b, a)]
    ans *= pow(2, v) + pow(2, c) - 1
    ans %= MOD
print((ans + tmp - 1) % MOD)

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


MOD = 10 ** 9 + 7
N = int(input())
sar = defaultdict(int)
zero = 0
for s in sys.stdin.readlines():
    A, B = map(int, s.split())
    if (A, B) == (0, 0):
        zero += 1
    else:
        a = abs(A)
        b = abs(B)
        x = gcd(a, b)
        if a == 0:
            sar[(0, b // x, 1)] += 1
        elif b == 0:
            sar[(a // x, 0, 0)] += 1
        else:
            sar[(a // x, b // x, int((A >= 0) ^ (B >= 0)))] += 1

ans = 1
done = set()
for k in list(sar.keys()):
    a, b, c = k
    if (a, b, c) not in done:
        cnt = pow(2, sar[(a, b, c)], MOD) + pow(2, sar[(b, a, c ^ 1)], MOD) - 1
        ans *= cnt
        ans %= MOD
        done.add((a, b, c))
        done.add((b, a, c ^ 1))

ans -= 1
ans += zero

print(ans % MOD)

Solution (Python):
import numpy as np
dic = dict()
mod = 10 ** 9 + 7
p = 0

def reg(a, b):
	if a < 0 or (a == 0 and b < 0):
		a, b = -a, -b
	if b > 0:
		return 0, a, b
	else:
		return 1, -b, a

n = int(input())
for _ in range(n):
	a, b = map(int, input().split())
	if a == 0 and b == 0:
		p += 1
		continue
	ab = np.gcd(a, b)
	a, b = a//ab, b//ab
	idx, a, b = reg(a, b)
	k = (a, b)
	if k not in dic.keys():
		dic[k] = [0, 0]
	dic[k][idx] += 1

not_p = 1
for k in dic.keys():
	a, b = k
	pp, pm = dic[k]
	not_p *= (pow(2, pp, mod) + pow(2, pm, mod) - 1) % mod
	not_p %= mod

print((p + not_p -1) % mod)

Solution (Python):
N=int(input())
from collections import defaultdict
dic=defaultdict(int)
import math
mod=1000000007
for _ in range(N):
    A,B=map(int,input().split())
    if A<0:
        A,B=-A,-B
    if A==0:
        if B==0:
            dic[(0,0)]+=1
        else:
            dic[(0,-1)]+=1
    elif B==0:
        dic[(1,0)]+=1
    else:
        gcd=math.gcd(A,B)
        A,B=A//gcd,B//gcd
        dic[(A,B)]+=1

ans=1
N-=dic[(0,0)]
for k,v in dic.items():
    if k==(0,0):
        continue
    a,b=k
    if not (b,-a) in dic:
        continue
    v_dash=dic[(b,-a)]
    ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
    ans%=mod
    N-=v+v_dash
ans*=pow(2,N,mod)
ans+=dic[(0,0)]-1
ans%=mod
print(ans)

Solution (Python):
N=int(input())
from collections import defaultdict
dic=defaultdict(int)
import math
mod=1000000007
for _ in range(N):
    A,B=map(int,input().split())
    if A<0:
        A,B=-A,-B
    if A==0:
        if B==0:
            dic[(0,0)]+=1
        else:
            dic[(0,-1)]+=1
    elif B==0:
        dic[(1,0)]+=1
    else:
        gcd=math.gcd(A,B)
        A,B=A//gcd,B//gcd
        dic[(A,B)]+=1

ans=1
N-=dic[(0,0)]
for k,v in dic.items():
    if k==(0,0) or k==(0,1):
        continue
    a,b=k
    if not (b,-a) in dic:
        continue
    v_dash=dic[(b,-a)]
    ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
    ans%=mod
    N-=v+v_dash
ans*=pow(2,N,mod)
ans+=dic[(0,0)]-1
ans%=mod
print(ans)

Solution (Python):
N=int(input())
from collections import defaultdict
dic=defaultdict(int)
import math
mod=1000000007
for _ in range(N):
    A,B=map(int,input().split())
    if A<0:
        A,B=-A,-B
    if A==0:
        if B==0:
            dic[(0,0)]+=1
        else:
            dic[(0,1)]+=1
    elif B==0:
        dic[(1,0)]+=1
    else:
        gcd=math.gcd(A,B)
        A,B=A//gcd,B//gcd
        dic[(A,B)]+=1

ans=1
N-=dic[(0,0)]
for k,v in dic.items():
    if k==(0,0) or k==(0,1):
        continue
    if k==(1,0):
        if not (0,1) in dic:
            continue
        v_dash=dic[(0,1)]
        ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
        ans%=mod
        N-=v+v_dash
        continue
    a,b=k
    if not (b,-a) in dic:
        continue
    v_dash=dic[(b,-a)]
    ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
    ans%=mod
    N-=v+v_dash
ans*=pow(2,N,mod)
ans+=dic[(0,0)]-1
ans%=mod
print(ans)

Solution (Python):
N=int(input())
from collections import defaultdict
dic=defaultdict(int)
dic[(0,0)]=dic[(0,1)]=0
import math
mod=1000000007
for _ in range(N):
    A,B=map(int,input().split())
    if A<0:
        A,B=-A,-B
    if A==0:
        if B==0:
            dic[(0,0)]+=1
        else:
            dic[(0,1)]+=1
    elif B==0:
        dic[(1,0)]+=1
    else:
        gcd=math.gcd(A,B)
        A,B=A//gcd,B//gcd
        dic[(A,B)]+=1

ans=1
N-=dic[(0,0)]
for k,v in dic.items():
    if k==(0,0) or k==(0,1):
        continue
    if k==(1,0):
        v_dash=dic[(0,1)]
        ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
        ans%=mod
        N-=v+v_dash
        continue
    a,b=k
    if not (b,-a) in dic:
        continue
    v_dash=dic[(b,-a)]
    ans*=((pow(2,v,mod)-1)+(pow(2,v_dash,mod)-1)+1)
    ans%=mod
    N-=v+v_dash
ans*=pow(2,N,mod)
ans+=dic[(0,0)]-1
ans%=mod
print(ans)

Solution (Python):
from collections import defaultdict

mod=1000000007
def mpow2(n):
    ret=1
    while n>0:
        ret*=2
        ret%=mod
        n-=1
    return ret

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

shift=2**64
d=defaultdict(int)
n=int(input())
l=[]
cnt0=0
for i in range(n):
    a,b=map(int,input().split())
    if a==b==0:
        cnt0+=1
        continue
    elif a==0:
        b=1
    elif b==0:
        a=1
    else:
        g=gcd(a,b)
        a//=g
        b//=g
    l.append((a,b))
    d[a*shift+b]+=1
res=1
for p in l:
    a=p[0]
    b=p[1]
    c=d[a*shift+b]+d[-a*shift-b]
    if c==0:
        continue
    d[a*shift+b]=0
    d[-a*shift-b]=0
    a=-p[1]
    b=p[0]
    cc=d[a*shift+b]+d[-a*shift-b]
    d[a*shift+b]=0
    d[-a*shift-b]=0
    if cc==0:
        res*=mpow2(c)
        res%=mod
    else:
        res*=mpow2(c)+mpow2(cc)-1
        res%=mod
print((res+cnt0+mod-1)%mod)

Solution (Python):
from collections import defaultdict

def gcd(x, y):
    r = x % y
    while r:
        x, y, r = y, r, y%r
    return y
    
def main():
    n = int(input())
    al = defaultdict(lambda: 0)
    All = 0
    mod = 1000000007
    goods = dict()
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            All += 1
        elif b == 0:
            al["inf"] += 1
            goods["inf"] = "0"
        elif a == 0:
            al["0"] += 1
            goods["0"] = "inf"
        else:
            g = gcd(b, a)
            a_key = f"{a//g},{b//g}"
            if b//g < 0:
                good = f"{-b//g},{a//g}"
            else:
                good = f"{b//g},{-a//g}"
            goods[a_key] = good
            al[a_key] += 1
    ans = 1
    al = dict(al)
    done = set()
    ok = 0
    for k, v in al.items():
        if k in done:
            continue
        num = al.get(goods[k])
        done.add(goods[k])
        if num:
            ans *= pow(2, num, mod)+pow(2, v, mod)-1
            ans %= mod
        else:
            ok += v
    ans *= pow(2, ok, mod)
    ans += All - 1
    ans %= mod
    print(ans)
        
        
            
    

if __name__ == "__main__":
    main()

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

input = sys.stdin.readline
mod = 1000000007

n = int(input())

n2 = [1]
for _ in range(n):
    n2.append(n2[-1] * 2 % mod)

zero = 0
plus = defaultdict(int)
minus = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        plus[(1, 0)] += 1
    elif b == 0:
        minus[(1, 0)] += 1
    else:
        p = math.gcd(a, b)
        a //= p
        b //= p
        if a * b > 0:
            plus[(abs(a), abs(b))] += 1
        else:
            minus[(abs(b), abs(a))] += 1

n -= zero
ans = 1

for k, v in plus.items():
    if minus[k] > 0:
        ans *= (n2[v] + n2[minus[k]] - 1)
        ans %= mod
        n -= v + minus[k]

ans *= n2[n]
ans %= mod
ans += zero - 1
ans %= mod
print(ans)

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

N = int(input())
zerozero = 0
zero1 = 0
zero2 = 0
cnt = defaultdict(int)

for _ in range(N):
    A, B = map(int, input().split())
    
    if A==0 and B==0:
        zerozero += 1
    elif A==0:
        zero1 += 1
    elif B==0:
        zero2 += 1
    else:
        G = gcd(abs(A), abs(B))
        A //= G
        B //= G
        
        if (A<0 and B<0) or (A<0 and B>0):
            cnt[(-A, -B)] += 1
        else:
            cnt[(A, B)] += 1

ans = 1
MOD = 10**9+7
checked = set()

for k, v in cnt.items():
    if k in checked:
        continue
    
    if k[0]>0 and k[1]>0:
        k2 = (k[1], -k[0])
    else:
        k2 = (-k[1], k[0])
    
    if k2 in cnt:
        v2 = cnt[k2]
        ans *= pow(2, v, MOD)+pow(2, v2, MOD)-1
        ans %= MOD
        checked.add(k2)
    else:
        ans *= pow(2, v, MOD)
        ans %= MOD

ans *= pow(2, zero1, MOD)+pow(2, zero2, MOD)-1
ans %= MOD
ans += zerozero
ans %= MOD
print((ans-1)%MOD)

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

read = sys.stdin.read
readline = sys.stdin.readline

N, *AB = map(int, read().split())
mod = 10 ** 9 + 7

ab = []
zero = 0
for A, B in zip(*[iter(AB)] * 2):
    if A == 0 and B == 0:
        zero += 1
        continue
    if A == 0:
        B = -1
    elif B == 0:
        A = 1
    else:
        g = gcd(A, B)
        A //= g
        B //= g
    if A < 0:
        A, B = -A, -B
    ab.append((A, B))

cnt = Counter(ab)
answer = 1
checked = set()
ok = 0

for (i, j), n in cnt.items():
    if (i, j) in checked:
        continue
    if j < 0:
        c, d = -j, i
    else:
        c, d = j, -i
    if (c, d) in cnt:
        m = cnt[(c, d)]
        answer = (answer * (pow(2, n, mod) + pow(2, m, mod) - 1)) % mod
        checked.add((c, d))
    else:
        ok += n

answer *= pow(2, ok, mod)
answer -= 1
answer += zero
answer %= mod
print(answer)

Solution (Python):
from math import gcd

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

m = 1000000007

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

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, m) + pow(2, k + l, m) - 1
    result %= m
result += d[0][0] - 1
result %= m
print(result)

Solution (Python):
n=int(input())
mod=1000000007
import math
ab=[]
n0=0
for i in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        n0+=1
        continue
    if b==0:
        ab.append( (1,0) )
    elif a==0:
        ab.append( (0,1) )
    else:
        gc = math.gcd(a,b)*b//abs(b)
        ab.append( (a//gc,b//gc) )
n_eff = n-n0

from collections import Counter
c=Counter(ab)

pairs =[]
for cc in c:
    n_dual = c[(-cc[1],cc[0])]
    if n_dual>0:

        pairs.append( (c[cc],n_dual) )

ans=1
for p in pairs:
    ans = ans*(pow(2,p[0],mod)+pow(2,p[1],mod)-1 ) %mod

amari = n_eff - sum(sum(p) for p in pairs)

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

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

Solution (Python):
from collections import Counter
import math
MOD=10**9+7
N=int(input())
li=[]
zcnt=0
az,bz=0,0
for i in range(N):
    A,B=map(int,input().split())
    if A==0 and B==0:
        zcnt+=1
        continue
    if A!=0 and B==0:
        bz+=1
        continue
    elif A==0 and B!=0:
        az+=1
        continue
    g=math.gcd(A,B)
    if A<0 and B<0:
        li.append((-(A//g),-(B//g)))
    elif A<0 and B>0:
        li.append((-(A//g),-(B//g)))
    else:
        li.append((A//g,B//g))
c=Counter(li)
dic={}
ans=(pow(2,az,MOD)+pow(2,bz,MOD)-1+MOD)%MOD
for a,b in c.keys():
    if (a,b) in dic:
        continue
    l,r=(-b,a),(b,-a)
    s=c.get(l,0)+c.get(r,0)
    dic[l],dic[r]=1,1
    res=(pow(2,c[(a,b)],MOD)+pow(2,s,MOD)-1+MOD)%MOD
    ans=(ans*res)%MOD
print((ans-1+zcnt)%MOD)

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

N = int(input())
d = {}
MOD = 10**9+7
zall = 0

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

    if A==0 and B==0:
        zall += 1
    else:
        if A and B:
            if A<0 and B<0:
                A *= -1
                B *= -1
            elif A<0 and B>0:
                A *= -1
                B *= -1

            g = gcd(A, B)
            A //= g
            B //= g
        elif A==0:
            B = 1
        elif B==0:
            A = 1
        
        if (A, B) in d:
            d[(A, B)] += 1
        else:
            d[(A, B)] = 1

ans = 1
used = defaultdict(int)

for (i, j), v in d.items():
    if used[(i, j)]:continue
    used[(i, j)] = 1
    buf = 0

    if j>0:
        if (j, -i) in d:
            used[(j, -i)] = 1
            buf = d[(j, -i)]
        else:
            buf = 0
    else:
        if (-j, i) in d:
            used[(-j, i)] = 1
            buf = d[(-j, i)]
        else:
            buf = 0

    ans *= (pow(2, buf, MOD)+pow(2, v, MOD)-1)
    ans %= MOD

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

Solution (Python):
import sys
import math


stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  


N = ni()

AB_array = [na() for _ in range(N)]



plus_dic = {}
minus_dic = {}
ans = 1
fish_count = 0
mod = 10 ** 9 + 7
zero_count = 0
for ab in AB_array:
    a, b = ab
    if a == 0 and b == 0:
        zero_count += 1
        continue
    fish_count += 1
    if a == 0:
        vec = (0, 1)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
        continue
    elif b == 0:
        vec = (1, 0)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1
        continue
    c = math.gcd(a, b)
    a = a // c
    b = b // c
    if a < 0:
        a *= -1
        b *= -1
    if b > 0:
        vec = (a, b)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
    else:
        vec = (a, b)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1




for k, vp in plus_dic.items():
    x, y = k
    if (y, -x) in minus_dic:
        vm = minus_dic[(y, -x)]
        ans = ans * (pow(2, vp, mod) + pow(2, vm, mod) - 1) % mod
        fish_count -= (vp + vm)

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

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

Solution (Python):

from math import gcd
from collections import defaultdict
mod = 10**9+7
n = int(input())
mp = defaultdict(lambda: [0, 0])
zero_zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    rot_cnt = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        
        
        rot_cnt += 1
    mp[(a, b)][rot_cnt % 2] += 1
ans = 1
for s, t in mp.values():
    now = (pow(2, s, mod) + pow(2, t, mod) - 1) % mod
    ans = (ans * now) % mod
ans = (ans - 1 + zero_zero) % mod
print(ans)

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

    mod = 1000000007

    N = int(input())

    zero_pair = 0
    zero_a = 0
    zero_b = 0
    pair_plus = defaultdict(int)
    pair_minus = defaultdict(int)
    for a, b in [tuple(map(int, input().split())) for _ in range(N)]:
        if a == 0 and b == 0:
            zero_pair += 1
            continue
        if a == 0:
            zero_a += 1
            continue
        if b == 0:
            zero_b += 1
            continue

        abs_a = abs(a)
        abs_b = abs(b)
        g = math.gcd(abs_a, abs_b)
        abs_a = abs_a//g
        abs_b = abs_b//g
        if a * b > 0:
            pair_plus[(abs_a, abs_b)] += 1
        else:
            pair_minus[(abs_a, abs_b)] += 1

    ans = 1
    ans *= (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) % mod
    ans %= mod

    count_all = 0
    for item in pair_plus.items():
        a, b = item[0]
        cnt = item[1]
        if (b,a) in pair_minus:
            ans *= (pow(2, cnt, mod) + pow(2, pair_minus[(b,a)]) - 1) % mod
            ans %= mod
            del pair_minus[(b, a)]
        else:
            count_all += cnt

    for val in pair_minus.values():
        count_all += val

    ans = (ans * pow(2, count_all, mod)) % mod
    ans += zero_pair
    print((ans - 1) % mod)

main()

Solution (Python):
from math import gcd
from collections import defaultdict
mod = 10**9+7
n = int(input())
mp = defaultdict(lambda: [0, 0])
zerozero = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zerozero += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    rot_cnt = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rot_cnt += 1
    mp[(a,b)][rot_cnt%2] += 1
ans = 1
for s, t in mp.values():
    now = (pow(2, s, mod) + pow(2, t, mod) - 1) % mod
    ans = (ans * now) % mod
ans = (ans - 1 + zerozero) % mod 
print(ans)

Solution (Python):
from math import gcd
from collections import defaultdict
mod = 10**9+7
n = int(input())
mp = defaultdict(lambda: [0, 0])
zerozero = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zerozero += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    rot_cnt = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rot_cnt += 1
    mp[(a,b)][rot_cnt%2] += 1
ans = 1
for s, t in mp.values():
    now = (pow(2, s, mod) + pow(2, t, mod) - 1) % mod
    ans = (ans * now) % mod
ans = (ans - 1 + zerozero) % mod 
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7
from math import gcd
from collections import Counter
from collections import defaultdict
used = defaultdict(list)

n = int(input())

ctr = Counter()
az = bz = zz = 0
for i in range(n):
    a, b = map(int, input().split())
    if a==b==0:
        zz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
    else:
        g = gcd(a,b)
        a,b = a//g, b//g
        if b < 0:
            a*=-1
            b*=-1
        ctr[(a,b)]+=1
        used[(a,b)]=False

ans = 1


for (a1,b1),v1 in ctr.items():
    if used[(a1,b1)]:
        continue
    a2,b2=-b1,a1
    if b2 < 0:
        b2*=-1
        a2*=-1
    v2 = ctr[(a2,b2)]

    r = (pow(2,v1,p)+pow(2,v2,p)-1)%p
    ans*=r
    ans%=p
    used[(a1,b1)]=True
    used[(a2,b2)]=True


r = (pow(2,az,p)+pow(2,bz,p)-1)%p
ans*=r
ans%=p

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