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



Sample input:
3
1 2
-1 1
2 -1


Sample output:
5

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007
x = []
y = []
ex = [0,0]
ex2 = 0
for i in range(n):
    if (a[i][0]==0 and a[i][1]==0):
        ex2 += 1
    elif (a[i][0]==0):
        ex[0] +=1
    elif (a[i][1]==0):
        ex[1] += 1
    elif (a[i][0]*a[i][1]>0):
        x.append(a[i][1]/a[i][0])
    else:
        y.append(-a[i][0]/a[i][1])
     
x.sort()
y.sort()
#print(x,y)
xl = 0
yl = 0
xu = []
yu = []
xn = 0
yn = 0
while (xl<len(x) and yl<len(y)):
    if (x[xl] > y[yl]):
        yl += 1
    elif (x[xl] < y[yl]):
        xl += 1
    else:
        #print(xl,yl,x,y)
        p = bisect.bisect_right(x,x[xl])
        q = bisect.bisect_right(y,y[yl])
        xn += (p-xl)
        yn += (q-yl)
        xu.append(p-xl)
        yu.append(q-yl)
        xl = p
        yl = q
xu.append(ex[0])
yu.append(ex[1])
#print(xn,yn,xu,yu)
ans = pow(2,n-xn-yn-ex2,mod)
#if (n-xn-yn>0):
    #t = 1
    #for i in range(1,n-xn-yn+1):
        #t *= i
        #t %= mod
    #ans += t
for i in range(len(xu)):
    ans *= (pow(2,xu[i],mod)+pow(2,yu[i],mod)-1)
    ans %= mod
if (ex2==0):
    print((ans-1)%mod)
else:
    f = 1
    for i in range(1,ex2+1):
        f *= i
        f %= mod
    print((ans-1+f)%mod)

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y


N=II()
MP1={}
A0 = 0
B0 = 0
RES=1
for i in range(N):
    A, B = LI()
    if A*B != 0:
        G = gcd(abs(A),abs(B))
        A //= G
        B //= G
        v = (abs(A), abs(B), A*B > 0)
        if not v in MP1:
            MP1[v] = 1
        else:
            MP1[v] += 1

    if A == 0 and B != 0: A0 += 1
    if A != 0 and B == 0: B0 += 1

# print(MP1)

VIS = set()
for (vv, n) in MP1.items():
    (A, B, isPos) = vv
    v = (B, A, not isPos)
    if not v in VIS and not vv in VIS:
        VIS.add(v)
        VIS.add(vv)
        if v in MP1:
            m = MP1[v]
            RES = (RES*POW(2, n))%DVSR + (RES*POW(2, m))%DVSR - RES
            RES %= DVSR
        else:
            RES *= POW(2, n)
            RES %= DVSR

if A0 and B0:
    RES = (RES*POW(2, A0))%DVSR + (RES*POW(2, B0))%DVSR - RES
elif A0:
    RES = RES*POW(2, A0)%DVSR
elif B0:
    RES = RES*POW(2, B0)%DVSR

print((RES-1)%DVSR)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
N, = map(int, input().split())
d = dict()
X = []
cc = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b==0:
        cc += 1
        continue
    if b == 0:
        f = -1
    else:
        f = Fraction(a, b)
    if f not in d:
        d[f] = 0
    d[f] += 1
    X.append((a, b))

vs = dict()
cs = []
for a, b in X:
    if b == 0:
        f1 = -1
    else:
        f1 = Fraction(a, b)
    if a == 0:
        f2 = -1
    else:
        f2 = Fraction(b, -a)
    if f2 not in d:
        d[f2] = 0
    if f1 in vs or f2 in vs:
        continue
    vs[f1] = (d[f1], d[f2])
mod = 10**9+7

tmp = []
r = 1
for k in vs:
    a, b = vs[k]
    r = r * (pow(2, a, mod) + pow(2, b, mod)-1) % mod
print(r-1+cc)

Submission status: Wrong Answer

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]
# a_b = [0 for i in range(n)]
# m_b_a = [0 for i in range(n)]

for i in range(n):
	a[i], b[i] = map(int, input().split())
	# a_b[i] = a[i] / b[i]
	# m_b_a[i] = -b[i] / a[i]

