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:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
A, B = [], []
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    A.append(a)
    B.append(b)
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add((r, -1 / r))
        else:
            rpairs.add((-1 / r, r))
    ans = 1
    for (r1, r2) in rpairs:
        p = pow(2, cnt_r[r1], MOD) + pow(2, cnt_r[r2], MOD) - 1
        ans *= p % MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans += pow(2, cnt_ab0, MOD)
    return (ans - 2) % MOD


if __name__ == "__main__":
    print(solve())

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N = int(rl())
    AB = tuple(tuple(map(int, rl().split())) for _ in range(N))
    
    zero_pare = 0
    zero_a, zero_b = 0, 0
    counter = defaultdict(int)
    for a, b in AB:
        if a == b == 0:
            zero_pare += 1
        elif a == 0:
            zero_a += 1
        elif b == 0:
            zero_a += 1
        else:
            cd = gcd(a, b)
            a, b = a // cd, b // cd
            if b < 0:
                a, b = -a, -b
            counter[(a, b)] += 1
    
    ans = pow(2, zero_a, MOD) + pow(2, zero_b, MOD) - 1
    memo = set()
    for a, b in list(counter):
        if (a, b) in memo:
            continue
        pa, pb = -b, a
        if pb < 0:
            pa, pb = -pa, -pb
        memo.add((a, b))
        memo.add((pa, pb))
        ans *= pow(2, counter[(a, b)], MOD) + pow(2, counter[(pa, pb)], MOD) - 1
        ans %= MOD
    
    ans = (ans + zero_pare - 1) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict
P = 13 ** 8 + 18
mod = 10 ** 9 + 7
N = int(input())
D = defaultdict(int)
C00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        C00 += 1
    elif a == 0:
        D[-1] += 1
    elif b == 0:
        D[-2] += 1
    else:
        x = a * pow(b, P - 2, P) % P
        D[x] += 1
ans = 1
for x in D:
    y = pow(-x, P - 2, P) if x > 0 else -3 - x
    if y in D and x > y: continue
    ans *= 1 + pow(2, D[x], mod) - 1 + pow(2, (D[y] if y in D else 0), mod) - 1
    ans %= mod
print((ans + C00 - 1) % mod)

Submission status: Wrong Answer

Solution code:
import math
import collections
from collections import defaultdict
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=10**9+7

