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 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)-((pow(2,c0)-1)*(pow(2,b0)-1))


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

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
def resolve():
    import math
    from fractions import Fraction
    mod = 10**9 + 7
    n = int(input())
    dic1 = {}
    for i in range(n):
        a, b = map(int, input().split())
        if a == 0 or b == 0:
            if 0 in dic1:
                dic1[0] += 1
            else:
                dic1[0] = 1
        else:
            c = math.gcd(a,b)
            a = a//c
            b = b//c
            if Fraction(a,b) in dic1:
                dic1[Fraction(a,b)] += 1
            else:
                dic1[Fraction(a,b)] = 1

    ans = 1
    for i in dic1:
        if i == 0:
            ans *= (dic1[0]+1)
            ans %= mod
        elif -1 * (Fraction(1,i)) in dic1:
            counter = -1 * (Fraction(1,i))
            ans *= (2**dic1[i]+2**dic1[counter]-1)
            ans %= mod
            dic1[i] = 0
            dic1[counter] = 0
        else:
            ans *= (dic1[i]+1)
            ans %= mod
    print(ans%mod-1)

resolve()

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

adivb = [float('inf') if ab[i][1] == 0 else ab[i][0] / ab[i][1]
         for i in range(n)]
bdiva = [-float('inf') if ab[i][0] == 0 else -ab[i][1] / ab[i][0]
         for i in range(n)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i >= 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
print((ans * 2 ** (n - cnt) - 1) % mod)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
ab=[list(map(int,input().split())) for i in range(n)]

dic=defaultdict(int)
zero=[0,0]

for i in range(n):
    a,b=ab[i]
    if a==0 and b==0:
        n-=1
    elif a==0:
        zero[0]+=1
    elif b==0:
        zero[1]+=1
    else:
        dic[a/b]+=1

# print(dic)
# print(zero)
anslst=[]
lst=list(dic.items())
ans=1
# print(lst)
for i in range(len(lst)):
    num,m=lst[i]
    tmp=1
    if dic[num]!=0:
        tmp=pow(2,m,mod)-1+pow(2,dic[-1/num],mod)-1+1
        dic[-1/num]=0
    anslst.append(tmp)


anslst.append(pow(2,zero[0],mod)-1+pow(2,zero[1],mod)-1+1)

for i in anslst:
    ans*=i
    ans%=mod
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 and 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 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 collections
import fractions

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

frac = {}

for _ in range(n):
    a, b = map(int, input().split())
    try:
        if b == 0: frac[float('inf')] += 1
        else: frac[fractions.Fraction(a, b)] += 1
    except KeyError:
        if b == 0: frac[float('inf')] = 1
        else: frac[fractions.Fraction(a, b)] = 1

for key, value in frac.items():
    if -1 <= key < 1: continue
    try:
        if key != 0:
            d.append(frac[-1 / key])
        else:
            d.append(frac[float('inf')])
        c.append(value)
    except KeyError:
        continue

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:
from math import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases = 1
    elif a * b >=0 and a != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 + zero_cases
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans-1) % MOD)

Submission status: Wrong Answer

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

mod = 10**9+7

N = int(input())
As = {}
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    if g == 0: continue
    x, y = x//g, y//g
    if y < 0 or (y==0 and x < 0):
        y = -y
        x = -x
    if (x, y) in As:
        As[(x, y)] += 1
    else:
        As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases = 1
    elif a * b >=0 and a != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 + zero_cases
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
import math
M = 10**9+7
def getRev(a,b):
    if -b>0:
        return (-b,a)
    else:
        return (b,-a)

def main():
    n = int(input())
    
    d = {}
    
    for _ in range(n):
        a,b = tuple(map(int,input().split()))
        if a<0:
            a,b = -a,-b
        e1,e2 = 0,0
        if a!=0 and b!=0:
            g = math.gcd(abs(a),abs(b))
            e1,e2 = a//g,b//g
        else:
            g = max(abs(a),abs(b))
            if g!=0:
                e1,e2 = a//g,b//g
                e2 = -abs(e2)
        k = e1,e2
        d.setdefault(k,0)
        d[k] += 1

    ans = 1
    for k,v in d.items():
        if k == (0,0):
            pass
        else:
            k_r = getRev(*k)
            if k_r in d:
                if d[k_r]!=-1 and d[k]!=-1:
                    v2 = d[k_r]
                    ans *= (pow(2,v,M)+pow(2,v2,M)-1)
                    ans %= M
                    d[k] = -1
                    d[k_r] = -1
            else:
                ans*=pow(2,v,M)
                ans %= M

    print(ans-1)
        

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import collections
import fractions

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