# print("a_b", a_b)
# print("m_b_a", m_b_a)

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		for j in range(n):
			graph[i].append(j)
			graph[j].append(i)
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		if m_b_a in value_indices:
			for j in value_indices[m_b_a]:
				graph[i].append(j)
				graph[j].append(i)
		value_indices[a_b] = value_indices.get(a_b, []) + [i]

# print("value_indices", value_indices)
# print("graph", graph)

def comb(i):
	layers = []
	cur_layer = [i]
	next_layer = []
	used[i] = True
	while len(cur_layer) > 0:
		layers.append(cur_layer)
		next_layer = []
		for item in cur_layer:
			for child in graph[item]:
				if not used[child]:
					next_layer.append(child)
					used[child] = True
		cur_layer = next_layer.copy()
	# print(layers)
	chet = 0
	nechet = 0
	for i in range(len(layers)):
		if i % 2 == 0:
			chet += len(layers[i])
		else:
			nechet += len(layers[i])
	return pow(2, chet, MODULO) + pow(2, nechet, MODULO) -1
	# return 1


ans = 1
used = [False for _ in range(n)]
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i]
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO
print(ans-1)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1

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

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a < 0 :
        a = -a
        b = -b
    g = math.gcd(abs(a),abs(b))
    if a == 0 and b == 0:
        continue
    else:
        if a == 0:
            b = 1
            g = 1
        elif b == 0:
            a = 1
            g = 1
        p1 = str(a//g)+" "+str(b//g)
        if p1 in d:
            d[p1] += 1
        else:
            d[p1] = 1

for i in d.keys():
    i0, i1 = map(int,i.split())
    if str(i1)+" "+str(-i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i1)+" "+str(-i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(i1)+" "+str(-i0)] = 0
    elif str(-i1)+" "+str(i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(-i1)+" "+str(i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(-i1)+" "+str(i0)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod

if ans == 1:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = inpm()
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                m = gcd(a,b)
                a //= m
                b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        if a == 0 or b == 0:
            continue
        flag = 0
        if a == 0 and b == 1:
            rev = ' '.join([str(1),str(0)])
        elif a == 1 and b == 0:
            rev = ' '.join([str(0),str(1)])
        elif a > 0 and b > 0:
            rev = ' '.join([str(b),str(-a)])
        else:
            rev = ' '.join([str(-b),str(a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        if flag:
            continue
        n1 = pow(2,dic[e],mod)
        n2 = pow(2,dic1[rev],mod)
        if n1 == 0:
            ans *= n2
        elif n2 == 0:
            ans *= n1
        else:
            ans *= (n1+n2-1)
        ans %= mod
    print(ans-1+dic['0 0'])
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import collections
from collections import defaultdict

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        b[i/j]+=1
        c[j/i]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0,mod)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))



for k,v in b.items():
    if c[-k]!=0:
        ans*=(pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())
for i,j in w:
    ans*=pow(i*j//2,mod-2,mod)
ans+=cnt
print(ans%mod-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        if a*b!=0:
            g=gcd(abs(a),abs(b))
            a=a//g
            b=b//g
        elif (a,b)!=(0,0):
            if a==0:
                b=1
            else:
                a=1
            
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k,d[k]))

    temp0=0
    for i in range(len(L)):
        k=L[i][0]
        v=d[k]
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if a*b!=0:
            if (-b,a) in d:
                v2=d[(-b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(-b,a)]=0
            if (b,-a) in d:
                v2=d[(b,-a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,-a)]=0
        elif (a,b)==(1,0) or (a,b)==(0,1):
            if (b,a) in d:
                v2=d[(b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,a)]=0
        else:
            temp0=v
            temp=1
        ans=(ans*temp)%mod
        
        


    ans=(ans-1+temp0)%mod
    print(ans)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()

Submission status: Wrong Answer

Solution code:
n=int(input())
mod = 1000000007
gp = []
gm = []
ga0  =0
gb0 = 0
ans = 1
cnt = 0
for _ in range(n):
    a,b= map(int,input().split())
    #a,b = 1,1
    if a == 0 and b == 0:
        cnt += 1
    elif  a == 0:
        ga0 += 1
    elif b == 0:
        gb0 += 1
    elif b/a > 0:
        gp.append(b/a)
    else:
        gm.append(-a/b)
gp.sort()
gm.sort()

lp,lm=0,0
cntall = 0
while lp < len(gp) and lm < len(gm):
    cal = gp[lp] - gm[lm]
    if cal == 0:
        cntp,cntm = 1,1
        while lp +1 < len(gp) and  gp[lp] == gp[lp+1]:
            cntp += 1
            lp+=1
        while lm +1 < len(gm) and  gm[lm] == gm[lm+1]:
            cntm += 1
            lm+=1
        ans *= (pow(2,cntp,mod)+pow(2,cntm,mod)-1)%mod
        ans %= mod
        lp+=1
        lm+=1
        cntall += cntp+cntm
    elif cal < 0:
        lp += 1
    else:
        lm += 1

ans *= (pow(2,ga0,mod)+pow(2,gb0,mod)-1)%mod
ans %= mod
n -= ga0+gb0+cntall+cnt
ans *= pow(2,n,mod)
ans %= mod
ans += cnt - 1
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
MOD = 10**9+7
AB = []
x = 0
y = 0
d = defaultdict(int)
ch = defaultdict(int)
flag = 0
for _ in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        flag = 1
        continue
    elif a == 0:
        x += 1
        continue
    elif b == 0:
        y += 1
        continue
    else:
        dd = math.gcd(abs(a),abs(b))
        a /= dd
        b /= dd
        c = a / b
        d[c] += 1
        AB.append(c)
n = len(AB)
ans = 1
for i in range(n):
    cc = AB[i]
    if ch[cc] != 0:
        continue
    m = d[cc]
    ccc = (-1)/cc
    l = d[ccc]
    ans *= (pow(2,m,MOD)+pow(2,l,MOD)-1)
    ch[cc] = 1
    ch[ccc] = 1
ans *= (pow(2,x,MOD)+pow(2,y,MOD)-1)
if flag == 0:
    ans -= 1
ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import fractions

n = int(input())
mod = 10 ** 6 + 7
c = []
d = []

tan = []
atan = []

for _ in range(n):
    a, b = map(int, input().split())
    if b == 0: tan.append(float('inf'))
    else: tan.append(fractions.Fraction(a, b))
    if a == 0: atan.append(float('inf'))
    else: atan.append(fractions.Fraction(-1 * b, a))

tan = collections.Counter(tan)
atan = collections.Counter(atan)

for key, value in tan.items():
    if -1 <= key < 1: continue
    if atan[key] > 0:
        c.append(value)
        d.append(atan[key])

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1)
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4000)
import math
N = int(input())
mod = 1000000007
degs = {}
ans = 1
for i in range(N):
    A,B = map(int,input().split())
    if(A==0 and B==0):
        ans += 1
        continue
    if(A!=0):
        ab = B/A
    else:
        ab = "mugen"
    if(ab==0):
        nakawaru = "mugen"
    elif(ab == "mugen"):
        nakawaru = 0
    else:
        nakawaru = -1/ab
    if(ab not in degs.keys()):
        degs[ab] = 1
    else:
        degs[ab] += 1
    if(nakawaru not in degs.keys()):
        ans = ans*2%mod
    else:
        waru = pow(2,degs[nakawaru],mod)
        ans = (ans + ans*pow(waru,mod-2,mod)%mod)%mod
    
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import collections
from collections import defaultdict

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        b[i/j]+=1
        c[j/i]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0,mod)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))



