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 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 and b == 0:
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == -1:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = -1
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(1)
    exit()

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

p_zero_map = 0
n_zero_map = 0
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
    elif a == 0 and b != 0:
        key = "{}_{}".format(a, abs(b))
        n_zero_map += 1
    elif b == 0 and a != 0:
        key = "{}_{}".format(abs(a), b)
        p_zero_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)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    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

res = 0
if p_zero_map > 0 and n_zero_map > 0:
    res = pow(2, p_zero_map, MOD)-1 + pow(2, n_zero_map, MOD)-1
    res += 1
elif p_zero_map > 0 and n_zero_map == 0:
    res = pow(2, p_zero_map, MOD)
elif p_zero_map == 0 and n_zero_map > 0:
    res = pow(2, n_zero_map, MOD)
if res > 0:
    res %= MOD
    ans *= res
    ans %= MOD


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

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 and b == 0:
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1) in d.keys():
    din = d[(i0,i1)]
    if din == 0:
        continue
    if i1 < 0:
        i00 = -i0
        i10 = -i1
    else:
        i00 = i0
        i10 = i1
    if (i10,-i00) in d.keys():
        aaa = (twoxxn(d[(i10,-i00)],mod)+twoxxn(din,mod)-1)%mod
        ans = (ans*aaa)%mod
        d[(i10,-i00)] = 0
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(1)
    exit()

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

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 and b == 0:
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1

for (i0, i1), din in d.items():
    if din == 0:
        continue
    if i1 < 0:
        i0 = -i0
        i1 = -i1
    if (i1,-i0) in d.keys():
        aaa = (twoxxn(d[(i1,-i0)],mod)+twoxxn(din,mod)-1)%mod
        ans = (ans*aaa)%mod
        d[(i1,-i0)] = 0
    else:
        ans = (ans*twoxxn(din,mod))%mod

if len(d.keys()) == 0:
    print(1)
    exit()

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

Submission status: Wrong Answer

Solution code:
from math import gcd
import sys
input = sys.stdin.readline
n=int(input())
dic={}
z=0
mod=10**9+7
for i in range(n):
    a,b=map(int,input().split())
    if a==b==0:
        z+=1
        continue
    k=gcd(a,b)
    a//=k
    b//=k
    if b<0:
        a=-a
        b=-b
    if b==0 and a<0:
        a=-a
    if a<=0:
        a,b=b,-a
        if (a,b) in dic:
            dic[(a,b)][0]+=1
        else:
            dic[(a,b)]=[1,0]
    else:
        if (a,b) in dic:
            dic[(a,b)][1]+=1
        else:
            dic[(a,b)]=[0,1]
ans=1
for x in dic:
    v=dic[x]
    s = v[0]
    t = v[1]
    ans*=pow(2,s,mod)+pow(2,t,mod)-1
    ans%=mod
print(z-1+ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a/b] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = a/b
    if done[k]: continue
    rk = -b/a
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)
for i in range(N):
    if ab[i][1] != 0:
        d[ab[i][0] / ab[i][1]] += 1
    elif ab[i][0] == ab[i][1] == 0:
        d[10**18+2] += 1
    else:
        d[10**18+1] += 1
