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:
# -*- coding: utf-8 -*-
from fractions import Fraction
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 (0, 0)
    if b == 0:
        return (1, 0)
    f = Fraction(a, b)
    a = f.numerator
    b = f.denominator
    return 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:
        a, b = f(a, b)
        adb[(a, b)] += 1
    M = Mod(1000000007)
    ans = 1 + adb[(0, 0)]
    done = {(0, 0)}
    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)
        elif a == 0:
            s = 1
        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.sub(ans, 1)


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 sys
input = sys.stdin.readline
import math

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = math.gcd(abs(x),abs(y))
    F.append((x,y))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product#accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    mod = 1000000007
    N, *AB = map(int, read().split())
    A_B = []
    INF = float('inf')
    zerozero = 0
    for i in range(N):
        a = AB[2*i]
        b = AB[2*i+1]
        if a== 0 and b == 0:
            zerozero += 1
        elif b == 0:
            A_B.append(INF)
        else:
            tmp = math.gcd(a,b)
            A_B.append((a/tmp)/(b/tmp))
    A_B.sort()
    comb_dict = defaultdict(lambda:[0,0])
    for val in A_B:
        if val == INF:
            comb_dict[0][1] += 1
        elif val <= 0:
            comb_dict[val][0] += 1
        elif val > 0:
            comb_dict[-1/val][1] += 1

    ret = 1
    for _, val_list in comb_dict.items():
        a,b = val_list
        if a == 0 or b == 0:
            ret *= pow(2, max(a,b), mod)
        else:
            ret *= pow(2, a, mod) + pow(2, b, mod) - 1
        ret %= mod
    ret += zerozero-1
    print(ret%mod)



if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product#accumulate, combinations, product
import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
def run():
    mod = 1000000007
    N, *AB = map(int, read().split())
    A_B = []
    INF = float('inf')
    zerozero = 0
    for i in range(N):
        a = AB[2*i]
        b = AB[2*i+1]
        if a== 0 and b == 0:
            zerozero += 1
        elif b == 0:
            A_B.append(INF)
        else:
            A_B.append(a/b)
    A_B.sort()
    comb_dict = defaultdict(lambda:[0,0])
    for val in A_B:
        if val == INF:
            comb_dict[0][1] += 1
        elif val <= 0:
            comb_dict[val][0] += 1
        elif val > 0:
            comb_dict[-1/val][1] += 1

    ret = 1
    for _, val_list in comb_dict.items():
        a,b = val_list
        if a == 0 or b == 0:
            ret *= pow(2, max(a,b), mod)
        else:
            ret *= pow(2, a, mod) + pow(2, b, mod) - 1
        ret %= mod
    ret += zerozero-1
    print(ret%mod)



if __name__ == "__main__":
    run()

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


from  fractions import Fraction

def frac(a, b):
    if a== 0 and b == 0:
        return (0, 0)
    if b == 0:
        return (1, 0)
    f = Fraction(a, b)
    a = f.numerator
    b = f.denominator
    return 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:
        a, b = frac(a, b)
        adb[(a, b)] += 1
    M = Mod(1000000007)
    ans = 1 + adb[(0, 0)]
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        kk = frac(-b, a)
        n = adb[kk]
        done.add(k)
        done.add(kk)
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.sub(ans, 1)


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:
# -*- 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


from  fractions import Fraction

def frac(a, b):
    if a== 0 and b == 0:
        return (0, 0)
    if b == 0:
        return (1, 0)
    f = Fraction(a, b)
    a = f.numerator
    b = f.denominator
    return 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:
        a, b = frac(a, b)
        adb[(a, b)] += 1
    M = Mod(1000000007)
    ans = 1 + adb[(0, 0)]
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        a, b = frac(b, a)
        if b != 0:
            kk = (-a, b)
        else:
            kk = (a, b)
        n = adb[kk]
        done.add(k)
        done.add(kk)
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.sub(ans, 1)


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 sys
#import numpy as np
#import math
from fractions import Fraction
import itertools

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)
input=sys.stdin.readline

ans=1
mod=10**9+7
n0=0
na=nb=0
n=int(input())
v=tuple(tuple(map(lambda x: int(x),input().split())) for _ in range(n))
d={}
for i in range(n):
    b= v[i][1]
    a= v[i][0]
    if b==0 and a==0:
        n0+=1
    elif b==0:
        nb+=1
    elif a==0:
        na+=1
    else:
        if Fraction(a, b) not in d:
            d[Fraction(a, b)]=1
        else:
            d[Fraction(a, b)]+=1
            
