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 = 1000000007
n = int(input())

ab00 = 0
abx0 = 0
ab0x = 0
p = []
m = []

from math import gcd
for _ in range(n):
    i, j = map(int, input().split())
    if i == 0:
        if j == 0:
            ab00 += 1
        else:
            ab0x += 1
        continue
    elif j == 0:
        abx0 += 1
        continue
    k = gcd(i, j)
    i //= k
    j //= k
    if i > 0:
        if j > 0:
            p.append((i, j))
        else:
            m.append((-j, i))
    elif j > 0:
        m.append((j, -i))
    else:
        p.append((-i, -j))

m.sort()
p.sort()

ans = pow(2, ab0x, mod) + pow(2, abx0, mod) - 1
ans %= mod

mi = 0
pi = 0
while mi < len(m) and pi < len(p):
    if m[mi] == p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] == m[mi-1]:
            mi += 1
            mnum += 1
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] == p[pi-1]:
            pi += 1
            pnum += 1
        ans *= pow(2, mnum, mod) + pow(2, pnum, mod) - 1
        ans %= mod

    elif m[mi] < p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] < p[pi]:
            mi += 1
            mnum += 1
        ans *= pow(2, mnum, mod)
        ans %= mod
    
    else:
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] < m[mi]:
            pi += 1
            pnum += 1
        ans *= pow(2, pnum, mod)
        ans %= mod

ans *= pow(2, len(p) - pi, mod)
ans %= mod
ans *= pow(2, len(m) - mi, mod)
ans %= mod
ans = (ans - 1 + ab00) % mod
print(ans)

Solution (Python):
mod = 1000000007
n = int(input())

ab00 = 0
abx0 = 0
ab0x = 0
p = []
m = []

from math import gcd
for _ in range(n):
    i, j = map(int, input().split())
    if i == 0:
        if j == 0:
            ab00 += 1
        else:
            ab0x += 1
        continue
    elif j == 0:
        abx0 += 1
        continue
    k = gcd(i, j)
    i //= k
    j //= k
    if i > 0:
        if j > 0:
            p.append((i, j))
        else:
            m.append((-j, i))
    elif j > 0:
        m.append((j, -i))
    else:
        p.append((-i, -j))

m.sort()
p.sort()

ans = pow(2, ab0x, mod) + pow(2, abx0, mod) - 1
ans %= mod

mi = 0
pi = 0
while mi < len(m) and pi < len(p):
    if m[mi] == p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] == m[mi-1]:
            mi += 1
            mnum += 1
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] == p[pi-1]:
            pi += 1
            pnum += 1
        ans *= pow(2, mnum, mod) + pow(2, pnum, mod) - 1
        ans %= mod

    elif m[mi] < p[pi]:
        mi += 1
        mnum = 1
        while mi < len(m) and m[mi] < p[pi]:
            mi += 1
            mnum += 1
        ans *= pow(2, mnum, mod)
        ans %= mod
    
    else:
        pi += 1
        pnum = 1
        while pi < len(p) and p[pi] < m[mi]:
            pi += 1
            pnum += 1
        ans *= pow(2, pnum, mod)
        ans %= mod

ans *= pow(2, len(p) - pi, mod)
ans %= mod
ans *= pow(2, len(m) - mi, mod)
ans %= mod
ans = (ans - 1 + ab00) % mod
print(ans)

Solution (Python):
import math
from collections import deque

N = int(input())

a = []
b = []
for i in range(N):
    i1, i2 = map(int, input().split())
    g = math.gcd(i1,i2)
    if g == 0:
        a.append(i1)
        b.append(i2)
        continue
    x = i1 // g
    y = i2 // g
    if x < 0:
        x = - x
        y = - y 
    a.append(x)
    b.append(y)

P = {}
for i in range(N):
    if b[i] < 0:
        tmp = b[i]
        b[i] = a[i]
        a[i] = - tmp
        sgn = 1
    elif a[i] == 0 and b[i] != 0:
        a[i] = b[i]
        b[i] = 0
        sgn = 1
    else :
        sgn = 0

    if (a[i],b[i]) in P:
        P[(a[i],b[i])][sgn]=P[(a[i],b[i])][sgn] + 1
    elif sgn == 0 :
        P[(a[i],b[i])]=[1,0]
    else :
        P[(a[i],b[i])]=[0,1]