d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
flag = 0
for k, v in d_l:
    if k == 10**18+2:
        flag = 1
        continue
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0.0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0:
        if not d[-1/k]:
            cnt = ((v+1) * cnt) % mod
    elif d[-1/k]:
        cnt = (cnt * ((2**v-1) + (2**d[-1/k]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print((cnt - 1 + flag) % mod)

Submission status: Wrong Answer

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a*b == 0:
        if a == 0 and b != 0:
            azero += 1
        elif a != 0 and b == 0:
            bzero += 1
    else:
        g = gcd(a,b)
        a //= g
        b //= g
        if a<0:
            a *= -1
            b *= -1
        before = cnd.get((a,b),False)
        if b > 0:
            check = cnd.get((b,-a),False)
        else:
            check = cnd.get((-b,a),False)
        if before:
            cnd[(a,b)] = [before[0]+1,before[1]]
        elif check:
            if b > 0:
                cnd[(b,-a)] = [check[0],check[1]+1]
            else:
                cnd[(-b,a)] = [check[0],check[1]+1]
        else:
            cnd[(a,b)] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1
#print(cnd)
for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]+2**item[1]-1)
        ans %= mod
print((ans*((2**noreg)%mod)-1+allzero)%mod)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

mod=1000000007

n=int(input())
katamuki_list=[]
for i in range(n):
    a, b=map(int, input().split())
    if a==0 and b==0:
        tmp=(0, 0)
    elif a==0:
        tmp=(0, 1)
    elif b==0:
        tmp=(1, 0)
    else:
        gcd=math.gcd(a, b)
        a=a//gcd
        b=b//gcd
    katamuki_list.append((a, b))

katamuki_counter=Counter(katamuki_list)
ans=1
for katamuki_key in list(katamuki_counter.keys()):
    # print(katamuki_key)
    katamuki_value=katamuki_counter[katamuki_key]
    if (0, 0)==katamuki_key:
        pass
    elif (0, 1)==katamuki_key or (1, 0)==katamuki_key:
        pass
    else:
        if katamuki_value!=0:
            reverse_0=(-katamuki_key[1], katamuki_key[0])
            reverse_1=(katamuki_key[1], -katamuki_key[0])
            reverse_count=katamuki_counter[reverse_0]+katamuki_counter[reverse_1]
            # print(reverse_count)
            ans=(ans*(pow(2, katamuki_value, mod)-1+pow(2, reverse_count, mod)-1+1))%mod
            # print(ans)
            katamuki_counter[reverse_0]=0
            katamuki_counter[reverse_1]=0
ans=(ans*(pow(2, katamuki_counter[(1, 0)], mod)-1+pow(2, katamuki_counter[(0, 1)], mod)-1+1))%mod
ans=ans-1 #全て選ばないという場合を引く
ans=(ans+katamuki_counter[(0, 0)])%mod

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
used = [False for _ in range(n)]
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
		# 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):
	# print("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
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i] = True
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO

print((ans-1+zeroes) % MODULO)

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a/b] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = a/b
    if done[k]: continue
    rk = -b/a
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from collections import Counter
slope=Counter()
slope_zero=0
slope_inf=0
both_zero=0
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        both_zero=1
    else:
        if a==0:
            slope_zero+=1
        elif b==0:
            slope_inf+=1
        else:
            sign=(a//abs(a))*(b//abs(b))
            a=abs(a)
            b=abs(b)
            gc=gcd(a,b)
            a//=gc
            b//=gc
            if sign==1:
                slope[(a,b)]+=1
            else:
                slope[(-a,b)]+=1
ans=1
mod=10**9+7
for a,b in slope.keys():
    if slope[(a,b)]>0:
        aa=-b
        bb=a
        if bb<0:
            bb*=-1
            aa*=-1
        if slope[(aa,bb)]>0:
            ans*=(pow(2,slope[(a,b)],mod)+pow(2,slope[(aa,bb)],mod)-1+mod)%mod
            ans%=mod
            slope[(aa,bb)]=0
        else:
            ans*=(pow(2,slope[(a,b)],mod))%mod
            ans%=mod
ans*=(pow(2,slope_zero,mod)+pow(2,slope_inf,mod)-1+mod)%mod
ans%=mod
ans+=both_zero
if ans>=mod:
    ans%=mod
print((ans-1+mod)%mod)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

mod=1000000007

n=int(input())
katamuki_list=[]
for i in range(n):
    a, b=map(int, input().split())
    if a==0 and b==0:
        tmp=(0, 0)
    elif a==0:
        tmp=(0, 1)
    elif b==0:
        tmp=(1, 0)
    else:
        gcd=math.gcd(a, b)
        a=a//gcd
        b=b//gcd
    katamuki_list.append((a, b))

katamuki_counter=Counter(katamuki_list)
ans=1
for katamuki_key in list(katamuki_counter.keys()):
    # print(katamuki_key)
    katamuki_value=katamuki_counter[katamuki_key]
    if (0, 0)==katamuki_key:
        pass
    elif (0, 1)==katamuki_key or (1, 0)==katamuki_key:
        pass
    else:
        if katamuki_value!=0:
            reverse_0=(-katamuki_key[1], katamuki_key[0])
            reverse_1=(katamuki_key[1], -katamuki_key[0])
            reverse_count=katamuki_counter[reverse_0]+katamuki_counter[reverse_1]
            # print(reverse_count)
            ans=ans*(pow(2, katamuki_value, mod)-1+pow(2, reverse_count, mod)-1+1)%mod
            # print(ans)
            katamuki_counter[reverse_0]=0
            katamuki_counter[reverse_1]=0
ans=(ans*(pow(2, katamuki_counter[(1, 0)], mod)-1+pow(2, katamuki_counter[(0, 1)], mod)-1+1))%mod
ans=ans-1 #全て選ばないという場合を引く
ans=(ans+katamuki_counter[(0, 0)])%mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a/b] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = a/b
    if done[k]: continue
    rk = -b/a
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)
for i in range(N):
    if ab[i][1] != 0:
        d[ab[i][0] / ab[i][1]] += 1
    else:
        d[10**18+1] += 1