for k,v in b.items():
    if c[-k]!=0:
        ans*=(pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())
ans+=cnt
for i,j in w:
    ans*=pow(i*j//2,mod-2,mod)
print(ans%mod-1)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = [],[]
    for i in range(n):
        a,b = map(int, input().split())
        if b == 0:
            C_n.append(0)
        elif a/b < 0:
            C_n.append(a/b)
        else:
            C_p.append(a/b)
    import numpy as np
    from collections import Counter as cc
    C_p,C_n = cc(C_p),cc(C_n)
    count= 0
    re = 1
    for c in C_p:
        if c == 0:
            re *= (2**C_n[c] + 2**C_p[c] -1)%mod
            count += C_p[c]+C_n[c]
            continue

        if -1/c in C_n:
            count += C_n[-1/c] + C_p[c]
            re *= (2**C_n[-1/c] + 2**C_p[c] -1)%mod
    ans = pow(2,n-count,mod)*re%mod -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
zz = 0
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 1
        # a=0
        # b=0
    elif b==0:
        n_sign = 0
        # a=0
        # b=0  


    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd
        #print(n_sign,a,b)

    

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      
    
#print (d_m,d_p)

ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans += zz
ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import sys
MOD = 1000000007  # type: int


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, A: "List[int]", B: "List[int]"):
    # fishes = {}
    # zeroFishesB = 0
    # zeroFishesA = 0
    # valueFishes = N
    #
    # def getFishC(a):
    #     return fishes[a] if a in fishes else 0
    # for i in range(N):
    #     if A[i] == 0 and B[i] == 0: # 両方0,0ならばどの魚とも仲良くなれないので消す
    #         valueFishes -= 1
    #         continue
    #     if A[i] == 0:
    #         zeroFishesA += 1
    #     if B[i] == 0:
    #         zeroFishesB += 1
    #     fishes[(A[i],B[i])] = getFishC((A[i],B[i]))+1
    # def countWithZero(a): # aと中の悪い魚の数を返す
    #     if a[0] != 0 or a[1] != 0:
    #         return getFishC((-a[1],a[0]))+getFishC((a[1],-a[0]))
    #     else:
    #         if a[0] == 0:
    #             return zeroFishesB
    #         else:
    #             return zeroFishesA
    #
    # allCandidate = powm(2,valueFishes,MOD)-1
    # print(allCandidate)
    # for k in fishes:
    #     print(f"{k}->{countWithZero(k)}")
    fishes = []
    validFishes = N
    fishRads = dict() # (int,int) -> (int,int) key: 第一象限になおした最小の整数で表現されたイワシベクトル、value: keyが等しくなるものの(第1,3象限の数、と第2,4象限の数)
    for i in range(N):
        if A[i] == 0 or B[i] == 0:
            validFishes-=1
            continue
        fishes.append((A[i],B[i]))
        cur = (0,0)
        gg = math.gcd(abs(A[i]), abs(B[i]))
        if (A[i] > 0 and B[i] >= 0) or (A[i] < 0 and B[i] <= 0):
            normalRad = (A[i]//gg,B[i]//gg)
            if normalRad[1] <= 0:
                normalRad = (-normalRad[0], -normalRad[1])
            if normalRad in fishRads:
                cur = fishRads[normalRad]
            fishRads[normalRad] = (cur[0]+1,cur[1])
        else:
            rotRad = (-B[i] // gg, A[i] // gg)
            if rotRad[1] <= 0:
                rotRad = (-rotRad[0],-rotRad[1])
            if rotRad in fishRads:
                cur = fishRads[rotRad]
            fishRads[rotRad] = (cur[0], cur[1]+1)
    current = 1
    # print(fishRads)
    for k in fishRads:
        groups = fishRads[k]
        stage= (powm(2,groups[0],MOD) + powm(2,groups[1],MOD)-1)%MOD
        current = current*stage%MOD
    print(current-1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    
    input = sys.stdin.readline
    n = int(input())
    mod = 10**9+7
    d = {}
    l1 = []
    l2 = []
    zero = [0]*3
    for i in range(n):
        a,b = map(int,input().split())
        if a == 0 and b == 0:
            zero[0] += 1
        elif a == 0:
            zero[1] += 1
        elif b == 0:
            zero[2] += 1
        else:
            s1 = -b/a
            s2 = a/b
            if s2 in d:
                d[s2] += 1
            else:
                l1.append(s2)
                l2.append(-1)
                d[s2] = 1
                if s1 in d:
                    ind = l1.index(s1)
                    l2[-1] = ind
                    l2[ind] = len(l1)-1

    done = set()
    ans = 1
    for i in range(len(l2)):
        if l2[i] < 0:
            ans *= 2
            ans %= mod
        else:
            if l2[i] in done:
                continue
            c1 = d[l1[i]]
            c2 = d[l1[l2[i]]]
            count = (pow(2,c1,mod)+pow(2,c2,mod)-1)%mod
            ans *= count
            ans %= mod
            done.add(i)
            done.add(l2[i])
    c = 0
    if zero[0] > 0:
        c = pow(2,zero[0],mod)
    if zero[1] *zero[2] > 0:
        count = (pow(2,zero[1],mod)+pow(2,zero[2],mod)-1)%mod
        ans *= count
        ans %= mod
    elif zero[1] > 0:
        ans *= pow(2,zero[1],mod)
        ans %= mod
    elif zero[2] > 0:
        ans *= pow(2,zero[2],mod)
        ans %= mod
    print(ans+c-1)
            
if __name__ =="__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

N = int(input())
MOD = 1000000007
d = defaultdict(int)
num_00 = 0
pow2 = [1]
for i in range(N):
  pow2.append((pow2[-1] * 2) % MOD)

def to_idx(a, b):
  if a == 0 and b != 0:
    return ((-1, 0), (1, 0))
  elif a != 0 and b == 0:
    return ((0, -1), (0, 1))
  else:
    return tuple(sorted(((a, b), (-a, -b))))

ans = 0
for i in range(N):
  a, b = map(int, input().split())
  if a == 0 and b != 0:
    d[((0, -1), (0, 1))] += 1
  elif a != 0 and b == 0:
    d[((-1, 0), (1, 0))] += 1
  elif a == b == 0:
    num_00 += 1
  else:
    g = gcd(a, b)
    a //= g; b //= g
    d[to_idx(a, b)] += 1

memo = []
key_set = set(d.keys())
while key_set:
  k = key_set.pop()
  v1, v2 = k
  a, b = v1
  idx = to_idx(-b, a)
  memo.append((pow2[d[k]] + pow2[d[idx]] - 1) % MOD)
  key_set.discard(idx)

ans = 1
for m in memo:
  ans *= m
  ans %= MOD

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

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18
SIZE = 3 * 10 ** 5

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

cnt = defaultdict(int)
zero = 0
for a, b in AB:
    if a != 0 and b != 0:
        cnt[b / a] += 1
    else:
        zero += 1
#print(cnt)


answer = 1
rest = N

answer *= 1 + zero
rest -= zero
#print(answer)

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

print(answer)

Submission status: Wrong Answer

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

zerozero = 0
somezero = 0
zerosome = 0
plus = []
minus = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zerozero += 1
    elif a == 0:
        zerosome += 1
    elif b == 0:
        somezero += 1
    elif (a > 0 and b > 0) or (a < 0 and b < 0):
        plus.append(a/b)
    else:
        minus.append(-b/a)
plus.sort()
minus.sort()

ans = pow(2, zerozero, mod)
ans *= pow(2, zerosome, mod) + pow(2, somezero, mod) - 1

i = 0
j = 0
while i < len(plus) and j < len(minus):
    ni = plus[i]
    nj = minus[j]
    if plus[i] < minus[j]:
        i += 1
        ans *= 2
        ans %= mod
        continue
    elif minus[j] < plus[i]:
        j += 1
        ans *= 2
        ans %= mod
        continue

    nump = 0
    numm = 0
    while i < len(plus) and plus[i] == ni:
        i += 1
        nump += 1
    while j < len(minus) and minus[j] == nj:
        j += 1
        numm += 1
    ans *= pow(2, nump, mod) + pow(2, numm, mod) - 1
    ans %= mod

ans *= pow(2, len(plus) - i, mod)
ans *= pow(2, len(minus) - j, mod)
ans %= mod

print(ans - 1)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

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

ans = 1
for k, v in p_map.items():

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

n_num = sum(n_map.values())
ans *= pow(2, n_num, MOD)
ans %= MOD

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from math import gcd
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
d = dd(int)
a = [tuple(map(int, input().split())) for _ in range(N)]
z = 0
for x, y in a:
  g = gcd(abs(x), abs(y))
  if (x, y) == (0, 0):
    N -= 1
    z += 1
    continue
  d[(x // g, y // g)] += 1
res = 1
u = 0
itr = list(d.keys())
#print(itr)
for x, y in itr:
  t = d[(y, -x)] + d[(-y, x)]
  if t == 0: u += d[(x, y)]
for x, y in itr:
  t = 0
  if (x, y) == (0, 1):
    t = d[(1, 0)]
  elif (x, y) == (1, 0):
    t = d[(0, 1)]
  else:
    t = d[(y, -x)] + d[(-y, x)]

  if t:
    v = 0
    v += pow(2, d[(x, y)], mod) - 1
    v %= mod
    v += pow(2, t, mod) - 1
    v %= mod
    v += 1
    v %= mod
    res *= v
    res %= mod
    #print(res, v)
  d[(x, y)] = 0
#print(itr, u, res)
print(res * pow(2, u, mod) - 1 + z % mod)