for i in d.keys():
    if Fraction(-1,i) in d:
        if i>0:
        	ans*=pow(2,d[Fraction(-1, i)])-1+pow(2,d[i])-1+1
        	ans=ans%mod
    else:
        ans*=pow(2,d[i])
        ans=ans%mod
ans*=pow(2,na)-1+pow(2,nb)-1+1
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

def seiki(x,y):
    tmp=gcd(x,y)
    return (x//tmp,y//tmp)

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a==0 and b==0:
        zero+=1
    elif a*b>0:
        tmp=seiki(abs(a),abs(b))
        pp[tmp]+=1
    elif a==0:
        pp[(1,0)]+=1
    elif b==0:
        pm[(1,0)]+=1
        pp[(1,0)]+=1
    else:
        tmp=seiki(abs(b),abs(a))
        pm[tmp]+=1
        pp[tmp]+=0
#print(pm)
#print(pp)
result=1
for key in pp.keys():
    pp_v=pp[key]
    pm_v=pm[key]
    result*=(pow(2,pm_v)+pow(2,pp_v)-1)
    result%=mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

def seiki(x,y):
    tmp=gcd(x,y)
    return (x//tmp,y//tmp)

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a==0 and b==0:
        zero+=1
    elif a*b>0:
        tmp=seiki(abs(a),abs(b))
        pp[tmp]+=1
    elif a==0:
        pp[(1,0)]+=1
    elif b==0:
        pm[(1,0)]+=1
        pp[(1,0)]+=1
    else:
        tmp=seiki(abs(b),abs(a))
        pm[tmp]+=1
        pp[tmp]+=0
#print(pm)
#print(pp)
result=1
for key in pp.keys():
    pp_v=pp[key]
    pm_v=pm[key]
    result*=(pow(2,pm_v,mod)+pow(2,pp_v,mod)-1)
    result%=mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
import math

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

zero = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a,b)
        a //= g
        b //= g
        if b < 0:
            a = -a
            b = -b
        if b == 0 and a == -1:
            a = 1
        if a > 0:
            if (a,b) in d:
                d[(a,b)][0] += 1
            else:
                d[(a,b)] = [1,0]
        else:
            if (b,-a) in d:
                d[(b,-a)][1] += 1
            else:
                d[(b,-a)] = [0,1]
ans = 1
for (a,b),(c,d) in d.items():
    count = (pow(2,c,mod)+pow(2,d,mod)-1)%mod
    ans *= count
    ans %= mod


print(ans+zero-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)
N = int(input())
data = defaultdict(int)


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

# a, b = (0,0)はそれを入れるのみなので，
# カウントから抜かして(a,b)の数を最後に足せば良い
# どちらかが0の場合は，
# a=0ならb=0のモノが対比となる

cnt_zero = 0

for i in range(N):
    a, b = map(int, input().split())
    div = gcd(abs(a), abs(b))

    # マイナスはaだけ
    if a <0 and b <0:
        a, b = -a, -b
    elif b < 0:
        a, b = -a, -b

    if a ==0 and b==0:
        cnt_zero += 1
        continue

    if a ==0:
        data[(0, 1)] += 1
        data[(1, 0)] += 0
        continue

    if b ==0:
        data[(1, 0)] += 1
        data[(0, 1)] += 0
        continue

    data[(a//div, b//div)] += 1
    if a > 0:
        data[(-b//div, a//div)] += 0
    else:
        data[(b // div, -a // div)] += 0

mod = 1000000007
res = 1


for d in data:
    if d[0]>0 and d[1]>0:
        val = data[d]
        a1 = data[(-d[1], d[0])]
        # print(d, val, a1)
        if val == 0:
            res *= pow(2, a1, mod)
        elif a1 > 0:
            res *= pow(2, val, mod) + pow(2, a1, mod) - 1
            data[(-d[1], d[0])] = 0
        else:
            res *= pow(2, val, mod)
        res %= mod
        # print(res)


print(res+cnt_zero-1)

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
#import math
from fractions import Fraction
import itertools

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)
input=sys.stdin.readline

ans=1
mod=10**9+7
n0=0
na=nb=0
n=int(input())
v=tuple(tuple(map(lambda x: int(x),input().split())) for _ in range(n))
d={}
for i in range(n):
    b= v[i][1]
    a= v[i][0]
    if b==0 or a==0:
        n0+=1
    elif b==0:
        nb+=1
    elif a==0:
        na+=1
    else:
        if Fraction(a, b) not in d:
            d[Fraction(a, b)]=1
        else:
            d[Fraction(a, b)]+=1
            
for i in d.keys():
    if Fraction(-1,i) in d:
        if i>0:
        	ans*=pow(2,d[Fraction(-1, i)],mod)-1+pow(2,d[i],mod)-1+1
        	ans=ans%mod
    else:
        ans*=pow(2,d[i],mod)-1+1
        ans=ans%mod
ans*=(pow(2,na,mod)-1+pow(2,nb,mod)-1+1)
print(ans-1)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a==0 and b==0:
        zero+=1
    elif a*b>0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp
        pp[(a,b)]+=1
    elif a==0:
        pp[(1,0)]+=1
    elif n==0:
        pm[(0,1)]+=1
    else:
        tmp=gcd(abs(a),abs(b))
        a=abs(a//tmp)
        b=abs(b//tmp)
        pm[(b,a)]+=1
            
            
result=1
for key in pp.keys():
    pp_v=pp[key]
    pm_v=pm[key]
    result*=(pow(2,pm_v,mod)+pow(2,pp_v,mod)-1)
    result%=mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書

pp = {} 
pm = {} 

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a*b!=0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp

        if a*b>0:
            if (a,b) in pp:
                pp[(a,b)]+=1
            else:
                pp[(a,b)]=1
        else:
            aa=abs(a)
            bb=abs(b)
            if (aa,bb) in pm:
                pm[(aa,bb)]+=1
            else:
                pm[(aa,bb)]=1

    elif a==0 and b==0:
        zero+=1
    elif a==0:
        if (0,1) in pp:
            pp[(0,1)]+=1
        else:
            pp[(0,1)]=1
    elif b==0:
        if (0,1) in pp:
            pp[(0,1)]+=1
        else:
            pp[(0,1)]=1

            

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    if (b,a) in pm:
        pm_v=pm[(b,a)]
        result=(result*((pow(2,pp_v,mod)-1)+(pow(2,pm_v,mod)-1)+1))%mod
    else:
        result=(result*pow(2,pp_v,mod))%mod

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    if (b,a) not in pp:
        result=result*pow(2,pm_v,mod)%mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書

pp = {} 
pm = {} 

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a*b!=0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp

        if a*b>0:
            if (a,b) in pp:
                pp[(a,b)]+=1
            else:
                pp[(a,b)]=1
        else:
            aa=abs(a)
            bb=abs(b)
            if (aa,bb) in pm:
                pm[(aa,bb)]+=1
            else:
                pm[(aa,bb)]=1

    elif a==0 and b==0:
        zero+=1
    elif a==0:
        if (0,1) in pp:
            pp[(0,1)]+=1
        else:
            pp[(0,1)]=1
    elif b==0:
        if (1,0) in pp:
            pp[(1,0)]+=1
        else:
            pp[(1,0)]=1

            

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    if (b,a) in pm:
        pm_v=pm[(b,a)]
        result=(result*((pow(2,pp_v,mod)-1)+(pow(2,pm_v,mod)-1)+1))%mod
    else:
        result=(result*pow(2,pp_v,mod))%mod

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    if (b,a) not in pp:
        result=result*pow(2,pm_v,mod)%mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a
for a, b in ab:
    if a*b!=0:
        g = gcd(abs(a), abs(b))
        a, b = a//g, b//g
    if a*b>0:
        ind = (abs(a), abs(b))
    elif a*b<0:
        ind = (abs(b), abs(a))
    else:
        ind = 0
    if ind in di:
        x, y = di[ind]
    else:
        x = y = 0
    if a*b==0:
        if b!=0:
            di[ind] = (x+1, y)
        elif a!=0:
            di[ind] = (x, y+1)
    else:
        if a*b>0:
            di[ind] = (x+1, y)
        else:
            di[ind] = (x, y+1)
mod = 10**9+7
ans = 1
for i, j in di.values():
    ans *= (pow(2, i, mod)+pow(2, j, mod)-1)
    ans %= mod
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a
for a, b in ab:
    if a*b!=0:
        g = gcd(abs(a), abs(b))
        a, b = a//g, b//g
    if a*b>0:
        ind = (abs(a), abs(b))
    elif a*b<0:
        ind = (abs(b), abs(a))
    else:
        ind = 0
    if ind in di:
        x, y = di[ind]
    else:
        x = y = 0
    if a*b==0:
        if b!=0:
            di[ind] = (x+1, y)
        elif a!=0:
            di[ind] = (x, y+1)
    else:
        if a*b>0:
            di[ind] = (x+1, y)
        else:
            di[ind] = (x, y+1)
print(di)
mod = 10**9+7
ans = 1
for i, j in di.values():
    ans *= (pow(2, i, mod)+pow(2, j, mod)-1)
    ans %= mod
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

def main():
    MOD = 10**9+7
    N = int(input())
    zero_cnt = 0
    L = defaultdict(int)
    L2 = defaultdict(int)
    for _ in range(N):
        x,y = map(int,input().split())
        if x == 0 and y == 0:
            zero_cnt += 1
            continue
        d = math.gcd(x,y)
        x //= d
        y //= d
        if x == 0 and y == 0:
            zero_cnt += 1
        if y < 0:
            x *= -1
            y *= -1
        elif ｙ == 0 and ｘ < 0:
            x *= -1
            y *= -1
        rot90 = (x <= 0)
        if rot90:
            tmp = x
            x = y
            y = -tmp
        if rot90:
            L[(x,y)] += 1
        else:
            L2[(x,y)] += 1

    ans = 1
    keys = set(list(L.keys()) + list(L2.keys()))
    for k in keys:
        now = 1
        s = L[k]
        t = L2[k]
        now += pow(2,s,MOD) - 1
        now += pow(2,t,MOD) -1
        ans *= now
        ans %= MOD
    ans -= 1
    ans += zero_cnt
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math

def main():
    MOD = 10**9+7
    N = int(input())
    zero_cnt = 0
    L = defaultdict(int)
    L2 = defaultdict(int)
    for _ in range(N):
        x,y = map(int,input().split())
        if x == 0 and y == 0:
            zero_cnt += 1
            continue
        d = math.gcd(x,y)
        x //= d
        y //= d
        if x == 0 and y == 0:
            zero_cnt += 1
        if y < 0:
            x *= -1
            y *= -1
        elif ｙ == 0 and ｘ < 0:
            x *= -1
            y *= -1
        rot90 = (x <= 0)
        if rot90:
            tmp = x
            x = y
            y = -tmp
        if rot90:
            L[(x,y)] += 1
        else:
            L2[(x,y)] += 1

    ans = 1
    keys = set(list(L.keys()) + list(L2.keys()))
    for k in keys:
        now = 1
        s = L[k]
        t = L2[k]
        now += 2**s - 1
        now += 2**t -1
        ans *= now
    ans -= 1
    ans += zero_cnt
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
N = int(input())
d = defaultdict(int)
s = set()
ans = 0
mod = 1000000007

def change(A, B):
    if A == 0 and B == 0:
        return (0, 0)
    if A == 0:
        return (0, 1)
    if B == 0:
        return (1, 0)
    GCD = gcd(A, B)
    A //= GCD
    B //= GCD
    if A < 0:
        A *= -1
        B *= -1
    return (A, B)

def pair(key):
    if key == (1, 0):
        return (0, 1)
    A, B = key
    return (B, -A)

for i in range(N):
    A, B = map(int,input().split())
    A, B = change(A, B)
    if A == 0 and B == 0:
        ans += 1
    else:
        d[(A, B)] += 1
        if A == 0:
            A, B = B, A
        elif B < 0:
            A, B = -B, A
        s.add((A, B))

cnt = 1
for k in s:
    cnt *= pow(2, d[k], mod) + pow(2, d[pair(k)], mod) - 1
    cnt %= mod
cnt -= 1
ans += cnt

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return abs(a)
for a, b in ab:
    if a*b!=0:
        g = gcd(a, b)
        a, b = a//g, b//g
    if a*b>0:
        ind = (abs(a), abs(b))
    elif a*b<0:
        ind = (abs(b), abs(a))
    else:
        ind = 0
    if ind in di:
        x, y = di[ind]
    else:
        x = y = 0
    if a*b==0:
        if b!=0:
            di[0] = (x+1, y)
        elif a!=0:
            di[0] = (x, y+1)
    else:
        if a*b>0:
            di[ind] = (x+1, y)
        else:
            di[ind] = (x, y+1)
mod = 10**9+7
ans = 1
for i, j in di.values():
    ans *= (pow(2, i, mod)+pow(2, j, mod)-1)
    ans %= mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
import math
mod=1000000007
n=int(input())
iwashi_group={}
count=0

#傾きを第1象限(True)と第4象限(False)の座標で管理する
for i in range(n):
    a,b=map(int,input().split())
    
    if a*b>0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(a)//GCD,abs(b)//GCD)
        flag=True
    
    elif a*b<0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(b)//GCD,abs(a)//GCD)
        flag=False

    elif a==0 and b==0:
        count+=1
        continue

    elif a==0:
        iwashi=(0,1)
        flag=True
    
    elif b==0:
        iwashi=(0,1)
        flag=False
  
    if iwashi in iwashi_group:
        if flag:
            iwashi_group[iwashi][0]+=1
        else:
            iwashi_group[iwashi][1]+=1
    else:
        if flag:
            iwashi_group[iwashi]=[1,0]
        else:
            iwashi_group[iwashi]=[0,1]

ans=1
for a,b in iwashi_group.values():
    ans=ans*(2**a+2**b-1)%mod

print(ans+count-1)

Submission status: Wrong Answer

Solution code:
import math
mod=1000000007
n=int(input())
iwashi_group={}

#傾きを第1象限(True)と第4象限(False)の座標で管理する
for i in range(n):
    a,b=map(int,input().split())
    
    if a*b>0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(a)//GCD,abs(b)//GCD)
        flag=True
    
    elif a*b<0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(b)//GCD,abs(a)//GCD)
        flag=False

    elif a==0 and b==0:
        iwashi=(0,0)
        flag=True

    elif a==0:
        iwashi=(0,1)
        flag=True
    
    elif b==0:
        iwashi=(0,1)
        flag=False
  
    if iwashi in iwashi_group:
        if flag:
            iwashi_group[iwashi][0]+=1
        else:
            iwashi_group[iwashi][1]+=1
    else:
        if flag:
            iwashi_group[iwashi]=[1,0]
        else:
            iwashi_group[iwashi]=[0,1]

ans=1
for a,b in iwashi_group.values():
    ans=ans*(2**a+2**b-1)%mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
z = 0
k = 0
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a
for a, b in ab:
    tmp = a*b//gcd(a, b)**2 if a*b!=0 else 0
    ind = abs(tmp) if (abs(a)<abs(b)) ^ (tmp>0) else -abs(tmp)
    if abs(a)==abs(b):
        ind = abs(tmp)
    if ind in di:
        x, y = di[ind]
    else:
        x = y = 0
    if tmp==0:
        if b!=0:
            di[0] = (x+1, y)
            k += 1
        elif a!=0:
            di[0] = (x, y+1)
            k += 1
        else:
            z += 1
    else:
        if tmp>0:
            di[ind] = (x+1, y)
        else:
            di[ind] = (x, y+1)
        k += 1
mod = 10**9+7
ans = pow(2, n-z-k, mod)
for i, j in di.values():
    ans *= (pow(2, i, mod)+pow(2, j, mod)-1)
    ans %= mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
n=int(input())

mod=10**9+7

#初期値が0の辞書

pp = {} 
pm = {} 

from math import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a*b!=0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp

        if a*b>0:
            if (a,b) in pp:
                pp[(a,b)]+=1
            else:
                pp[(a,b)]=1
        else:
            aa=abs(a)
            bb=abs(b)
            if (aa,bb) in pm:
                pm[(aa,bb)]+=1
            else:
                pm[(aa,bb)]=1

    elif a==0 and b==0:
        zero+=1
    else:
        if (a,b) in pp:
            pp[(a,b)]+=1
        else:
            pp[(a,b)]=1

            

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    if (b,a) in pm:
        pm_v=pm[(b,a)]
        result=(result*((pow(2,pp_v,mod)-1)+(pow(2,pm_v,mod)-1)+1))%mod
    else:
        result=(result*pow(2,pp_v,mod))%mod

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    if (b,a) not in pp:
        result=result*pow(2,pm_v,mod)%mod

print((result-1+zero)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

mod=10**9+7

#初期値が0の辞書

pp = {} 
pm = {} 

from fractions import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a*b!=0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp

        if a*b>0:
            if (a,b) in pp:
                pp[(a,b)]+=1
            else:
                pp[(a,b)]=1
        else:
            aa=abs(a)
            bb=abs(b)
            if (aa,bb) in pm:
                pm[(aa,bb)]+=1
            else:
                pm[(aa,bb)]=1

    elif a==0 and b==0:
        zero+=1
    else:
        if (a,b) in pp:
            pp[(a,b)]+=1
        else:
            pp[(a,b)]=1

            

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    if (b,a) in pm:
        pm_v=pm[(b,a)]
        result=(result*((pow(2,pp_v,mod)-1)+(pow(2,pm_v,mod)-1)+1))%mod
    else:
        result=(result*pow(2,pp_v,mod))%mod

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    if (b,a) not in pp:
        result=result*pow(2,pm_v,mod)%mod

print((result-1+zero)%mod)