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:
from math import gcd
from collections import defaultdict
N = int(input())
MOD = 10 ** 9 + 7

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


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

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

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

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

Submission status: Wrong Answer

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

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


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

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

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

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

Submission status: Wrong Answer

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

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

#import numpy as np

from math import gcd
from collections import defaultdict

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

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

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


	s=set()

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

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

MOD = 10 ** 9 + 7

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
import sys


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

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

ans -= 1
ans += zero

print(ans % MOD)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import defaultdict

input = sys.stdin.readline
mod = 1000000007

n = int(input())

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

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

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

n -= zero
ans = 1

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

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

Submission status: Wrong Answer

Solution code:
import math
import sys
from collections import defaultdict

input = sys.stdin.readline
mod = 1000000007

n = int(input())

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

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

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

ans = zero + 1
ans %= mod
n -= zero

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

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

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

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

answer -= 1
answer += zero
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

cnt = Counter(ab)
answer = 1

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

answer -= 1
answer += zero
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import defaultdict

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

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

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

answer = 1

for (i, j) in tuple(ab.keys()):
    n = ab[(i, j)]
    if j < 0:
        m = ab[(-j, i)]
    else:
        m = ab[(j, -i)]
    if m == -1:
        continue
    if m != 0:
        answer = (answer * (pow(2, n, mod) + pow(2, m, mod) - 1)) % mod
        ab[(i, j)] = -1
    else:
        answer = (answer * pow(2, n, mod)) % mod

answer -= 1
answer += zero
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
from collections import Counter

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

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

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

cnt = Counter(ab)
answer = 1

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

answer -= 1
answer += zero
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

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

N, *AB = map(int, read().split())
mod = 10 ** 9 + 7
A = np.array(AB[::2], np.int64)
B = np.array(AB[1::2], np.int64)
idx = np.nonzero((A != 0) & (B != 0))[0]
if len(idx) == 0:
    print(N)
    exit()
zeros = N - len(idx)
answer = 0
A = A[idx]
B = B[idx]
g = np.gcd(A, B)
A //= g
B //= g
a = A.tolist()
b = B.tolist()
ab = []

for i, j in zip(a, b):
    if i == 0 and j == 0:
        answer += 1
        continue
    if i == 0:
        j = -1
    if j == 0:
        i = 1
    if i < 0:
        ab.append((-i, -j))
    else:
        ab.append((i, j))

cnt = Counter(ab)
if len(cnt) != 0 and answer == 0:
    answer = 1

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

answer -= 1
answer += zeros
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

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

N, *AB = map(int, read().split())
mod = 10 ** 9 + 7
A = np.array(AB[::2], np.int64)
B = np.array(AB[1::2], np.int64)
idx = np.nonzero((A != 0) & (B != 0))[0]
if len(idx) == 0:
    print(N)
    exit()
answer = N - len(idx)
A = A[idx]
B = B[idx]
g = np.gcd(A, B)
A //= g
B //= g
a = A.tolist()
b = B.tolist()
ab = []

for i, j in zip(a, b):
    if i == 0 and j == 0:
        answer += 1
        continue
    if i == 0:
        j = -1
    if j == 0:
        i = 1
    if i < 0:
        ab.append((-i, -j))
    else:
        ab.append((i, j))

cnt = Counter(ab)
if len(cnt) != 0 and answer == 0:
    answer = 1

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

answer -= 1
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

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

N, *AB = map(int, read().split())
mod = 10 ** 9 + 7
A = np.array(AB[::2], np.int64)
B = np.array(AB[1::2], np.int64)
g = np.gcd(A, B)
A //= g
B //= g
a = A.tolist()
b = B.tolist()
ab = []
answer = 0
for i, j in zip(a, b):
    if i == 0 and j == 0:
        answer += 1
        continue
    if i == 0:
        j = -1
    if j == 0:
        i = 1
    if i < 0:
        ab.append((-i, -j))
    else:
        ab.append((i, j))

cnt = Counter(ab)
if len(cnt) != 0 and answer == 0:
    answer = 1

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

answer -= 1
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import Counter

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

N, *AB = map(int, read().split())
A = np.array(AB[::2], np.int64)
B = np.array(AB[1::2], np.int64)
g = np.gcd(A, B)
A //= g
B //= g
a = Counter(A.tolist())
b = Counter(B.tolist())

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

ans = 1
used = defaultdict(int)

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

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

b = 1
used = defaultdict(int)

for (i, j), v in d.items():
    if used[(i, j)]:continue
    buf = 0
    if (-j, i) in d or (j, -i) in d:
        if (-j, i) in d:
            used[(-j, i)] = 1
            buf += pow(2, d[(-j, i)], MOD)+pow(2, v, MOD)-1
        if (j, -i) in d:
            used[(j, -i)] = 1
            buf += pow(2, d[(j, -i)], MOD)+pow(2, v, MOD)-1
        b *= buf
    else:
        b *= pow(2, v, MOD)
    b %= MOD

b *= pow(2, za, MOD)+pow(2, zb, MOD)-1
b %= MOD
b = (b+zall+MOD-1)%MOD
print(b)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

b = 1
used = defaultdict(int)

for (i, j), v in d.items():
    if used[(i, j)]:continue
    buf = 0
    if (-j, i) in d or (j, -i) in d:
        if (-j, i) in d:
            used[(-j, i)] = 1
            buf += pow(2, d[(-j, i)], MOD)+pow(2, v, MOD)-1
        if (j, -i) in d:
            used[(j, -i)] = 1
            buf += pow(2, d[(j, -i)], MOD)+pow(2, v, MOD)-1
        b *= buf
    else:
        b *= pow(2, v, MOD)
    b %= MOD

