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 collections import defaultdict


def fraction(a, b):
    """a/b を既約分数 numer/denom として求める
    denom は必ず非負整数
    numer = denom = 0 のときは numer/denom = 0/0
    numer = 0 のときは numer/denom = 0/1
    denom = 0 のときは numer/denom = 1/0
    """
    numer, denom = a, b
    if numer == denom == 0:
        return 0, 0
    elif numer == 0:
        return 0, 1
    elif denom == 0:
        return 1, 0

    # GCD(a, b) を計算して約分する
    while b:
        a, b = b, a % b
    gcd_ab = a
    numer = numer // gcd_ab
    denom = denom // gcd_ab

    if denom < 0:  # denom は必ず非負整数
       numer, denom = -numer, -denom
    return numer, denom
  

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7


memo = defaultdict(int)
for i in range(n):
    a, b = info[i]
    memo[fraction(a, b)] += 1

cnt_00 = 0
cnt_n0 = 0 
cnt_d0 = 0
ans = 1
used = set()
for frac in memo:
    numer, denom = frac
    if numer == 0 and denom == 0:
        cnt_00 += memo[frac]
        continue
    elif numer == 0:
        cnt_n0 += memo[frac]
        continue
    elif denom == 0:
        cnt_d0 += memo[frac]
        continue
    
    if frac in used:
        continue
    rev_num, rev_den = -denom, numer
    if rev_den < 0:
        rev_num, rev_den = -rev_num, -rev_den

    cnt1 = memo[frac]
    cnt2 = 0
    if (rev_num, rev_den) in memo:
        cnt2 = memo[(rev_num, rev_den)]
    tmp = (pow(2, cnt1, MOD) - 1) + (pow(2, cnt2, MOD) - 1) + 1
    ans *= tmp
    used.add((rev_num, rev_den))

ans = ans + cnt_00 + cnt_n0 * ans + cnt_d0 * ans + cnt_n0 * cnt_d0 * ans
print((ans - 1) % MOD)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a > 0 and a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(a, b):
    if a == 0 and b == 0:
        return (1, 0, 0)
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = -1
    elif b == 0 and a < 0:
        s = -1
    else:
        s = 1 if a * b >= 0 else -1
    if b == 0:
        a = 1
        s = 1
    a = abs(a)
    b = abs(b)
    return s, a, b


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

if len(d.keys()) == 0:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(a, b):
    if a == 0 and b == 0:
        return 1, 0, 0
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = -1
    elif b == 0 and a < 0:
        s = -1
    else:
        s = 1 if a * b >= 0 else -1
    if b == 0:
        a = 1
        s = 1
    a = abs(a)
    b = abs(b)
    return s, a, b


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [[int(_) for _ in input().split()] for i in range(N)]

from math import gcd

