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: Accepted

Solution code:

from collections import defaultdict
from math import gcd

def resolve():
    MOD = 1000000007

    N = int(input())
    dic = defaultdict(int)
    zeros = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zeros += 1
        else:
            g = gcd(a, b)
            a //= g
            b //= g
            if a < 0:
                a *= -1
                b *= -1
            if a == 0 and b == -1:
                b = 1
            dic[(a, b)] += 1

    ans = 1
    free = 0
    for (a, b), n in dic.items():
        if b > 0:
            if (b, -a) in dic:
                m = dic[(b, -a)]
                ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
            else:
                free += n
        else:
            if (-b, a) not in dic:
                free += n
                
    ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
z = 0
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:
            z += 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+z-1)%mod)

Submission status: Accepted

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)]+=0
    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: Accepted

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)%mod)

Submission status: Accepted

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)
    # aが0の場合
    if d[0]==0:
        val = data[d]
        a1 = data[(1, 0)]

        if val == 0:
            res *= pow(2, a1, mod)
        elif a1 > 0:
            res *= pow(2, val, mod) + pow(2, a1, mod) - 1
        else:
            res *= pow(2, val, mod)
        res %= mod

print((res+cnt_zero-1)%mod)

Submission status: Accepted

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 f(a, b):
    if a== 0 and b == 0:
        return (1, 0, 0)
    if b == 0:
        return (1, 1, 0)
    f = Fraction(a, b)
    a = f.numerator
    b = f.denominator
    if a < 0:
        s = -1
        a *= -1
    else:
        s = 1
    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)
        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.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: Accepted

Solution code:
from math import gcd
from collections import defaultdict
mod=10**9+7
_,*S=open(0)
mp=defaultdict(lambda:[0,0])
O=0
for s in S:
    a,b=map(int,s.split())
    if a==b==0:O+=1
    else:
        g=gcd(a,b)
        a//=g
        b//=g
        if a<0 or a==0<b:a,b=-a,-b
        f=0
        if b<0:a,b,f=-b,a,1
        mp[(a,b)][f]+=1