frac = {}

for _ in range(n):
    a, b = map(int, input().split())
    try:
        if b == 0: frac[float('inf')] += 1
        else: frac[fractions.Fraction(a, b)] += 1
    except KeyError:
        if b == 0: frac[float('inf')] = 1
        else: frac[fractions.Fraction(a, b)] = 1

for key, value in frac.items():
    if -1 <= key < 1: continue
    try:
        d.append(frac[-1 / key])
        c.append(value)
    except KeyError:
        continue

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 collections

N=int(input())
posi=[]
nega=[]
mod=1000000007
power=[1]*(N+1)
zero=0

for i in range(1,N+1):
    power[i]=power[i-1]*2%mod
    
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif b==0:
        nega.append(0.0)
    elif a/b>=0:
        posi.append(a/b)
    else:
        nega.append((-1)*b/a)

m=N-zero
cp=collections.Counter(posi)
cn=collections.Counter(nega)

x=1
y=1


for pp in cp.keys():
    if pp in cn.keys():
        p=cp[pp]
        n=cn[pp]
        powp=power[p]
        pown=power[n]
        e=(powp-1)*(pown-1)%mod
        f=(powp+pown-1)%mod
        x=x*(e+f)%mod
        y=y*f%mod
        m-=(p+n)
        
ans=power[N-zero]-1-power[m]*(x-y)%mod
print((ans+zero)%mod)

Submission status: Wrong Answer

Solution code:
import math
mod = 1000000007
D = {}
X = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    elif a == 0:
        b = 1
    g = math.gcd(a,b)
    a = a//g
    b = b//g
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d    
    if [a,b] in X:
        D[(a,b)] += 1
    else:
        D[(a,b)] = 1
        X.append([a,b])
n = N - zero
A = []
for [a,b] in X:
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d
    x = D[(a,b)]
    y = 0
    if [c,d] in X:
        y = D[(c,d)]
        X.remove([c,d])
    if y > 0:
        A.append([x,y])
        n = n - x - y
ans = 1
for [x,y] in A:
    z = (2**x + 2**y - 1)%mod
    ans *= z
    ans % mod
z = 2**n % mod
ans *= z
ans -= 1
ans % mod
ans += zero
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 and 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 and n2 != 0:
            ans *= n2
        elif n2 == 0 and n1 != 0:
            ans *= n1
        elif n1 != 0 and n2 != 0:
            ans *= (n1+n2-1)
        ans %= mod
    print(ans-1+dic['0 0'])
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
mod = 1000000007
D = {}
X = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if (a,b) == (0,0):
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    elif a == 0:
        b = 1
    g = math.gcd(a,b)
    a = a//g
    b = b//g
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d    
    if [a,b] in X:
        D[(a,b)] += 1
    else:
        D[(a,b)] = 1
        X.append([a,b])
n = N - zero
A = []
for [a,b] in X:
    c = b
    d = -a
    if c < 0:
        c = -c
        d = -d
    x = D[(a,b)]
    y = 0
    if [c,d] in X:
        y = D[(c,d)]
        X.remove([c,d])
    if y > 0:
        A.append([x,y])
        n = n - x - y
ans = 1
for [x,y] in A:
    z = (2**x + 2**y - 1)%mod
    print(z)
    ans *= z
    ans % mod
z = 2**n % mod
ans *= z
ans -= 1
ans % mod
ans += zero
print(ans)

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)]

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

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
zeroes = 0
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		# 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

	chet = 0
	nechet = 0
	is_chet = True
	while len(cur_layer) > 0:
		if is_chet:
			chet += len(cur_layer)
		else:
			nechet += len(cur_layer)
		is_chet = not is_chet
		# 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)
	# 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


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 + zeroes)

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 and 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 math
mod = 10**9 + 7
n = int(input())
d = {}
d0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    if g == 0:
        d0 += 1
    else:
        a //= g
        b //= g
        if a < 0:
            a = -a
            b = -b
        elif a == 0 and b < 0:
            b = -b
        if (a,b) in d:
            d[(a,b)] += 1
        else:
            d[(a,b)] = 1