c = pow(2, za, MOD)+pow(2, zb, MOD)-1
b = (c*b+zall+MOD-1)%MOD
print(b)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

b = 1
used = defaultdict(int)

for (i, j), v in d.items():
    if used[(i, j)]:continue
    buf = 0
    if (-j, i) in d or (j, -i) in d:
        if (-j, i) in d:
            used[(-j, i)] = 1
            buf += pow(2, d[(-j, i)], MOD)+pow(2, v, MOD)-1
        if (j, -i) in d:
            used[(j, -i)] = 1
            buf += pow(2, d[(j, -i)], MOD)+pow(2, v, MOD)-1
        b *= buf
    else:
        b *= pow(2, v, MOD)
    b %= MOD
b = ((zall+pow(2, za, MOD)+pow(2, zb, MOD)-1)*b)%MOD
b -= 1
b %= MOD

print(b)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

b = 1
used = defaultdict(int)

for (i, j), v in d.items():
    if used[(i, j)]:continue
    buf = 0
    if (-j, i) in d or (j, -i) in d:
        if (-j, i) in d:
            used[(-j, i)] = 1
            buf += pow(2, d[(-j, i)], MOD)+pow(2, v, MOD)-1
        if (j, -i) in d:
            used[(j, -i)] = 1
            buf += pow(2, d[(j, -i)], MOD)+pow(2, v, MOD)-1
        b *= buf
    else:
        b *= pow(2, v, MOD)
    b %= MOD
b -= 1
b %= MOD
b = ((zall+pow(2, za, MOD)+pow(2, zb, MOD)-1)*b)%MOD

print(b)

Submission status: Wrong Answer

Solution code:
import sys
import math


stdin = sys.stdin


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


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


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

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

# print(AB_array)

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


# print(plus_dic, minus_dic, fish_count)

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

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

print((ans - 1) % mod)

Submission status: Wrong Answer

Solution code:
import math
mod = 10**9+7
n = int(input())
cnt = {}
cnt_zero = 0

for i in range(n):
  a, b = map(int, input().split())
  if (a, b) == (0, 0):
    cnt_zero += 1
    continue
    
  if b == 0:
    if not (0, 0) in cnt:
      cnt[(0, 0)] = [0, 1]
    cnt[(0, 0)][1] += 1
  if a == 0:
    if not (0, 0) in cnt:
      cnt[(0, 0)] = [1, 0]
    cnt[(0, 0)][0] += 1
  
  waruyatu = math.gcd(a, b)
  a //= waruyatu
  b //= waruyatu
  if a*b > 0:
    a, b = abs(a), abs(b)
    if not (a, b) in cnt:
      cnt[(a, b)] = [1, 0]
    else:
      cnt[(a, b)][0] += 1
  else:
    a, b = abs(a), abs(b)
    if not (b, a) in cnt:
      cnt[(b, a)] = [0, 1]
    else:
      cnt[(b, a)][1] += 1

ans = 1
for key in cnt:
  ans *= pow(2, cnt[key][0], mod) + pow(2, cnt[key][1], mod) - 1
  ans %= mod
ans += cnt_zero
if ans == 0:
  ans = mod-1
else:
  ans -= 1
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math
mod = 10**9+7
n = int(input())
cnt = {}
cnt_zero = 0

for i in range(n):
  a, b = map(int, input().split())
  if (a, b) == (0, 0):
    cnt_zero += 1
    continue
    
  if b == 0:
    if not (0, 0) in cnt:
      cnt[(0, 0)] = [0, 1]
    cnt[(0, 0)][1] += 1
  if a == 0:
    if not (0, 0) in cnt:
      cnt[(0, 0)] = [1, 0]
    cnt[(0, 0)][0] += 1
  
  waruyatu = math.gcd(a, b)
  a //= waruyatu
  b //= waruyatu
  if a*b > 0:
    a, b = abs(a), abs(b)
    if not (a, b) in cnt:
      cnt[(a, b)] = [1, 0]
    else:
      cnt[(a, b)][0] += 1
  else:
    a, b = abs(a), abs(b)
    if not (b, a) in cnt:
      cnt[(b, a)] = [0, 1]
    else:
      cnt[(b, a)][1] += 1

ans = 1
for key in cnt:
  ans *= pow(2, cnt[key][0], mod) + pow(2, cnt[key][1], mod) - 1
  ans %= mod
ans += cnt_zero
ans -= 1
ans %= mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math
mod = 10**9+7
n = int(input())
mp = {}
zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    g = math.gcd(a, b)
    a /= g
    b /= g
    if b < 0:
        a, b = -a, -b
    if b == 0 and a < 0:
        a, b = 1, 0
    rot90 = a <= 0
    if rot90:
        a, b = b, -a
        if (a, b) in mp:
            mp[(a,b)][0] += 1
        else:
            mp[(a,b)] = [1, 0]
    else:
        if (a, b) in mp:
            mp[(a, b)][1] += 1
        else:
            mp[(a, b)] = [0, 1]
ans = 1
for k in mp:
    s = mp[k][0]
    t = mp[k][1]
    now = 1
    now = (now + (pow(2, s, mod) - 1) % mod) % mod
    now = (now + (pow(2, t, mod) - 1) % mod) % mod
    ans = (ans * now) % mod
ans =  (ans -1) % mod
ans = (ans + zero) % mod 
print(ans)