ans=1
for k in mp:x,y=mp[k];ans=ans*(pow(2,x,mod)+pow(2,y,mod)-1)%mod
print((ans+O-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
import sys
input = sys.stdin.readline

def main():
    n = int(input())

    dict1 = {}
    mod = 1000000007
    cnt00 = 0
    cnt01 = 0
    cnt10 = 0

    for _ in range(n):
        a,b = map(int,input().split())
        if a == 0 and b == 0:
            cnt00 += 1
        elif a == 0:
            cnt01 += 1
        elif b == 0:
            cnt10 += 1
        else:
            c = gcd(a,b)
            if b < 0:
                a *= -1
                b *= -1
            set1 = (a//c, b//c)
            if set1 in dict1:
                dict1[set1] += 1
            else:
                dict1[set1] = 1

    ans = 1

    for k,v in dict1.items():
        a,b = k
        if dict1[(a,b)] == -1:
            continue
        if a > 0:
            if (-b,a) in dict1:
                ans *= 2**v + 2**dict1[(-b,a)] - 1
                dict1[(-b,a)] = -1
            else:
                ans *= 2**v
        else:
            if (b,-a) in dict1:
                ans *= 2**v + 2**dict1[(b,-a)] - 1
                dict1[(b,-a)] = -1
            else:
                ans *= 2**v
        ans %= mod

    ans *= 2 ** cnt01 + 2 ** cnt10 - 1
    ans += cnt00 - 1

    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
"""
n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]

mod = 1000000007

ab1 = []
ab2 = []
ab3 = []
ab4 = []
count00 = 0
count01 = 0
count10 = 0

for i in range(n):
    if ab[i][0] != 0 and ab[i][1] != 0:
        ab1.append(ab[i][0]/ab[i][1])
        ab2.append(-ab[i][1]/ab[i][0])
        if ab[i][0]/ab[i][1] > 0:
            ab3.append((ab[i][0]/ab[i][1],-ab[i][1]/ab[i][0]))
        else:
            ab4.append((ab[i][0]/ab[i][1],-ab[i][1]/ab[i][0]))
    elif ab[i][0] == 0 and ab[i][1] == 0:
        count00 += 1
    elif ab[i][0] == 0 and ab[i][1] == 1:
        count01 += 1
    else:
        count10 += 1

dict1 = {}
dict2 = {}
ab3.sort()
ab4.sort(reverse = True)

print(ab3)
print(ab4)

for i in ab1:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1

for i in ab2:
    if i in dict2:
        dict2[i] += 1
    else:
        dict2[i] = 1

sorted1 = sorted(dict1.items(), key = lambda x: x[0])
sorted2 = sorted(dict2.items(), key = lambda x: x[0])

print(sorted1)
print(sorted2)

cnt = 0
num1 = n - count00 - count01 - count10
ans = 0
for i in range(len(ab3)):
    a,b = ab3[i]
    num1 -= 1
    if cnt < len(sorted2):
        while cnt < len(sorted2):
            if sorted2[cnt][0] == a:
                ans += pow(2, num1+count01+count10-sorted2[cnt][1], mod)
                ans %= mod
                break
            elif sorted2[cnt][0] < a:
                cnt += 1
            else:
                ans += pow(2, num1+count01+count10, mod)
                ans %= mod
                break
        else:
            ans += pow(2, num1+count01+count10, mod) - pow(2, )
            ans %= mod
    print(ans)

for i in range(len(ab4)):
    num1 -= 1
    ans += pow(2, num1+count01+count10, mod)
    ans %= mod
    print(ans)

ans += pow(2, count01, mod) -1
print(ans)
ans += pow(2, count10, mod) -1
print(ans)
ans += count00
print(ans)

print(ans % mod)
"""

from math import gcd

n = int(input())

dict1 = {}
mod = 1000000007
cnt00 = 0
cnt01 = 0
cnt10 = 0

for _ in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        cnt00 += 1
    elif a == 0:
        cnt01 += 1
    elif b == 0:
        cnt10 += 1
    else:
        c = gcd(a,b)
        if b < 0:
            a *= -1
            b *= -1
        set1 = (a//c, b//c)
        if set1 in dict1:
            dict1[set1] += 1
        else:
            dict1[set1] = 1

ans = 1

for k,v in dict1.items():
    a,b = k
    if dict1[(a,b)] == -1:
        continue
    if a > 0:
        if (-b,a) in dict1:
            ans *= 2**v + 2**dict1[(-b,a)] - 1
            dict1[(-b,a)] = -1
        else:
            ans *= 2**v
    else:
        if (b,-a) in dict1:
            ans *= 2**v + 2**dict1[(b,-a)] - 1
            dict1[(b,-a)] = -1
        else:
            ans *= 2**v
    ans %= mod

ans *= 2 ** cnt01 + 2 ** cnt10 - 1
ans += cnt00 - 1

print(ans%mod)

Submission status: Accepted

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%MOD)

main()

Submission status: Accepted

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
ans %= mod

print(ans)

Submission status: Accepted

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)%mod)

Submission status: Accepted

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

N = int(input())
pp = defaultdict(int)
pn = defaultdict(int)
p_zero = 0
zero_p = 0
zero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        zero += 1
    elif a == 0:
        zero_p += 1
    elif b == 0:
        p_zero += 1
    elif a * b > 0:
        g = gcd(a, b)
        a = abs(a) // g
        b = abs(b) // g
        pp[(a, b)] += 1
    else:
        g = gcd(a, b)
        a = abs(a) // g
        b = abs(b) // g
        pn[(a, b)] += 1

checked = defaultdict(bool)
ans = 1

#(a,b), (c,d)
for (x, y), v in pp.items():
    checked[(x, y)] = True
    R = 0
    R += pow(2, v, mod) - 1
    R += pow(2, pn[(y, x)], mod) - 1
    R += 1
    ans = ans * R % mod

for (x, y), v in pn.items():
    if checked[(y, x)]:
        continue
    R = pow(2, v, mod)
    ans = ans * R % mod

#(0, x), (y, 0)
R = pow(2, zero_p, mod) - 1
R += pow(2, p_zero, mod) - 1
R += 1
ans = ans * R % mod

# (0,0)
ans = (ans + zero) % mod

# 空はダメ
ans = (ans - 1 + mod) % mod

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque, Counter, defaultdict
# from fractions import gcd
from math import gcd
import heapq

MOD = 10 ** 9 + 7
input = stdin.readline

n = int(input())
zero = 0
A, B = [], []
# mp = defaultdict(lambda: [0, 0])
mp = {}
for i in range(n):
    ai, bi = map(int, input().split())
    if ai == 0 and bi == 0:
        zero += 1
        continue

    gi = gcd(ai, bi)
    ai = ai // gi
    bi = bi // gi

    if bi < 0:
        ai = -ai
        bi = -bi
    if bi == 0 and ai < 0:
        ai = -ai
    if ai <= 0:
        ai, bi = bi, -ai
        if (ai, bi) in mp:
            mp[(ai, bi)][0] += 1
        else:
            mp[(ai, bi)] = [1, 0]
    else:
        if (ai, bi) in mp:
            mp[(ai, bi)][1] += 1
        else:
            mp[(ai, bi)] = [0, 1]

ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, MOD) + pow(2, t, MOD) - 1
    ans %= MOD