def normalize(x, y):
    if x == 0 and y == 0:
        return (0, 0)
    if x == 0:
        return (0, 1)
    if y == 0:
        return (1, 0)
    if x < 0:
        x, y = -x, -y
    d = gcd(x, y)
    return (x // d, y // d)

def rev(x, y):
    x, y = -y, x
    if x < 0:
        x, y = -x, -y
    return x, y

xs = {}

for a, b in AB:
    if a == 0 and b == 0:
        continue
    nab = normalize(a, b)
    rab = rev(*nab)
    if nab in xs:
        xs[nab][0] += 1
    elif rab in xs:
        xs[rab][1] += 1
    else:
        xs[nab] = [1, 0]

M = 1000000007

result = 1
for ab, nm in xs.items():
    k = (pow(2, nm[0], M) + pow(2, nm[1], M) - 1) % M
    result = (result * k) % M

print((result - 1) % M)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd


def normal(x, y):
    if x == 0:
        return (0, 1)
    elif y == 0:
        return (1, 0)
    g = gcd(x, y)
    x, y = x // g, y // g
    if x < 0:
        x, y = -x, -y
    return (x, y)


def orthogonal(T):
    if T[0] == 0:
        return (1, 0)
    elif T[1] == 0:
        return (0, 1)
    if T[1] > 0:
        return (T[1], -T[0])
    else:
        return (-T[1], T[0])


N = int(input())
C = defaultdict(int)
z = 0
for i in range(N):
    Ai, Bi = map(int, input().split())
    if Ai == Bi == 0:
        z += 1
        continue
    n = normal(Ai, Bi)
    C[n] += 1

MOD = 1000000007
B = [1] * (N + 1)
for i in range(1, N + 1):
    B[i] = B[i - 1] * 2 % MOD

ans = 1
calc = set()
for n, c in C.items():
    if n in calc:
        continue
    a = B[c]
    calc.add(n)
    no = orthogonal(n)
    if no in C:
        co = C[no]
        a += B[co] - 1
        calc.add(no)
    ans *= a
    ans %= MOD
print(ans - 1 + z)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

mod=10**9+7

n=int(input())

dp=defaultdict(int)
dm=defaultdict(int)
ans=0
cp=[]
cm=[]
az=0
bz=0
cz=0
mod2=10**20+9
for i in range(n):
    a,b=map(int,input().split())
    if a*b>0:
        c=gcd(a,b)
        a=abs(a)//c
        b=abs(b)//c
        if dp[(a,b)]==0:
            cp.append([a,b])
        dp[(a,b)]+=1
    elif a*b<0:
        c=gcd(a,b)
        a=abs(a)//c
        b=abs(b)//c
        dm[(a,b)]+=1
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1

kk=pow(2,az,mod)+pow(2,bz,mod)-1
if kk>0:
    ans=kk
else:
    ans=1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[(a,b)],mod)+pow(2,dm[(b,a)],mod)-1
    ans%=mod
    z-=(dp[(a,b)]+dm[(b,a)])
# print(z)
ans*=pow(2,z,mod)

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
data = [list(map(int,input().split())) for i in range(N)]
mod = 10**9+7
ans = 0

from math import gcd

A = []

for i in range(N):
    if data[i][0] == 0 and data[i][1] == 0:  #(0,0)の場合は以降取り除いて考える
        ans += 1
    else:                                 #各々の成分をgcdで割り、第1成分が非負になるように調整
        if data[i][0] < 0:
            data[i][0] *= -1
            data[i][1] *= -1
        g = gcd(data[i][0],data[i][1])
        data[i][0] //= g
        data[i][1] //= g
        if data[i][0] == 0:
            A.append((0,1))
        elif data[i][1] > 0:
            A.append((data[i][0],data[i][1]))
        elif data[i][1] == 0:
            A.append((1,0))
        else:
            A.append((data[i][0],data[i][1]))


from collections import Counter

C = Counter(A)
D = []             #仲が悪いイワシの数の組

for i,j in list(C.keys()):
    if j <= 0:
        continue
    else:
        if j == 0:
            if C[(0,1)] > 0:
                D.append((C[(1,0)],C[(0,1)]))
        else:
            if C[(j,-i)] > 0:
                D.append((C[(i,j)],C[(j,-i)]))

r = 0  #仲が悪くなり得るイワシの数
for i,j in D:
    r += i+j

a = 1  #仲が悪くなり得るイワシたちの選び方
for i,j in D:
    a = (a*(pow(2,i,mod)+pow(2,j,mod)-1)) % mod

a = (a*pow(2,len(A)-r,mod)) % mod  #仲が悪くなり得ないイワシたちの選び方

ans += a-1  #全部選ばないものを除く

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def fraction(a, b):
    """a/b を既約分数 numer/denom として求める
    denom は必ず非負整数
    numer = denom = 0 のときは numer/denom = 0/0
    numer = 0 のときは numer/denom = 0/1
    denom = 0 のときは numer/denom = 1/0
    """
    numer, denom = a, b
    if numer == denom == 0:
        return 0, 0
    elif numer == 0:
        return 0, 1
    elif denom == 0:
        return 1, 0

    # GCD(a, b) を計算して約分する
    while b:
        a, b = b, a % b
    gcd_ab = a
    numer = numer // gcd_ab
    denom = denom // gcd_ab

    if denom < 0:  # denom は必ず非負整数
       numer, denom = -numer, -denom
    return numer, denom
  

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7


memo = defaultdict(int)
for i in range(n):
    a, b = info[i]
    memo[fraction(a, b)] += 1