MOD = 1000000007
a1 = 1 
ans0=0
for k in P:
    if k == (0,0):
        ans0 = P[k][0]
    else:
        a1 = a1*(pow(2,P[k][0],MOD)+pow(2,P[k][1],MOD) - 1) % MOD

if ans0 != 0:
    ans = ans0 + a1 -1
else:
    ans = a1 -1
print(ans%MOD)

Solution (Python):
import math
from collections import Counter

MOD = 10**9 + 7
N = int(input())

I = []
zz = 0
sz = 0
tz = 0
for _ in range(N):
    a,b = map(int, input().split())

    
    if a == 0 and b == 0:
        zz += 1
        continue
    
    if a == 0:
        sz += 1
        continue
    
    if b == 0:
        tz += 1
        continue

    gcd = math.gcd(a, b)
    if b < 0:
        a *= -1
        b *= -1
    I.append((a//gcd,b//gcd))

S = []
T = []
C = Counter(I)
for a, b in C.keys():
    if a > 0:
        S.append(C[(a,b)])
        T.append(C[(-b,a)])
    else:
        if C[(b,-a)] == 0:
            S.append(0)
            T.append(C[(a,b)])

ans = 1
ans *= 2**sz + 2**tz - 1
ans %= MOD
for i in range(len(S)):
    ans *= 2**S[i] + 2**T[i] - 1
    ans %= MOD
ans += zz  
ans -= 1
print(ans % MOD)

Solution (Python):
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i 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

ans = 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):

import math
MOD = 10**9+7
N = int(input())


    
d = dict()
'''
def bisection(a, n, p):
    
    bin_str = format(n, 'b')
    res = 1
    tmp = a
    for i in range(1, len(bin_str)+1):
        if(bin_str[(-1)*i] == '1'):
            res = res * tmp % p
        tmp = tmp * tmp % p
    return res
'''
d['a'] = 0
d['b'] = 0
d['c'] = 0

for i in range(N):
    
    
    a,b=map(int,input().split())
    
    if(a == 0):
        
        if(b == 0):
            d['c'] += 1
        else:
            d['b'] += 1
    
    elif(b == 0):
        d['a'] += 1
    else:
        
        g = math.gcd(a, b)
        
        
        a = a//g
        b = b//g
        if(a<0):
            p = (-1*a, -1*b)
        else:
            p = (a, b)
        if p in d:
            d[p] += 1
        else:
            d[p] = 1
    


a = d.pop('a')
b = d.pop('b')


    
    
    
    
res = pow(2, a, MOD) + pow(2, b, MOD) - 1
res %= MOD


    
    
    

    
    
    
c = d.pop('c')





while len(d) > 0:
    s, v = d.popitem()
    if(s[1] < 0):
        opposite = (-1*s[1], s[0])
    else:
        opposite = (s[1], -1*s[0])
    if opposite in d:
        t = d.pop(opposite)
        
        
        
        
        res *= pow(2, v, MOD) + pow(2, t, MOD) - 1
        res %= MOD
    else:
        
        
        
        res *= pow(2, v, MOD)
        res %= MOD
    


res += c
res = (res + MOD - 1) % MOD

print(res)

Solution (Python):
from math import gcd
n=int(input())
mod=10**9+7
d1=dict()
d2=dict()
zero=0
zeroa=0
zerob=0
for _ in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0 and b!=0:
        zeroa+=1
    elif a!=0 and b==0:
        zerob+=1
    else:
        g=gcd(abs(a),abs(b))
        na=a//g
        nb=b//g
        if na<0:
            na=-na
            nb=-nb
        if (na,nb) not in d1 and (na,nb) not in d2:
            d1[(na,nb)]=1
            d2[(-nb,na)]=0
            d2[(nb,-na)]=0
        elif (na,nb) in d1:
            d1[(na,nb)]+=1
        else:
            d2[(na,nb)]+=1


d1=list(d1.items())
ans=pow(2,zeroa,mod)+pow(2,zerob,mod)-1
ans%=mod
for (a,b),cnt1 in d1:
  cnt2=0
  cnt2+=d2[(-b,a)]
  cnt2+=d2[(b,-a)]
  ans*=pow(2,cnt1,mod)+pow(2,cnt2,mod)-1
  ans%=mod
ans+=zero
ans=(ans+mod-1)%mod
print(ans)

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


def select_num(a, b, mod=1000000007):
    sum = pow(2, a, mod) + pow(2, b, mod) - 1
    return sum % mod


def dict_count(d, a, b):
    this = a / b
    pair = b / a
    if not d.get(this, False):
        d[this] = {"num": 0, "pair": pair}
    d[this]["num"] += 1


def main():
    MOD = 1000000007
    n = int(input())

    d = defaultdict(lambda: [0] * 2)
    zero = 0
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if a == b == 0:
                n -= 1
                zero += 1
            elif a == 0:
                d[0][True] += 1
            elif b == 0:
                d[0][False] += 1

        else:
            gcd = math.gcd(a, b)
            a //= gcd
            b //= gcd

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

            rot = False
            if a < 0:
                b, a = -a, b
                rot = True
            d[(a, b)][rot] += 1

    ans = 1
    for k, v in d.items():
        ans *= select_num(v[0], v[1], MOD)
        ans %= MOD

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


if __name__ == '__main__':
    main()

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

MOD=10**9+7

n=int(input())
L=[]
for i in range(n):
	l=list(map(int,input().split()))
	L.append(l)

def kikaku(a,b):
	g=gcd(a,b)
	a//=g
	b//=g
	if a<0:
		return -a,-b
	return a,b

Dpos=defaultdict(int)

Dneg=defaultdict(int)

zerozero=0
azero=0
bzero=0

for l in L:
	a=l[0]
	b=l[1]
	if a==b==0:
		zerozero+=1
		continue
	if a==0:
		azero+=1
		continue
	if b==0:
		bzero+=1
		continue
	a,b=kikaku(a,b)
	if b>0:
		Dpos[(a,b)]+=1
	else:
		Dneg[(a,-b)]+=1
		Dpos[(-b,a)]+=0

r=1
for k,v in Dpos.items():
	a,b=k
	j=Dneg[(b,a)]
	r*=pow(2,v,MOD)+pow(2,j,MOD)-1
	
	r%=MOD

r*=pow(2,azero,MOD)+pow(2,bzero,MOD)-1
r%=MOD
r-=1
r%=MOD

ans=r+zerozero
ans%=MOD
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect
from fractions import Fraction
from collections import defaultdict

def is_same_sign(a, b):
    if a > 0 and b > 0:
        return True
    if a < 0 and b < 0:
        return True
    return False

def fraction_taple(a, b):
    g = math.gcd(a, b)
    if is_same_sign(a, b):
        s = 1
    else:
        s = -1
    a = abs(a) // g
    b = abs(b) // g
    return (s, a, b)

def mode(a, b):
    
    if a == 0 and b == 0:
        return 0, 0
    if a == 0:
        return 'ab', 0
    if b == 0:
        return 'ab', 1
    x = fraction_taple(a, b)
    y = fraction_taple(-1 * b, a)
    if x > y:
        return x, 0
    else:
        return y, 1

MOD = 1000000007

if __name__ == '__main__':

    n = int(input())

    d = defaultdict(lambda: [0, 0])
    zero = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        dkey, akey = mode(a, b)
        if dkey == 0:
            zero += 1
        else:
            d[dkey][akey] += 1
    
    

    ans = 1
    for pair in d.values():
        tmp = pow(2, pair[0], MOD) - 1 + pow(2, pair[1], MOD) - 1 + 1
        ans *= tmp
    ans += zero - 1
    ans %= MOD
    
    print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect
from fractions import Fraction
from collections import defaultdict

def is_same_sign(a, b):
    if a > 0 and b > 0:
        return True
    if a < 0 and b < 0:
        return True
    return False

def fraction_taple(a, b):
    g = math.gcd(a, b)
    if is_same_sign(a, b):
        s = 1
    else:
        s = -1
    a = abs(a) // g
    b = abs(b) // g
    return (s, a, b)

def mode(a, b):
    
    if a == 0 and b == 0:
        return 0, 0
    if a == 0:
        return 'ab', 0
    if b == 0:
        return 'ab', 1
    x = fraction_taple(a, b)
    y = fraction_taple(-1 * b, a)
    if x > y:
        return x, 0
    else:
        return y, 1

MOD = 1000000007

if __name__ == '__main__':

    n = int(input())

    d = defaultdict(lambda: [0, 0])
    zero = 0
    for _ in range(n):
        a, b = list(map(int, input().split()))
        dkey, akey = mode(a, b)
        if dkey == 0:
            zero += 1
        else:
            d[dkey][akey] += 1
    
    

    ans = 1
    for pair in d.values():
        tmp = pow(2, pair[0], MOD) - 1 + pow(2, pair[1], MOD) - 1 + 1
        ans *= tmp
    ans += zero - 1
    ans %= MOD
    
    print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[本番中]
全体から引くことを考えていたが, 考えることが多く解けなかった

[解説AC]
Ai=0かつBi=0は他の全てと仲が悪いので, 単体で用いるしかない(最後に足す)

Ai*Aj + Bi*Bj = 0の式から内積が思い浮かぶ
仲が悪いペアはAi*Bi >= 0 と Aj*Bj <= 0の場合しかないことがわかる
X: Ai*Bi > 0の場合の(|Ai|, |Bi|)の数
y: Ai*Bi < 0の場合の(|Bi|, |Ai|)の数とすると, 
xとyで同じ(A, B)のペアがあると仲が悪い可能性がある
この場合, 以下の3通りのみ使用できる
xのみで使用(少なくとも1つ) or yのみで使用(少なくとも1つ) or xもyも使用しない
つまり, 2**x[(A, B)] - 1 + 2**y[(A, B)] -1 + 1 = 2**x[(A, B)] + 2**y[(A, B)] - 1
これらの積をとり, 最後に全て使用しなかった場合の1を引いた値が答え(最後に(A,B)=(0,0)を足す必要がある)
"""

n = I()
ab = [LI() for _ in range(n)]

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]

fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = defaultdict(lambda : 0)
y = defaultdict(lambda : 0)
z = defaultdict(lambda : 0)
tmp = 0
for a, b in ab:
    if a == 0 and b == 0:
        tmp += 1
    elif a == 0:
        x[0] += 1
        z[0] = 1
    elif b == 0:
        y[0] += 1
        z[0] = 1
    else:
        if a * b > 0:
            g = math.gcd(a, b)
            a //= g
            b //= g
            x[(abs(a), abs(b))] += 1
            z[(abs(a), abs(b))] = 1
        else:
            g = math.gcd(a, b)
            a //= g
            b //= g
            y[(abs(b), abs(a))] += 1
            z[(abs(b), abs(a))] = 1

ans = 1
for i in z.keys():
    ans *= (2**x[i] + 2**y[i] - 1)
    ans %= mod
ans -= 1
ans += tmp
ans %= mod
print(ans)

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):
import sys
import collections
import fractions
import math
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
zero = 0
dic = {}
mod = 10**9+7
for i in range(n):
    a,b = map(int,input().split())
    rt =0
    if a==0 and b==0:
        zero+=1
        continue
    g = math.gcd(a,b)
    a = a//g
    b = b//g
    if b<0:
        a=-a
        b=-b
    if a<0 and b==0:
        a=-a
        b=-b
    if a<=0:
        rt=1
        a,b = b,-a

    if (a,b) not in dic:
        if rt==0:
            dic[(a,b)] = [1,0]
        else:
            dic[(a,b)] = [0,1]
    else:
        if rt==0:
            dic[(a,b)][0] += 1
        else:
            dic[(a,b)][1] += 1

ans = 1
for i,j in dic.values():
    tmp = pow(2,i,mod) - 1
    tmp2 = pow(2,j,mod) - 1
    su = (tmp+tmp2+1)%mod
    ans = (ans*su)%mod

ans = (ans-1+zero)%mod

print(ans)

Solution (Python):
import sys, bisect, collections, math
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
MOD = 1000000007
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    AB = [LI() for _ in range(N)]

    
    def normalize(AB):
        A = AB[0]
        B = AB[1]
        if A==B==0:
            return (0, 0)
        elif A==0:
            return(0, 1)
        elif B==0:
            return(1, 0)
        else:
            gcd = math.gcd(A, B)
            A //= gcd
            B //= gcd
            if A<0:
                A, B = -A, -B
            return (A, B)
    
    def orthogonal(AB):
        A = AB[0]
        B = AB[1]
        if B>0:
            return (B, -A)
        else:
            return(-B, A)

    AB_n = [normalize(i) for i in AB]
    counter = collections.Counter(AB_n)

    
    used = set()
    ans = 1
    
    for A, B in AB_n:
        if not (A, B) in used:
            if (A, B)!=(0, 0):
                ans *= pow(2, counter[(A, B)], MOD) + pow(2, counter[orthogonal((A, B))], MOD) - 1
                ans %= MOD
                used.add((A, B))
                used.add(orthogonal((A, B)))
    ans -= 1
    
    ans += counter[(0, 0)]
    ans %= MOD

    print(ans)

if __name__ == '__main__':
    resolve()

Solution (Python):
from math import gcd

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

for i 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 math import gcd

mod = 10**9 +7
N = int(input())
dic = {}

zero = 0
for _ in range(N):
    a,b = map(int, input().split())
    if  a ==0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        key = (0,1)
    elif b == 0:
        key = (1,0)
    else:
        if a<0:
            a=-a 
            b=-b
        g = gcd(a,abs(b))
        key = (a//g,b//g)
    
    if key not in dic:
        dic[key]=0

    dic[key] +=1

ans = 1
for k1, v1 in dic.items():
    if v1 ==0:
        continue

    if k1[1] >0:
        k2 = (k1[1],-k1[0])
    else:
        k2 = (-k1[1],k1[0])

    if k2 not in dic:
        ans *= 2**v1
        ans %= mod
    else:
        ans *= ((2**v1-1) %mod) + ((2**dic[k2]-1) %mod) +1
        ans %= mod
        dic[k2]=0

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

Solution (Python):
import collections

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

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(0,1)]+=1
    elif b==0:
      dic[(1,0)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a>0:
    s.add((-b,a))
    cnt1=dic[(a,b)]
    if (-b,a) in dic:
      cnt2=dic[(-b,a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
  else:
    s.add((b,-a))
    cnt1=dic[(a,b)]
    if (b,-a) in dic:
      cnt2=dic[(b,-a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
print((ans+cnt-1)%mod)

Solution (Python):
import collections

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

mod=10**9+7
n=int(input())
dic=collections.defaultdict(int)
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      dic[(0,1)]+=1
    elif b==0:
      dic[(1,0)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      s.add((-b,a))
      cnt1=dic[(a,b)]
      if (-b,a) in dic:
        cnt2=dic[(-b,a)]
      else:
        cnt2=0
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    elif a<0:
      s.add((b,-a))
      cnt1=dic[(a,b)]
      if (b,-a) in dic:
        cnt2=dic[(b,-a)]
      else:
        cnt2=0
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
  else:
    s.add((b,a))
    cnt1=dic[(a,b)]
    if (b,a) in dic:
      cnt2=dic[(b,a)]
    else:
      cnt2=0
    ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
    ans%=mod
print((ans+cnt-1)%mod)

Solution (Python):
from math import gcd
 
N = int(input())
mod = 10 ** 9 + 7 
 
d = dict()
zeros = 0
for _ in range(N):
  a, b = map(int, input().split()) 
  
  
  
  if not any((a,b)):
    zeros += 1
    continue
  if all((a, b)):
    g = gcd(a, b) * (a//abs(a)) 
  elif a:
    g = a
  else:
    g = b
  p = a//g, b//g 
  d[p] = d.get(p, 0) + 1 

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

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

Solution (Python):
from math import gcd

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

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

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

Solution (Python):
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {} 
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1 
        continue
    g = gcd(x, y)
    x //= g 
    y //= g 
    
    if y < 0: x, y = -x, -y 
    if y==0 and x<0: x, y = -x, -y 
    
    is_rotate90 = (x <= 0)
    if is_rotate90: x, y = y, -x 
    if not (x, y) in bad: bad[x, y] = [0, 0]
    
    bad[x, y][is_rotate90] += 1

ans = 1 
for x, y in bad:
    c1, c2 = bad[x, y]
    
    
    
    
    c3 = (pow(2, c1, mod) - 1) + (pow(2, c2, mod) - 1) + 1
    ans *= c3
    ans %= mod



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

Solution (Python):
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1
        continue
    g = gcd(x, y)
    x //= g
    y //= g
    if y < 0: x, y = -x, -y
    if y==0 and x<0: x, y = -x, -y
    is_rotate90 = (x <= 0)
    if is_rotate90: x, y = y, -x
    if not (x, y) in bad: bad[x, y] = [0, 0]
    bad[x, y][is_rotate90] += 1

ans = 1
for x, y in bad:
    c1, c2 = bad[x, y]
    c3 = (pow(2, c1, mod) - 1) + (pow(2, c2, mod) - 1) + 1
    ans *= c3
    ans %= mod

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

Solution (Python):
from math import gcd
mod = 1000000007
n = int(input())
zero = 0
bad = {}
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zero += 1
        continue
    g = gcd(x, y)
    x //= g
    y //= g
    if y < 0: x, y = -x, -y
    if y==0 and x<0: x, y = -x, -y
    is_rotate90 = (x <= 0)
    if is_rotate90:
        x, y = y, x
        y = -y
    if not (x, y) in bad:
        bad[x, y] = [0, 0]
    if is_rotate90:
        bad[x, y][0] += 1
    else:
        bad[x, y][1] += 1



cnt = 1
for x, y in bad:
    c1, c2 = bad[x, y]
    c3 = 1
    c3 += pow(2, c1, mod) - 1
    c3 += pow(2, c2, mod) - 1
    cnt = cnt * c3 % mod

ans = (cnt + zero - 1) % mod




print((ans+mod) % mod)

Solution (Python):

import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10**8)

MOD = 1000000007  


def solve(N: int, A: "List[int]", B: "List[int]"):

    def quadrant(a, b):
        if a > 0 and b >= 0:
            return 0
        elif a <= 0 and b > 0:
            return 1
        elif a < 0 and b <= 0:
            return 2
        elif a >= 0 and b < 0:
            return 3
        else:
            return None

    def norm(a, b):
        g = gcd(a, b)
        a //= g
        b //= g
        while quadrant(a, b) != 0:
            a, b = -b, a
        return a, b

    d = defaultdict(lambda: [0, 0, 0, 0])
    kodoku = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if (a, b) == (0, 0):
            kodoku += 1
        else:
            d[norm(a, b)][quadrant(a, b)] += 1

    ans = 1
    for v in d.values():
        buf = pow(2, v[0]+v[2], MOD)
        buf += pow(2, v[1]+v[3], MOD)
        buf = (buf-1) % MOD
        ans *= buf
        ans %= MOD

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import math
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  


def solve(N: int, A: "List[int]", B: "List[int]"):
    
    
    
    
    d = Counter()
    
    
    kodokunaiwashi = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if a == 0 and b == 0:
            kodokunaiwashi += 1
        elif b == 0:
            d[1, 0] += 1
        elif b > 0:
            g = math.gcd(b, a)
            aa = a//g
            bb = b//g
            d[aa, bb] += 1
        else:
            g = math.gcd(-b, -a)
            aa = -a//g
            bb = -b//g
            d[(aa, bb)] += 1

    
    ans = 1
    for a, b in d:
        
        
        x, y = -b, a
        if y < 0:
            x = -x
            y = -y
        elif y == 0:
            x = abs(x)

        
        if d[a, b] == None:
            continue

        if d[x, y] == 0:
            
            ans *= pow(2, d[a, b], MOD)
            ans %= MOD
            continue
        else:
            
            
            buf = pow(2, d[a, b], MOD)
            buf += pow(2, d[x, y], MOD)
            buf -= 1
            buf %= MOD
            
            ans *= buf
            ans %= MOD
            d[x, y] = None

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N)  
    B = [int()] * (N)  
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    
    mod = 10**9 + 7

    n = int(input())
    posi = {}
    nega = {}
    ab_zero = 0
    a_zero = 0
    b_zero = 0

    for _ in range(n):
        a,b = map(int, input().split())
        if a==0 and b==0:
            ab_zero += 1
        elif a==0:
            a_zero += 1
        elif b==0:
            b_zero += 1
        elif a*b > 0:
            a = abs(a)
            b = abs(b)
            g = gcd(a, b)
            po = (a//g, b//g)
            if po in posi:
                posi[po] += 1
            else:
                posi[po] = 1
        else:
            a = abs(a)
            b = abs(b)
            g = gcd(a, b)
            ne = (b//g, a//g)
            if ne in nega:
                nega[ne] += 1
            else:
                nega[ne] = 1
    
    res = pow(2, a_zero, mod) + pow(2, b_zero, mod) - 1
    for k, v in posi.items():
        if k in nega:
            res *= pow(2, v, mod) + pow(2, nega[k], mod) - 1
            res %= mod
            nega.pop(k)
        else:
            res *= pow(2, v, mod)
            res %= mod

    for v in nega.values():
        res *= pow(2, v, mod)
        res %= mod

    res += ab_zero - 1
    print(res%mod)

if __name__ == '__main__':
    main()