ans = 1
for (a,b) in d.keys():
    if d[(a,b)] > 0:
        t = 2**d[(a,b)]
        if b < 0:
            a = -a
            b = -b
        if (b,-a) in d:
            t += 2**d[(b,-a)] - 1
            d[(b,-a)] = 0
        ans *= t
        ans %= mod
print((ans+d0-1)%mod)

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

    if a*b > 0:
        if a < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        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 b < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        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:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

mod=10**9+7
n=int(input())
fact=[1]
revfact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[-1],mod-2,mod))
dic={}
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:
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      if (-abs(a)//g,abs(b)//g) not in dic:
        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:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a*b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      tmp=1
      for i in range(1,cnt1+1):
        tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
      for i in range(1,cnt2+1):
        tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
      ans*=tmp
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
print(ans+cnt-1)

Submission status: Wrong Answer

Solution code:
import math
mod = 10**9 + 7
n = int(input())
d = {}
d0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    if g == 0:
        d0 += 1
    else:
        a //= g
        b //= g
        if a < 0:
            a = -a
            b = -b
        elif a == 0 and b < 0:
            b = -b
        if (a,b) in d:
            d[(a,b)] += 1
        else:
            d[(a,b)] = 1
ans = 1
print(d)
for (a,b) in d.keys():
    if d[(a,b)] > 0:
        t = 2**d[(a,b)]
        if b < 0:
            a = -a
            b = -b
        if (b,-a) in d:
            t += 2**d[(b,-a)] - 1
            d[(b,-a)] = 0
        ans *= t
        ans %= mod
print((ans+d0-1)%mod)

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 y < 0:
    x, y = -x, -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 * pow(-1, int(x < 0) + 1), abs(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 * pow(-1, int(x < 0) + 1), abs(x))]
  #print(t, d, (x, y))
  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)

Submission status: Wrong Answer

Solution code:
from math import gcd
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):
        if a < 0:
            a, b = -a, -b
        g = gcd(a, b)
        a //= g
        b //= g
        plus.append((a, b))
    else:
        if a < 0:
            a = -a
        else:
            b = -b
        g = gcd(a, b)
        a //= g
        b //= g
        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:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = [],[]
    from fractions import Fraction as f
    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(f(a/b))
        else:
            C_p.append(f(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 (cinv:=f(-1/c)) in C_n:
            count += C_n[cinv] + C_p[c]
            re *= (2**C_n[cinv] + 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:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = {}
r = 0
for i in range(n):
    if a[i][0] == 0 and a[i][1] == 0:
        r += 1
    elif a[i][0] == 0:
        if 0 in d:
            d[0][0] = d[0][0] +1
        else:
            d[0] = [1, 0]
    elif a[i][1] == 0:
        if 0 in d:
            d[0][1] = d[0][1] +1
        else:
            d[0] = [0, 1]
    else:
        if a[i][0] * a[i][1] > 0:
            s = a[i][0] / a[i][1]
            if s in d:
                d[s][0] = d[s][0] +1
            else:
                d[s] = [1, 0]
        else:
            s = -a[i][1] / a[i][0]
            if s in d:
                d[s][1] = d[s][1] +1
            else:
                d[s] = [0, 1]
ans = 1
m = 0
for i in d:
    m += 1
    ans *= 2**d[i][0] + 2**d[i][1] - 1
    #if m != 1:
        #ans -= 1
    #print(ans)
ans -= 1
ans += r
ans = ans%1000000007
#print(d)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
mod = 10**9+7
def f(aai, bbi):
    if (aai == 0)&(bbi==0):
        return 0, 0
    gc = gcd(aai, bbi)
    a, b = aai // gc, bbi // gc
    if a < 0:
        a = -a
        b = -b
    return a, b

n= int(input())
aa = [0] * n
for i in range(n):
    ai, bi = map(int, input().split())
    aa[i] = f(ai, bi)

dic_ = Counter(aa)

cnt = 1
while len(dic_) > 0:
    k, v = dic_.popitem()
    ka , kb = k[0], k[1]
    if (ka ==0) & (kb==0):
        cnt = (cnt + 2**v-1)%mod
    if kb < 0:
        ka = -ka
        kb = -kb
    t = dic_.get((kb, -ka), 0)
    if t > 0:
        del dic_[(kb, -ka)]
        cnt = (cnt * (2**v) + (2**t) - 1) % mod
    else:
        cnt = (cnt * (2**v)) % mod
print((cnt+mod-1)%mod)