print((zero - 1 + ans) % MOD)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,gcd #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))



def main():
    N=I()
    A,B=[],[]
    for i in range(N):
        a,b = MI()
        A.append(a)
        B.append(b)
    both_zero_cnt = 0
    num_of_group = defaultdict(int) ##既約分数にしてあげて、(分子,分母)がkeyで、負なら分子が負になる他は正
    for i in range(N):
        a,b = A[i], B[i]
        if(a==b==0):
            both_zero_cnt+=1
            continue
        elif(a==0):
            num_of_group[-inf,inf] += 1
            num_of_group[inf,inf] += 0

        elif(b==0):
            num_of_group[inf,inf] += 1
        else:
            if(a*b<0):
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(-b,a)] += 1
                num_of_group[(b,a)] += 0
            else:
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(a,b)] += 1
    # print(num_of_group.items())
    if(both_zero_cnt==N):
        print(N)
        return
    ##solve
    ans = ModInt(1)
    # two_pow = [1]
    # for i in range(N):
    #     two_pow.append((2*two_pow[-1])%mod)
    # print(two_pow,"#######")
    for (a,b),cnt1 in num_of_group.items():
        if(a<0):
            continue
        tmp = ModInt(2)**cnt1
        if (-a,b) in num_of_group:
            cnt2 = num_of_group[-a,b]
            tmp += ModInt(2)**cnt2
            tmp-=1
        if(tmp):
            ans *= tmp
    ans -= 1 ##全部選ばない
    ans += both_zero_cnt
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,gcd #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))