d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
for k, v in d_l:
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0.0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0:
        if not d[-1/k]:
            cnt = ((v+1) * cnt) % mod
    elif d[-1/k]:
        cnt = (cnt * ((2**v-1) + (2**d[-1/k]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print((cnt - 1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n)]
mod = 10 ** 9 + 7
cnt = defaultdict(lambda :0)

for i in range(n):
    a, b = ab[i]
    if (a, b) == (0, 0):
        cnt[(0, 0)] += 1
        continue

    elif b == 0:
        temp = (1, 0)
        cnt[temp] += 1
        ab[i] = temp
        continue

    GCD = gcd(a, b)
    temp = (a // GCD, b // GCD) if b > 0 else (- a // GCD, - b // GCD)
    cnt[temp] += 1
    ab[i] = temp

check = defaultdict(lambda :0)
for key in ab:
    a, b = key
    if not check[key]:check[key] += cnt[(-b, a)]

num = n - cnt[(0, 0)]
ans = 0
for key in ab:
    if key == (0, 0):
        ans += 1
        continue
        
    a, b = key
    k = num - check[key] if check[key] > 0 else num
    if k > 0:
        ans = (ans + (pow(2, k) - pow(2, k - 1)) % mod) % mod
    check[(-b, a)] -= 1
    num -= 1
    #print(key, ans, num, k)

print(ans)

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

mod=1000000007

n=int(input())
katamuki_list=[]
for i in range(n):
    a, b=map(int, input().split())
    if a==0 and b==0:
        tmp=(0, 0)
    elif a==0:
        tmp=(0, 1)
    elif b==0:
        tmp=(1, 0)
    else:
        gcd=math.gcd(a, b)
        a=a//gcd
        b=b//gcd
    katamuki_list.append((a, b))

katamuki_counter=Counter(katamuki_list)
ans=1
for katamuki_key in list(katamuki_counter.keys()):
    # print(katamuki_key)
    katamuki_value=katamuki_counter[katamuki_key]
    if (0, 0)==katamuki_key:
        pass
    elif (0, 1)==katamuki_key or (1, 0)==katamuki_key:
        pass
    else:
        if katamuki_value!=0:
            reverse_0=(-katamuki_key[1], katamuki_key[0])
            reverse_1=(katamuki_key[1], -katamuki_key[0])
            reverse_count=katamuki_counter[reverse_0]+katamuki_counter[reverse_1]
            # print(reverse_count)
            ans=ans*(pow(2, katamuki_value, mod)-1+pow(2, reverse_count, mod)-1+1)%mod
            # print(ans)
            katamuki_counter[reverse_0]=0
            katamuki_counter[reverse_1]=0
ans=ans-1 #全て選ばないという場合を引く
ans=ans*(pow(2, katamuki_counter[(1, 0)], mod)-1+pow(2, katamuki_counter[(0, 1)], mod)-1+1)
ans=ans+katamuki_counter[(0, 0)]

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import math
    import collections
    N = int(input())

    mod = 10**9+7
    AB = [tuple(map(int, input().split())) for i in range(N)]

    d = collections.defaultdict(set)
    i = 0
    ans2 = 0
    for a, b in AB:
        if a == 0 and b == 0:
            N -= 1
            ans2 += 1
            continue
        g = math.gcd(a, b)
        if g != 0:
            a = a // g
            b = b // g
        if a < 0 and b < 0:
            a = -a
            b = -b
        d[(a, b)].add(i)
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for a, b in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])
        if l1:
            s2 = set()
            if (-b, a) in d:
                s2 |= d[(-b, a)]
            if (b, -a) in d:
                s2 |= d[(b, -a)]
            s2 -= d[(a, b)]
            l2 = len(s2)
            if l2:
                ans *= dd[l1] + dd[l2] - 1
                N -= l1 + l2
                ans %= mod
                r.add((-b, a))
                r.add((b, -a))
            else:
                continue
    if N:
        ans *= dd[N]

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


main()

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
m=[]
groups=[]
INF=10**27
a0only=0
b0only=0
both0=0
negativecounter=0
for i in range(n):
  a,b=map(int,sys.stdin.readline().split())
  if b==0:
    if a==0:
      both0+=1
    else:
      b0only+=1
  elif a==0:
    a0only+=1
  else:
    m.append([a,b,a/b,-b/a])
  if a*b<0:
    negativecounter+=1
m1=sorted(m, key=lambda student: student[2])
m2=sorted(m, key=lambda student: student[3])
backcounter=0
done=set()
for i in range(len(m)):
  a=m1[i][0]
  b=m1[i][1]
  if len(groups)>0:
    if groups[-1][0]*b==a*groups[-1][1]:
      groups[-1][2]+=1
    else:
      if i in done:
        groups.append([a,b,1,0,0])
      else:
       	groups.append([a,b,1,0,-1])
  else:
    if i in done:
      groups.append([a,b,1,0,0])
    else:
      groups.append([a,b,1,0,-1])
  backcounter=max(0,backcounter-100)
  while backcounter<len(m) and ((a*m2[backcounter][0]>=-b*m2[backcounter][1] and b*m2[backcounter][0]>0) or (a*m2[backcounter][0]<=-b*m2[backcounter][1] and b*m2[backcounter][0]<0)):
    if m2[backcounter][0]*a+m2[backcounter][1]*b==0:
      groups[-1][3]+=1
      groups[-1][4]=0
    backcounter+=1
ans=1
donenumbers=[0]*len(groups)
for i in range(len(groups)):
  a=groups[i][0]
  b=groups[i][1]
  c=groups[i][2]
  d=groups[i][3]
  if groups[i][4]==0 and a*b<0:
    continue
  ans=(ans*((2**c+2**d)-1))%(10**9+7)
ans=(ans*(((2**a0only+2**b0only)-1+both0))%(10**9+7))
print(ans-1)

Submission status: Wrong Answer

Solution code:
import math

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

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a /= gcd
        b /= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
bin_n = [2]
for i in range(len(bin(n)) - 3):
    temp = bin_n[-1]
    temp = temp ** 2
    temp %= mod
    bin_n.append(temp)
def beki2(n):
    num = bin(n)
    temp = 1
    for i in range(len(num) - 2):
        if num[-i-1] == "1":
            temp *= bin_n[i]
            temp %= mod
    return temp

ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (beki2(num2) + beki2(num3) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= beki2(n)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math

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

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a /= gcd
        b /= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
bin_n = [2]
for i in range(len(bin(n)) - 3):
    temp = bin_n[-1]
    temp = temp ** 2
    temp %= mod
    bin_n.append(temp)
def beki2(n):
    num = bin(n)
    temp = 1
    for i in range(len(num) - 2):
        if num[-i-1] == "1":
            temp *= bin_n[i]
            temp %= mod
    return temp

ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (beki2(num2) + beki2(num3) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= beki2(n)
temp3 -= 1
temp3 %= mod
ans += temp3
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ab = li2(N)
mod = 10**9+7

d = defaultdict(int)

for i in range(N):
    if ab[i][1] != 0:
        d[ab[i][0] / ab[i][1]] += 1
    else:
        d[10**18+1] += 1

d_l = sorted(d.items(), key=lambda x:x[0])

cnt = 1
for k, v in d_l:
    if k == 0:
        if d[10**18+1]:
            cnt = (cnt * ((2**v-1) + (2**d[10**18+1]-1) + 1)) % mod
        else:
            cnt = ((v+1) * cnt) % mod
    elif k == 10**18+1:
        if d[0]:
            continue
        cnt = ((v+1) * cnt) % mod
    elif k > 0 :
        if not d[-1/k]:
            cnt = ((v+1) * cnt) % mod
    elif d[-1/k]:
        cnt = (cnt * ((2**v-1) + (2**d[-1/k]-1) + 1)) % mod
    else:
        cnt = ((v+1) * cnt) % mod

print(cnt - 1)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
m=[]
groups=[]
INF=10**27
a0only=0
b0only=0
both0=0
negativecounter=0
for i in range(n):
  a,b=map(int,sys.stdin.readline().split())
  if b==0:
    if a==0:
      both0+=1
    else:
      b0only+=1
  elif a==0:
    a0only+=1
  else:
    m.append([a,b,a/b,-b/a])
  if a*b<0:
    negativecounter+=1
m1=sorted(m, key=lambda student: student[2])
m2=sorted(m, key=lambda student: student[3])
backcounter=0
done=set()
for i in range(len(m)):
  a=m1[i][0]
  b=m1[i][1]
  if len(groups)>0:
    if groups[-1][0]*b==a*groups[-1][1]:
      groups[-1][2]+=1
    else:
      if i in done:
        groups.append([a,b,1,0,0])
      else:
       	groups.append([a,b,1,0,-1])
  else:
    if i in done:
      groups.append([a,b,1,0,0])
    else:
      groups.append([a,b,1,0,-1])
  while backcounter<len(m) and ((a*m2[backcounter][0]>=-b*m2[backcounter][1] and b*m2[backcounter][0]>0) or (a*m2[backcounter][0]<=-b*m2[backcounter][1] and b*m2[backcounter][0]<0)):
    if m2[backcounter][0]*m1[i][0]+m2[backcounter][1]*m1[i][1]==0:
      groups[-1][3]+=1
      groups[-1][4]=0
    backcounter+=1
ans=1
donenumbers=[0]*len(groups)
for i in range(len(groups)):
  a=groups[i][0]
  b=groups[i][1]
  c=groups[i][2]
  d=groups[i][3]
  if groups[i][4]==0 and a*b<0:
    continue
  ans=(ans*((2**c+2**d)-1))%(10**9+7)
ans=(ans*(((2**a0only+2**b0only)-1+both0))%(10**9+7))
print(ans-1)

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, radians, sin, cos

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = defaultdict(int)
zero = 0

tmp = []
for a, b in AB:
    if a * b == 0:
        tmp.append([a, b])
    else:
        gcd_ab = gcd(abs(a), abs(b))
        if a < 0: a,  b = - a, - b 
        tmp.append([a // gcd_ab, b // gcd_ab])
AB = tmp
#print(AB)

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

answer = 1
rest = N

answer *= zero + 1
answer %= MOD
rest -= zero

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

answer *= pow(2, rest, MOD)
answer -= 1
answer %= MOD

print(answer)