cnt_00 = 0
cnt_n0 = 0 
cnt_d0 = 0
ans = 1
used = set()
for frac in memo:
    numer, denom = frac
    if numer == 0 and denom == 0:
        cnt_00 += 1
        continue
    elif numer == 0:
        cnt_n0 += 1
        continue
    elif denom == 0:
        cnt_d0 += 1
        continue
    
    if frac in used:
        continue
    rev_num, rev_den = -denom, numer
    if rev_den < 0:
        rev_num, rev_den = -rev_num, -rev_den

    cnt1 = memo[frac]
    cnt2 = 0
    if (rev_num, rev_den) in memo:
        cnt2 = memo[(rev_num, rev_den)]
    tmp = (pow(2, cnt1, MOD) - 1) + (pow(2, cnt2, MOD) - 1) + 1
    ans *= tmp
    used.add((rev_num, rev_den))

ans = ans + cnt_00 + cnt_n0 * ans + cnt_d0 * ans + cnt_n0 * cnt_d0 * ans
print((ans - 1) % MOD)

Submission status: Wrong Answer

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

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

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

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

if len(d.keys()) == 0:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    MOD = 1000000007
    N = int(input())
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    n00 = 0
    for i in range(N):
        a, b = map(int, input().split())
        # (0, 0) はどのイワシとも仲が悪いので、考慮の対象から外して置き、
        # 後で(0, 0)のイワシの本数分足す
        if a == 0 and b == 0:
            n00 += 1
            continue

        # Bが0の場合、Aが0のイワシであればなんでも仲が悪くなるので、
        # C = 1 / 0 で統一する。
        if b == 0:
            C[(1, 0)] += 1
            continue
        # Aが0の場合、Bが0のイワシであればなんでも仲が悪くなるので、
        # C = 0 / 1 で統一する。
        elif a == 0:
            C[(0, 1)] += 1
            continue
        _gcd = gcd(a, b)
        a = a // _gcd
        b = b // _gcd
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    groups = []
    for c, nc in C.items():
        a, b = c
        # 仲の悪いイワシの個数
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_b = -bad_b
            bad_a = -bad_a
        nBad = C.get((bad_a, bad_b), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        if nBad == 0:
            groups.append(2 ** nc)
            continue
        # 中の悪いグループがすでに調査済みなら何もしない
        elif flag[(bad_a, bad_b)]:
            continue

        # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
        # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
        # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
        # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
        groups.append((2 ** nc) + (2 ** nBad) - 1)
        flag[(a, b)] = True

    # 各グループの選択肢を掛け合わせ、-1する
    # (全て選択しないパターンを除外する)
    ans = 1
    for g in groups:
        ans = (ans * g) % MOD
    # -1 するついでに(0, 0) のイワシから1本以上選ぶ場合の数も足しておく
    ans = (ans + n00 - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

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 fractions import Fraction

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            '''
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
            '''
            cnd[ratio] = [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]%mod+2**item[1]%mod-1)%mod
        ans %= mod
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

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/b>=-m2[backcounter][1]/m2[backcounter][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:
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 fractions import Fraction

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
mod = 10**9 + 7
cou = 0
pdic = {}
kan = []
betu = [0,0,0]

for i in range(n):
    a , b = map(int,input().split())
    if a*b != 0:
        g = math.gcd(abs(a),abs(b))
        if a*b > 0:
            m = 1
        elif a*b < 0:
            m = -1
        p = (m*abs(a)/g,abs(b)/g)
        q = ((-m)*abs(b)/g,abs(a)/g)
        if pdic.get(q,-1) != -1:
            kan[pdic[q]][1] += 1
        elif pdic.get(p,-1) == -1:
            pdic[p] = cou
            kan.append([1,0])
            cou += 1
        elif pdic.get(p,-1) != -1:
            kan[pdic[p]][0] += 1
    elif a*b == 0:
        if a == 0 and b == 0:
            betu[2] += 1
        elif a == 0:
            betu[0] += 1
        elif b == 0:
            betu[1] += 1
        
        
ans = 1
for i in range(len(kan)):
    ans *= (pow(2,kan[i][0],mod) + pow(2,kan[i][1],mod) - 1) % mod
    ans %= mod
ans *= (pow(2,betu[0],mod) + pow(2,betu[1],mod) - 1) % mod
print((ans-1+betu[2])%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if (a > 0 and b >= 0) or (a < 0 and b <= 0):
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][0]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

N = int(input())
A = [0]*N
B = [0]*N
C = [[0]*2 for _ in range(N)]
zero = 0
for i in range(N):
    A[i],B[i] = map(int,(input().split()))
    if A[i] == 0 and B[i] == 0:
        C[i] = (0,0)
        zero += 1
    elif B[i] == 0:
        C[i] = (A[i],B[i])
    elif B[i] > 0:
        g = math.gcd(A[i],B[i])
        C[i] = (A[i]//g,B[i]//g)
    else:
        g = math.gcd(A[i],B[i])
        C[i] = (-A[i]//g,-B[i]//g)

d = defaultdict(int)

for i in range(N):
    if C[i] != (0,0):
        d[C[i]] += 1

ans = 1
for k in d.keys():
    if k[0] >= 0:
        if (-k[1],k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(-k[1],k[0])],MOD) - 1
            d[k],d[(-k[1],k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)
    else:
        if (k[1],-k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(k[1],-k[0])],MOD) -1
            d[k],d[(k[1],-k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

    flip = 0
    while not (a >= 0 and b >= 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    MOD = 1000000007
    N = int(input())
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    for i in range(N):
        a, b = map(int, input().split())
        # Bが0の場合、Aが0のイワシであればなんでも仲が悪くなるので、
        # C = 1 / 0 で統一する。
        if b == 0:
            C[(1, 0)] += 1
            continue
        # Aが0の場合、Bが0のイワシであればなんでも仲が悪くなるので、
        # C = 0 / 1 で統一する。
        elif a == 0:
            C[(0, 1)] += 1
            continue
        _gcd = gcd(a, b)
        a = a // _gcd
        b = b // _gcd
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    groups = []
    for c, nc in C.items():
        a, b = c
        # 仲の悪いイワシの個数
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_b = -bad_b
            bad_a = -bad_a
        nBad = C.get((bad_a, bad_b), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        if nBad == 0:
            groups.append(2 ** nc)
            continue
        # 中の悪いグループがすでに調査済みなら何もしない
        elif flag[(bad_a, bad_b)]:
            continue

        # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
        # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
        # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
        # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
        groups.append((2 ** nc) + (2 ** nBad) - 1)
        flag[(a, b)] = True

    # 各グループの選択肢を掛け合わせ、-1する
    # (全て選択しないパターンを除外する)
    ans = 1
    for g in groups:
        ans = (ans * g) % MOD
    ans = (ans - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd

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

    flip = 0
    while a*b < 0 or (a <= 0 and b <= 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Wrong Answer

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

def main():
    N = int(input())
    MOD = 1000000007
    d = {}
    
    pd = [1]
    for _ in range(N):
        pd.append((pd[-1]*2)%MOD)

    zero = 0
    ab = [0,0]
    for i in range(N):
        a,b = map(int,input().split())
        if a == b == 0:
            zero += 1
        elif a*b == 0:
            if a == 0:
                ab[0] += 1
            else:
                ab[1] += 1
        else:
            gcd = math.gcd(abs(a),abs(b))
            a //= gcd
            b //= gcd
            if a < 0 and b < 0:
                a *= -1
                b *= -1
            elif a < 0 and b > 0:
                a,b = b,a
            elif a > 0 and b < 0:
                a *= -1
                b *= -1
                a,b = b,a
            if (a,b) not in d:
                d[(a,b)] = 1
            else:
                d[(a,b)] += 1

    ans = 1
    use = {}
    
    for k,v in d.items():
        a,b = k
        if (a,-b) in d:
            if (a,-b) in use:
                continue
            ret = pd[d[(a,b)]]+pd[d[(a,-b)]]-1
            ans *= ret
            use[(a,b)] = 1
            use[(a,-b)] = 1
        else:
            ret = pd[d[(a,b)]]
            ans *= ret
            use[(a,b)] = 1

    ret = pd[ab[0]]+pd[ab[1]]-1
    ans *= ret
    ans += zero
    
    print(ans-1)
    
if __name__ == "__main__":
    main()