def main():
    N=I()
    A,B=[],[]
    for i in range(N):
        a,b = MI()
        A.append(a)
        B.append(b)
    both_zero_cnt = 0
    num_of_group = defaultdict(int) ##既約分数にしてあげて、(分子,分母)がkeyで、負なら分子が負になる他は正
    for i in range(N):
        a,b = A[i], B[i]
        if(a==b==0):
            both_zero_cnt+=1
            continue
        elif(a==0):
            num_of_group[-inf,inf] += 1
            num_of_group[inf,inf] += 0

        elif(b==0):
            num_of_group[inf,inf] += 1
        else:
            if(a*b<0):
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(-b,a)] += 1
                num_of_group[(b,a)] += 0
            else:
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(a,b)] += 1
    # print(num_of_group.items())
    if(both_zero_cnt==N):
        print(N)
        return
    ##solve
    ans = ModInt(1)
    two_pow = [1]
    for i in range(N):
        two_pow.append((2*two_pow[-1])%mod)
    # print(two_pow,"#######")
    for (a,b),cnt1 in num_of_group.items():
        if(a<0):
            continue
        tmp = two_pow[cnt1]

        if (-a,b) in num_of_group:
            cnt2 = num_of_group[-a,b]
            tmp += two_pow[cnt2]
            tmp-=1
        if(tmp):
            ans *= tmp
    ans -= 1 ##全部選ばない
    ans += both_zero_cnt
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
mod = 10**9+7
n=int(input())
r = dict()
zeros = 0
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    zeros+=1
    continue
  if all((a,b)):
    g = gcd(a,b)*(a//abs(a))
  elif a:
    g = a
  else:
    g = b
  p = a//g,b//g
  r[p] = r.get(p,0)+1
ans = 1
done = set()
for (a,b), v in r.items():
  if (b,-a) in done or (-b,a) in done:
    continue
  done.add((a,b))
  w = r.get((b,-a),0)+r.get((-b,a),0)
  ans = ans*(pow(2,v,mod)+pow(2,w,mod)-1)%mod
  
print((ans+zeros+mod-1)%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
mod = 1000000007

pos = defaultdict(int)
neg = defaultdict(int)
zero = 0

n = int(input())
for _ in range(n):
	a, b = list(map(int, input().split()))
	if a == b == 0:
		zero += 1
	elif a == 0:
		pos[(0, 1)] += 1
	elif b == 0:
		neg[(0, 1)] += 1
	else:
		c = a * b
		g = math.gcd(a, b)
		a, b = abs(a // g), abs(b // g)
		if c > 0:
			pos[(a, b)] += 1
		elif c < 0:
			neg[(b, a)] += 1

cnt = 1
for x in pos.keys():
	if x in neg.keys():
		cnt = (cnt * (pow(2, pos[x], mod) + pow(2, neg[x], mod) - 1)) % mod
		del neg[x]
	else:
		cnt = (cnt * pow(2, pos[x], mod)) % mod

for x in neg.keys():
	cnt = (cnt * pow(2, neg[x], mod)) % mod

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
from math import gcd
count = defaultdict(int)
N = int(sys.stdin.readline())

zeros = 0
for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A == B == 0:
        zeros += 1
        continue
    if A == 0:
        angle = (0, 1)
    elif B == 0:
        angle = (1, 0)
    else:
        sgn = A // abs(A)
        g = gcd(A, B)
        angle = (A // sgn // g, B // sgn // g)

    count[angle] += 1
# print(count)

pairs = {}
solos = []
for k1 in count:
    if k1 in pairs:
        continue
    if k1 == (0, 1):
        if (1, 0) in count:
            pairs[(1, 0)] = k1
        else:
            solos.append(k1)
        continue

    A, B = k1
    if B:
        sgn = -B // abs(B)
        k2 = (-B // sgn, A // sgn)
    else:
        k2 = (0, 1)
    if k2 in count:
        pairs[k2] = k1
    else:
        solos.append(k1)
#print(pairs, solos)

P = 1000000007


def pow2(n):
    # if n < 30:
    #     return 2 ** n

    # p = pow2(n // 2)
    # pp = (p * p) % P
    # if n % 2 == 1:
    #     return (2 * pp) % P
    # else:
    #     return pp
    return pow(2, n, P)


result = 1
for p in pairs:
    # print("pair", p, count[p], pairs[p], count[pairs[p]])
    n = count[p]
    m = count[pairs[p]]
    result = result * ((pow2(n) - 1) + (pow2(m) - 1) + 1) % P
for k in solos:
    # print("solo", k, count[k])
    result = result * pow2(count[k]) % P

print((result + zeros - 1) % P)

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def main():
    n = int(input())
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = map(int,input().split())
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                m = gcd(a,b)
                a //= m
                b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        if a == 0 and b == 0:
            continue
        flag = 0
        if a == 0 and b == 1:
            rev = ' '.join([str(1),str(0)])
        elif a == 1 and b == 0:
            rev = ' '.join([str(0),str(1)])
        elif a > 0 and b > 0:
            rev = ' '.join([str(b),str(-a)])
        else:
            rev = ' '.join([str(-b),str(a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        if flag:
            continue
        n1 = pow(2,dic[e],mod)
        n2 = pow(2,dic1[rev],mod)
        ans *= (n1+n2-1)
        ans %= mod
    print((ans-1+dic['0 0'])%mod)
    
if __name__ == "__main__":
    main()