L=[]
ct0=0
for i in range(n):
  if l[i][0]==0 and l[i][1]==0:
    ct0+=1
  elif l[i][0]==0:
    L.append((0,1))
  elif l[i][1]==0:
    L.append((1,0))
  elif l[i][0]<0:
    L.append((-l[i][0]//math.gcd(l[i][0],l[i][1]),-l[i][1]//math.gcd(l[i][0],l[i][1])))
  else:
    L.append((l[i][0]//math.gcd(l[i][0],l[i][1]),l[i][1]//math.gcd(l[i][0],l[i][1])))

ans=1
d=set()
c=collections.Counter(L)
for i in c.keys():
  if i[0]==0:
    x=(1,0)
  elif i[1]==0:
    x=(0,1)
  elif i[1]<0:
    x=(-i[1],i[0])
  else:
    x=(i[1],-i[0])
  if i not in d:
    ans*=pow(2,c[i],mod)+pow(2,c[x],mod)-1
    ans%=mod
    d.add(x)
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC168
# Problem No.: E
# Solver:      JEMINI
# Date:        20200517

import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 2 ** (len(zpList) + len(znList)) % modVal + 2 ** (len(pzList) + len(nzList)) % modVal - 1
    zAns = zAns % modVal
    ans = zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
mod = 10**9+7
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = defaultdict(int)
ans = 0
for i, (A, B) in enumerate(AB):
    if A == B == 0:
        ans += 1
        continue
    elif B == 0:
        cnt[(1, 0)] += 1
        continue
    elif A == 0:
        cnt[(0, 1)] += 1
        continue
    g = gcd(A, B)
    a = A//g
    b = B//g
    if b < 0:
        cnt[(-a, -b)] += 1
    else:
        cnt[(a, b)] += 1
f = 1
p = defaultdict(int)
ks = list(cnt.keys())
cnt2 = defaultdict(int)
for k in ks:
    a, b = k
    v = cnt[k]
    if v <= 0:
        continue
    if a > 0:
        p[k] = pow(2, v+cnt[-b, a], mod)
        cnt2[k] = (cnt[k], cnt[(-b, a)])
        cnt[(-b, a)] = -1
    else:
        p[k] = pow(2, v+cnt[b, -a], mod)
        cnt2[k] = (cnt[k], cnt[(b, -a)])
        cnt[(b, -a)] = -1
    f = f * p[k] % mod
for k in cnt2:
    f = f * pow(p[k], mod-2, mod) % mod
    ans += (cnt2[k][0]+cnt2[k][1]) * f % mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC168
# Problem No.: E
# Solver:      JEMINI
# Date:        20200517

import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 2 ** (len(zpList) + len(znList)) + 2 ** (len(pzList) + len(nzList)) - 1
    ans *= zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

mod = 10 ** 9 + 7
n = int(input())
iwashi = dict()
origin_iwashi = 0
for _ in range(n):
  a, b = map(int, input().split())
  if a == b == 0:
    origin_iwashi += 1
  elif a == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][1] += 1
    else:
      iwashi[(1, 0)] = [0, 1]
  elif b == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][0] += 1
    else:
      iwashi[(1, 0)] = [1, 0]
  else:
    if b < 0:
      a, b = -a, -b
    g = gcd(a, b)
    a //= g
    b //= g
    if a > 0:
      if (a, b) in iwashi:
        iwashi[(a, b)][0] += 1
      else:
        iwashi[(a, b)] = [1, 0]
    else:
      if (b, -a) in iwashi:
        iwashi[(b, -a)][1] += 1
      else:
        iwashi[(b, -a)] = [0, 1]
count = 1
for i, j in iwashi.values():
  tmp = pow(2, i, mod) + pow(2, j, mod) - 1
  count = count * tmp % mod
count = (count + pow(2, origin_iwashi, mod) - 2) % mod
print(count)

Submission status: Wrong Answer

Solution code:
# Contest No.: ABC168
# Problem No.: E
# Solver:      JEMINI
# Date:        20200517

import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 1
    length = (len(zpList) + len(znList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns *= temp
        zAns = zAns % modVal

    zAns2 = 1
    length = (len(pzList) + len(nzList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns2 *= temp
        zAns2 = zAns2 % modVal
    zAns += zAns2 - 1
    ans *= zAns

    groupCnt = 0
    if znList or zpList or nzList or npList:
        groupCnt += 1

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
            groupCnt += 1
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
            groupCnt += 1
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
            groupCnt += 1
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
            groupCnt += 1
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    if groupCnt > 1:
        ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

a_b = [0 for i in range(n)]
m_b_a = [0 for i in range(n)]

# a_b_value_count = {} # a_b values
# m_b_a_value_count = {} # a_b values

a_b_value_indices = {} # a_b values
m_b_a_value_indices = {} # a_b values

# used_a_b_keys = set()
used = [False for _ in range(n)]

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

	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
	else:
		if a[i] == 0:
			a_b[i] = 0
			m_b_a[i] = INF
		elif b[i] == 0:
			a_b[i] = INF
			m_b_a[i] = 0
		else:
			a_b[i] = a[i] / b[i]
			m_b_a[i] = -b[i] / a[i]

		# a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		a_b_value_indices[a_b[i]] = a_b_value_indices.get(a_b[i], []) + [i]

		# m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1
		m_b_a_value_indices[m_b_a[i]] = m_b_a_value_indices.get(m_b_a[i], []) + [i]

ans = 1
for i in range(n):
	if not used[i]:
		# not connected
		if a_b[i] not in m_b_a_value_indices:
			ans *= pow(2, len(a_b_value_indices[a_b[i]]), MODULO)
			ans %= MODULO
			for j in a_b_value_indices[a_b[i]]:
				used[j] = True
		else:
			s = len(a_b_value_indices[a_b[i]])
			t = len(m_b_a_value_indices[a_b[i]])
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO

			for j in a_b_value_indices[a_b[i]]:
				used[j] = True
			for j in m_b_a_value_indices[a_b[i]]:
				used[j] = True

			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)


# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 1
    length = (len(zpList) + len(znList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns *= temp
        zAns = zAns % modVal

    zAns2 = 1
    length = (len(pzList) + len(nzList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns2 *= temp
        zAns2 = zAns2 % modVal
    zAns += zAns2 - 1
    ans *= zAns

    groupCnt = 0
    if znList or zpList or nzList or npList:
        groupCnt += 1

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        groupCnt += 1
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    if groupCnt > 1:
        ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        if a != 0 and b != 0:
            g = gcd(a, b) * a // abs(a)
        elif a != 0:
            g = a
        else:
            g = b
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD

print(e_bullet())

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict

MOD = 10**9+7
N = int(input())
d = defaultdict(int)
zero = [0, 0, 0]
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero[0] += 1
        continue
    if a == 0:
        zero[1] += 1
        continue
    if b == 0:
        zero[2] += 1
        continue

    s = -1 if (a*b) < 0 else 1
    g = gcd(a, b)
    a //= g
    b //= g

    d[(s, abs(a), abs(b))] += 1

ans = 1
for (s, a, b), c1 in d.items():
    if c1 == 0:
        continue
    k = (-s, b, a)
    if k in d:
        c2 = d[k]
        ans *= pow(2, c1, MOD) + pow(2, c2, MOD)-1
        ans %= MOD
        d[k] = 0
    else:
        ans *= pow(2, c1, MOD)
        ans %= MOD

ans *= pow(2, zero[1], MOD)+pow(2, zero[2], MOD)-1
ans %= MOD

ans += zero[0]
ans -= 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 1
    length = (len(zpList) + len(znList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns *= temp
        zAns = zAns % modVal

    zAns2 = 1
    length = (len(pzList) + len(nzList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns2 *= temp
        zAns2 = zAns2 % modVal
    zAns += zAns2 - 1
    ans *= zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        if a != 0 and b != 0:
            g = gcd(a, b)
        elif a != 0:
            g = a
        else:
            g = b
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Submission status: Wrong Answer

Solution code:
#!python3

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

# input
N = int(input())
AB = [LI() for _ in range(N)]

MOD = 10 ** 9 + 7


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


def create_pairs():
    z = 0
    d = {}
    for a, b in AB:
        # irre
        if a == 0 and b == 0:
            z += 1
            continue
        if a == 0:
            b = 1
        elif b == 0:
            a == 1
        else:
            m = abs(gcd(a, b))
            a, b = a // m, b // m
        
        # 180
        if b < 0:
            a, b = -a, -b

        if a > 0:
            t = (a, b)
            i = 0
        else:
            t = (b, -a)
            i = 1
        if t in d:
            d[t][i] += 1
        else:
            d[t] = [0, 0]
            d[t][i] = 1
    
    return d, z


def main():
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(1, N + 1):
        p2[i] = p2[i - 1] * 2 % MOD
    
    d, z = create_pairs()
    ans = 1
    for x, y in d.values():
        v = p2[x] + p2[y] - 1
        ans = ans * v % MOD

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def comp(a,b):
    if a[1]*b[1]+a[0]*b[0] != 0:
        return(True)
    else:
        return(False)

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

ans = 0                
s = 0
while s < n:
    d = 0
    for i in l[s+1:]:
        if comp(l[0],i) == True:
            d += 1
        else:
            continue
        
    ans+=(2**d)
    s += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import heapq

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 1
    length = (len(zpList) + len(znList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns *= temp
        zAns = zAns % modVal

    zAns2 = 1
    length = (len(pzList) + len(nzList))
    while length > 0:
        cnt = 1
        temp = 2
        while 2 * cnt <= length:
            temp *= temp
            temp = temp % modVal
            cnt *= 2
        length -= cnt
        zAns2 *= temp
        zAns2 = zAns2 % modVal
    zAns += zAns2 - 1
    ans *= zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        ratio = i[0] / i[1]
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        ratio = -i[1] / i[0]
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    print(ans)
    return

if __name__ == "__main__":
    main()