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:
#!/usr/bin/env python3
import sys
from math import gcd
from collections import defaultdict
sys.setrecursionlimit(10**8)

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):

    def quadrant(a, b):
        if a > 0 and b >= 0:
            return 0
        elif a <= 0 and b > 0:
            return 1
        elif a < 0 and b <= 0:
            return 2
        elif a >= 0 and b < 0:
            return 3
        else:
            return None

    def norm(a, b):
        g = gcd(a, b)
        a //= g
        b //= g
        while quadrant(a, b) != 0:
            a, b = -b, a
        return a, b

    d = defaultdict(lambda: [0, 0, 0, 0])
    kodoku = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if (a, b) == (0, 0):
            kodoku += 1
        else:
            d[norm(a, b)][quadrant(a, b)] += 1

    ans = 1
    for v in d.values():
        buf = pow(2, v[0]+v[2], MOD)
        buf += pow(2, v[1]+v[3], MOD)
        buf = (buf-1) % MOD
        ans *= buf
        ans %= MOD

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない。
    # 順にイワシを見て、直行するものをグループにする。
    # 先に単純な整数比へ変換しておく（有理数としての扱い）
    # aは整数、bは非負整数となるように整理する
    d = Counter()
    # (a, b) == (0, 0)については、他のイワシと同時に選ぶことができない。
    # 個別にカウントする。
    kodokunaiwashi = 0
    for i, (a, b) in enumerate(zip(A, B)):
        if a == 0 and b == 0:
            kodokunaiwashi += 1
        elif b == 0:
            d[1, 0] += 1
        elif b > 0:
            g = math.gcd(b, a)
            aa = a//g
            bb = b//g
            d[aa, bb] += 1
        else:
            g = math.gcd(-b, -a)
            aa = -a//g
            bb = -b//g
            d[(aa, bb)] += 1

    # 直交するグループを考える。
    ans = 1
    for a, b in d:
        # (a, b)と直交するのは、(-b, a)と(b, -a)である。
        # このうち、有理数としてカウントしている方を採用する
        x, y = -b, a
        if y < 0:
            x = -x
            y = -y
        elif y == 0:
            x = abs(x)

        # すでに直交するイワシとしてカウントをしたらNoneとしている。
        if d[a, b] == None:
            continue

        if d[x, y] == 0:
            # 直交するイワシが存在しない場合、自由に選ぶことができる。
            ans *= pow(2, d[a, b], MOD)
            ans %= MOD
            continue
        else:
            # 直交するイワシが存在する場合、どちらかのグループから自由に選ぶ。
            # ただし、一つも選ばないという場合は、重複するためケア
            buf = pow(2, d[a, b], MOD)
            buf += pow(2, d[x, y], MOD)
            buf -= 1
            buf %= MOD
            # print(buf)
            ans *= buf
            ans %= MOD
            d[x, y] = None

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    posi = {}
    nega = {}
    ab_zero = 0
    a_zero = 0
    b_zero = 0

    for _ in range(n):
        a,b = map(int, input().split())
        if a==0 and b==0:
            ab_zero += 1
        elif a==0:
            a_zero += 1
        elif b==0:
            b_zero += 1
        elif a*b > 0:
            a = abs(a)
            b = abs(b)
            g = gcd(a, b)
            po = (a//g, b//g)
            if po in posi:
                posi[po] += 1
            else:
                posi[po] = 1
        else:
            a = abs(a)
            b = abs(b)
            g = gcd(a, b)
            ne = (b//g, a//g)
            if ne in nega:
                nega[ne] += 1
            else:
                nega[ne] = 1
    
    res = pow(2, a_zero, mod) + pow(2, b_zero, mod) - 1
    for k, v in posi.items():
        if k in nega:
            res *= pow(2, v, mod) + pow(2, nega[k], mod) - 1
            res %= mod
            nega.pop(k)
        else:
            res *= pow(2, v, mod)
            res %= mod

    for v in nega.values():
        res *= pow(2, v, mod)
        res %= mod

    res += ab_zero - 1
    print(res%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
_, *e = [[*map(int, t.split())] for t in open(0)]
ans = 1
mod = 10 ** 9 + 7
slope_dict = {}
zeros = 0
for x, y in e:
    if x == y == 0:
        zeros += 1
    else:
        d = gcd(x, y)
        x //= d
        y //= d
        if x < 0 or x == 0 < y:
            x, y = -x, -y
        s = 0
        if y < 0:
            x, y, s = -y, x, 1
        if (x, y) not in slope_dict:
            slope_dict[(x, y)] = [0, 0]
        slope_dict[(x, y)][s] += 1

for k in slope_dict:
    ans = ans * (pow(2, slope_dict[k][0], mod) +
                 pow(2, slope_dict[k][1], mod) - 1) % mod
print((ans + zeros - 1) % mod)

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:
# E - Bullet

from collections import Counter
from math import gcd

n = int(input())
counter = Counter()  # 各ベクトルの個数
for i in range(n):
    a, b = map(int, input().split())
    if b < 0:
        a, b = -a, -b  # 180度回転して第1〜2象限に
    elif b == 0:
        a = abs(a)
    if not a == b == 0:
        # 既約化
        g = gcd(a, b)
        a //= g
        b //= g
    counter[(a, b)] += 1

modulus = 1000000007

vs = set(counter)
# 第2象限のベクトルと直交するベクトルを追加
vs.update((b, -a) for a, b in counter if a <= 0)
# 第1象限のベクトルのみ抽出
vs = [(a, b) for a, b in vs if a > 0]

ncomb = 1  # イワシの選び方の個数
for a, b in vs:
    # 互いに仲が悪いイワシ群
    n1 = counter[(a, b)]
    n2 = counter[(-b, a)]
    # それぞれの群から好きな数だけイワシを選ぶ (0匹選ぶことも含む)
    m = pow(2, n1, modulus) + pow(2, n2, modulus) - 1
    ncomb = ncomb * m % modulus

ncomb -= 1  # 1匹も選ばない場合を除く

# (0, 0)のイワシを1匹だけ選ぶ
ncomb += counter[(0, 0)]

print(ncomb % modulus)

Submission status: Accepted

Solution code:
from math import gcd 
n=int(input())
mod = 10**9+7
count = {}

num=0
for _ in range(n):
    a,b = map(int,input().split())
    if a==0 and b==0:
        num+=1
        continue
    if a*b != 0:
        g=gcd(a,b)*(b//abs(b))
    elif a != 0:
        g=a
    else:
        g=b
        
    l=a//g,b//g
    count[l]=count.get(l,0)+1
        
mem=set()
ans=1
for (x,y),z in count.items():
    if x*y==0:
        k=(y,x)
    else:
        k=(-1*x//abs(x)*y,abs(x))
    if k in mem:
        continue
    mem.add((x,y))
    ans*=(pow(2,z)+pow(2,count.get(k,0))-1)
    ans%=mod

print((ans+num-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
from sys import setrecursionlimit
setrecursionlimit(4100000)
mod = 10 ** 9 + 7
n = int(input())

zeros = 0
d = {}
for i in range(n):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        zeros += 1
    else:
        g = gcd(x, y)
        x, y = x // g, y // g
        if (y < 0) or (y == 0 and x < 0): 
            x, y = -x, -y
        else: 
            pass
        if x <= 0:
            sq = True   #second quadrant
            x, y = y, -x
        else:
            sq = False
        if sq == True:
            if (x, y) in d:
                d[(x, y)][1] += 1
            else:
                d[(x, y)] = [0, 1]
        else:
            if (x, y) in d:
                d[(x, y)][0] += 1
            else:
                d[(x, y)] =[1, 0] 

#繰り返し2乗法
def  mod_pow(a:int, b:int, mod:int)->int:
    if b == 0:
        return 1 % mod
    elif b % 2 == 0:
        return (mod_pow(a, b//2, mod) ** 2) % mod
    elif b == 1:
        return a % mod
    else:
        return ((mod_pow(a, b//2, mod) ** 2) * a) % mod
#print(d)

ans = 1
for (a, b), (k, l) in d.items():
    now = 1
    now = (now + mod_pow(2, k, mod) - 1) % mod
    now = (now + mod_pow(2, l, mod) - 1) % mod
    ans = (ans * now) % mod
    
ans -= 1
zeros = zeros % mod
ans = (ans + zeros) % mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

N = int(input())
m = defaultdict(lambda : 0)
BIG_NUMBER = 1000000007
bad_iwashi_count = 0

for _ in range(N):
    A,B = map(int,input().split())
    #0の場合
    if A == 0 and B == 0:
        bad_iwashi_count += 1
        continue
    if A == 0:
        m[(-1,0,1)]+=1
        continue
    if B == 0:
        m[(1,1,0)]+=1
        continue
    #0以外
    gcd_ = math.gcd(A,B)
    A = A//gcd_
    B = B//gcd_
    if A < 0 and B > 0: m[(-1,-A,B)]+=1
    elif B < 0 and A > 0: m[(-1,A,-B)]+=1
    elif A < 0 and B < 0 :m[(1,-A,-B)]+=1
    elif A > 0 and B > 0 :m[(1,A,B)]+=1

total = 1
for key in list(dict(m).keys()):
    total *= pow(2,m[key],BIG_NUMBER) + pow(2,m[-key[0],key[2],key[1]],BIG_NUMBER) -1
    total %= BIG_NUMBER
    m.pop(key)
    m.pop((-key[0],key[2],key[1]))
print((total+bad_iwashi_count-1)%BIG_NUMBER)

'''
3
1 2
-1 1
2 -1
'''

Submission status: Accepted

Solution code:

from fractions import Fraction
from collections import defaultdict
def resolve():
    # A1*A2 + B1*B2 = 0 式変形 A1/B1 = -(B2/A2)
    # a, b の0がある条件を考える
    
    MOD = 1000000007
    N = int(input())
    zeroes = 0
    hash1 = defaultdict(int) #
    hash2 = defaultdict(str) #中の悪い相手を記入
    for _ in range(N):
        a, b = map(int, input().split())
        if a==0 and b==0:
            zeroes += 1
        elif b == 0:
            hash1["1/0"] += 1
            hash2["1/0"] = "0/1"
        elif a == 0:
            hash1["0/1"] += 1
            hash2["0/1"] = "1/0"
        else: # a, bが0以外
            rat1 = Fraction(a, b)
            rat2 = Fraction(-b, a)
            hash1[str(rat1)] += 1
            hash2[str(rat1)] = str(rat2) # 相手を入れる

    confirmed = set()
    ans = 1
    for k, v in hash1.items():
        if k in confirmed: # 確認済みを数えないようにする
            continue
        bad = hash1.get(hash2[k], 0) # 中の悪い相手, キーがなかったら0を出力
        cnt1 = pow(2, v, MOD) - 1
        cnt2 = pow(2, bad, MOD) - 1
        ans = (ans * (cnt1 + cnt2 + 1)) % MOD
        # 確認済みにする
        confirmed.add(k)
        confirmed.add(hash2[k])
        # ※ ループ中に値を変更したらエラー
        # hash1[k] = -1

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
M = 1000000007


def gcd(a, b):
  while b != 0:
    a, b = b, a % b

  return a


def comb(n):
  c = 1

  for _ in range(n):
    c = (c * 2) % M

  return c - 1


def main():
  zeros = 0
  groups = {}

  for _ in range(int(input())):
    a, b = map(int, input().split())

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

    if a == 0:
      v = (1, 0)
      i = 0
    elif b == 0:
      v = (1, 0)
      i = 1
    else:
      if b < 0:
        a = -a
        b = -b

      g = gcd(a, b)
      a //= g
      b //= g

      if a > 0:
        v = (a, b)
        i = 0
      else:
        v = (b, -a)
        i = 1

    if v not in groups:
      groups[v] = [0, 0]

    groups[v][i] += 1

  count = 1

  for k, (v1, v2) in groups.items():
    c = (comb(v1) + comb(v2) + 1) % M
    count = (count * c) % M

  count = (count - 1 + zeros) % M

  print(count)


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from math import gcd
 
n=int(input())
mod = 10**9+7
 
d = 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
  d[p] = d.get(p,0)+1
 
ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v)+pow(2,w)-1)
  ans %= mod
print((ans+zeros-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
 
n=int(input())
mod = 10**9+7
 
d = 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
  d[p] = d.get(p,0)+1
 
ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v)+pow(2,w)-1)
  ans %= mod
print((ans+zeros-1+mod)%mod)

Submission status: Accepted

Solution code:
from math import gcd
 
n=int(input())
mod = 10**9+7
 
d = 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
  d[p] = d.get(p,0)+1
 
ans = 1
done = set()
for (a,b),v in d.items():
  if (-b,a) in done or (b,-a) in done:
    continue
  done.add((a,b))
  w=d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v,mod)+pow(2,w,mod)-1)
  ans %= mod
print((ans+zeros-1+mod)%mod)

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
from math import gcd
d=defaultdict(int)
for a,b in ab:
  if a==0 and b==0:
    d[(0,0)]+=1
  elif a==0:
    d[(1,0)]+=1
  elif b==0:
    d[(0,1)]+=1
  else:
    if a<0:
      a*=-1
      b*=-1
    g=gcd(a,b)
    d[(a//g,b//g)]+=1
mod=pow(10,9)+7
ans=1
keys=d.keys()
for k in keys:
  if k==(0,0):
    continue
  else:
    a,b=k
    x=b if b>0 else -b
    y=-a if b>0 else a
    k0=tuple([x,y])
    if k0 in d:
      ans*=pow(2,d[k],mod)-1+pow(2,d[k0],mod)-1+1
      ans%=mod
      d[k]=0
      d[k0]=0
    else:
      ans*=pow(2,d[(a,b)],mod)
      ans%=mod
ans+=d[(0,0)]
ans-=1
print(ans%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
n,*L=map(int,open(0).read().split())
mod=10**9+7
d=defaultdict(lambda:[0,0])
gcd=lambda x,y:x if y==0 else gcd(y,x%y)
two=[1]*(n+1)
for i in range(n):
	two[i+1]=(two[i]*2)%mod
zero=0
for a,b in zip(*[iter(L)]*2):
	if a==b==0:
		zero+=1
		continue
	if a==0:
		d[(0,1)][0]+=1
	elif b==0:
		d[(0,1)][1]+=1
	else:
		g=gcd(a,b)
		a//=g
		b//=g
		if a*b>0:
			d[(a,b)][0]+=1
		else:
			d[(abs(b),abs(a))][1]+=1
ans=1
for (_,_),(x,y) in d.items():
	ans*=(two[x]+two[y]-1)%mod
	ans%=mod
print((ans+zero+mod-1)%mod)

Submission status: Accepted

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

mod = 1000000007
N = int(input())

def reduce(vec):
	vec = list(vec)
	if vec[0]==0:
		if vec[1] == 0:
			return (0,0)
		else:
			return (0,1)
	elif vec[1] == 0:
		return (1,0)
	else:
		if vec[0]<0:
			vec[0] = -vec[0]
			vec[1] = -vec[1]
		d = gcd(vec[0],vec[1])
		return (vec[0]//d, vec[1]//d)

counter0 = defaultdict(int)
counter1 = defaultdict(int)
origin = 0

for i in range(N):
	a,b = map(int, input().split())
	if a==0 and b==0:
		origin += 1
		continue
	a,b = reduce((a,b))
	if b>0:
		counter0[(a,b)] += 1
	else:
		counter0[(-b,a)] += 0
		counter1[(-b,a)] += 1

ans = origin
k = 1
for key, cnt0 in counter0.items():
	cnt1 = counter1[key]
	tmp = (pow(2, cnt0, mod) + pow(2, cnt1, mod) - 1)% mod
	k = (k*tmp) % mod

ans = ans + k-1
ans %= mod
print(ans)

Submission status: Accepted

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

dickey = list(dic.keys())
s = set(dickey)
nopair = N-zero-r_zero-l_zero
ans = pow(2, r_zero, mod)+pow(2, l_zero, mod)-1
for a, b in dickey:
    if a*b>0 and (b, -a) in s:
        ans *= (pow(2, dic[(a, b)], mod)+pow(2, dic[(b, -a)], mod)-1)%mod
        nopair -= (dic[(a, b)]+dic[(b, -a)])
ans *= pow(2, nopair, mod)
print((ans-1+zero)%mod)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
p = 10**9 + 7
iwashi = {}
bad = 0
ans = 1
for i in range(n):
    x, y = map(int, input().split())
    if(x == 0 and y == 0):
      bad += 1
      continue
    elif(x == 0):
        try:
        	iwashi[(0, 1)] += 1
        except KeyError:
            iwashi[(0, 1)] = 1
            continue
    elif(y == 0):
        try:
        	iwashi[(1, 0)] += 1
        except KeyError:
            iwashi[(1, 0)] = 1
        continue
    else:
        g = gcd(x, y)
        x, y = x // g, y // g
        if x < 0:
            x, y = -x, -y
        try:
        	iwashi[(x, y)] += 1
        except KeyError:
            iwashi[(x, y)] = 1
            
for x, y in iwashi:
    a = iwashi[(x, y)]
    if y > 0:
    	rx,ry = y, -x
    else:
      	rx,ry = -y, x
    try:
        b = iwashi[(rx,ry)]
        iwashi[(rx,ry)] = 0
    except KeyError:
      	b = 0
    ans *= pow(2, a, p) + pow(2, b, p) - 1
    ans %= p
    iwashi[(x, y)] = 0
print((ans + bad - 1) % p)

Submission status: Accepted

Solution code:
import math

n = int(input())
ab = []
for i in range(n):
  ab.append(tuple(map(int,input().split())))
MOD = 1000000007

d = {}
zero = 0
for a,b in ab:
  if a == 0 and b == 0:
    zero += 1
    continue
  g = math.gcd(a,b)
  a //= g
  b //= g
  if b < 0:
    a,b = -a,-b
  elif a < 0 and b == 0:
    a = -a
  rot90 = False
  if a <= 0:
    a,b = b,-a
    rot90 = True
  if (a,b) in d:
    if rot90:
      d[(a,b)][1] += 1
    else:
      d[(a,b)][0] += 1
  else:
    if rot90:
      d[(a,b)] = [0,1]
    else:
      d[(a,b)] = [1,0]
#print(d)

ans = 1
for k,v in d.items():
  tmpans = pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
  tmpans %= MOD
  ans *= tmpans
  ans %= MOD
ans -= 1
ans += zero
print(ans%MOD)

Submission status: Accepted

Solution code:
import math

n = int(input())
ab = []
for i in range(n):
  ab.append(tuple(map(int,input().split())))
MOD = 1000000007

d = {}
zero = 0
for a,b in ab:
  if a == 0 and b == 0:
    zero += 1
    continue
  g = math.gcd(a,b)
  a //= g
  b //= g
  if b < 0:
    a,b = -a,-b
  elif a < 0 and b == 0:
    a = -a
  rot90 = False
  if a <= 0:
    a,b = b,-a
    rot90 = True
  if (a,b) in d:
    if rot90:
      d[(a,b)][1] += 1
    else:
      d[(a,b)][0] += 1
  else:
    if rot90:
      d[(a,b)] = [0,1]
    else:
      d[(a,b)] = [1,0]
#print(d)

ans = 1
for k,v in d.items():
  tmpans = pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
  tmpans %= MOD
  ans *= tmpans
ans -= 1
ans += zero
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys, math

max_int = 1000000001  # 10^9+1
min_int = -max_int

n = int(sys.stdin.readline())
positive_counter = {}
negative_counter = {}
to_add = 0
a_zero_counter = b_zero_counter = 0
for _n in range(n):
    s = sys.stdin.readline()
    a, b = map(int, s.split())

    if a == 0 and b == 0:
        to_add += 1
        continue
    elif a == 0:
        a_zero_counter += 1
        continue
    elif b == 0:
        b_zero_counter += 1
        continue
    elif (a > 0) == (b > 0):
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a, b)
        definer = (a // gcd, b // gcd)

        if definer not in positive_counter:
            positive_counter[definer] = 1
        else:
            positive_counter[definer] += 1
    else:
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a, b)
        definer = (b // gcd, a // gcd)

        if definer not in negative_counter:
            negative_counter[definer] = 1
        else:
            negative_counter[definer] += 1

prod = 2 ** a_zero_counter + 2 ** b_zero_counter - 1
#print(positive_counter, negative_counter)
for k in positive_counter:
    if k in negative_counter:
        prod *= 2 ** positive_counter[k] + 2 ** negative_counter[k] - 1
        negative_counter.pop(k)
    else:
        prod *= 2 ** positive_counter[k]
    prod %= 1000000007

for k in negative_counter:
    prod *= 2 ** negative_counter[k]
    prod %= 1000000007

prod += to_add - 1

print(prod % 1000000007)

Submission status: Accepted

Solution code:
import math
def main():
    N = int(input())
    d = {}
    za = zb = zab = r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a, b = -a, -b
            x = math.gcd(abs(a), abs(b))
            d[(a//x, b//x)] = d.get((a//x, b//x), 0) + 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
        else:
            t = (abs(b), abs(a))
        used.add(t)
        l.append((d[x], d.get(t, 0)))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return (r - 1 + zab) % mod
print(main())

Submission status: Accepted

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((d[x], 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((d[x], 0))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return (r - 1 + zab) % mod
print(main())

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
mod = 1000000007

def Sign(n):
    if n > 0:
        return 1
    elif n < 0:
        return -1
    else:
        return 0

allZeros = 0
vectors = dict()


def add_positive(_):
    if _ not in vectors:
        vectors[_] = (1, 0)
    else:
        vectors[_] = (vectors[_][0] + 1, vectors[_][1])


def add_negative(_):
    if _ not in vectors:
        vectors[_] = (0, 1)
    else:
        vectors[_] = (vectors[_][0], vectors[_][1] + 1)


for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        allZeros += 1
        continue
    gcd = math.gcd(a, b)

    key = (0, 0)
    if a == 0:
        key = (1, 0)
        add_negative(key)
    elif b == 0:
        key = (1, 0)
        add_positive(key)

    elif Sign(a) * Sign(b) > 0:
        key = (abs(a) // gcd, abs(b) // gcd)
        add_positive(key)
    else:
        key = (abs(b) // gcd, abs(a) // gcd)
        add_negative(key)

total = 1
for vec in vectors.values():

    total *= ((2**(vec[0]))
              + (2**(vec[1])) - 1) % mod

print(((total- 1) % mod + allZeros % mod) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
def GCD(a,b):
    gc = gcd(a,b)
    a//=gc
    b//=gc
    return a,b

zero = 0
First_quadrant = defaultdict(int)
Second_quadrant = defaultdict(int)
n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    if a == 0 and b == 0:
        zero +=1
    elif a*b >= 0 and b != 0:
        First_quadrant[(GCD(abs(a),abs(b)))] +=1
    else:
        Second_quadrant[(GCD(abs(b), abs(a)))] +=1
        First_quadrant[(GCD(abs(b), abs(a)))] +=0

ans = 1
for key1, val in  First_quadrant.items():

    v2 = Second_quadrant[key1]
    ans *= (2**val + 2**v2 -1)
    ans %= (10**9+7)
ans  = ans + zero -1
ans %= (10**9+7)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,*ab = map(int, read().split())

    ab_zero = 0
    ratio = []
    for a, b in zip(*[iter(ab)]*2):
        if a == 0 and b == 0:
            ab_zero += 1
        else:
            if b < 0:
                a, b = -a, -b
            if b == 0:
                a = 1
            g = gcd(a, b)
            a //= g
            b //= g
            ratio.append((a, b))
    
    s = Counter(ratio)

    bad = 1
    no_pair = 0
    for k, v in s.items():
        a, b = k
        if a > 0:
            if (-b, a) in s:
                bad *= pow(2, v, MOD) + pow(2, s[(-b, a)], MOD) -1
                bad %= MOD
            else:
                no_pair += v
            
        elif (b, -a) not in s:
            no_pair += v

    bad *= pow(2, no_pair, MOD)
    bad %= MOD

    ans = (bad + ab_zero -1) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,*ab = map(int, read().split())

    ab_zero = 0
    ratio = []
    for a, b in zip(*[iter(ab)]*2):
        if a == 0 and b == 0:
            ab_zero += 1
        else:
            if b < 0:
                a, b = -a, -b
            if b == 0:
                a = 1
            g = gcd(a, b)
            a //= g
            b //= g
            ratio.append((a, b))
    ab_zero %= MOD
    
    s = Counter(ratio)

    bad = 1
    for k, v in s.items():
        if v == 0:
            continue
        a, b = k
        if (-b, a) in s:
            bad *= (pow(2, v, MOD) + pow(2, s[(-b, a)], MOD) -1) % MOD
            bad %= MOD            
            s[(-b, a)] = 0
        elif (b, -a) in s:
            bad *= (pow(2, v, MOD) + pow(2, s[(b, -a)], MOD) -1) % MOD
            bad %= MOD            
            s[(b, -a)] = 0
        else:
            bad *= pow(2, v, MOD)
            bad %= MOD            
        s[k] = 0

    ans = (bad + ab_zero -1) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,*ab = map(int, read().split())

    ab_zero = 0
    ratio = []
    for a, b in zip(*[iter(ab)]*2):
        if a == 0 and b == 0:
            ab_zero += 1
        else:
            g = gcd(a, b)
            a //= g
            b //= g
            ratio.append((a, b))
    ab_zero %= MOD
    
    s = Counter(ratio)

    bad = 1
    for k, v in s.items():
        if v == 0:
            continue
        
        a, b = k
        if (-a, -b) in s:
            v += s[(-a, -b)]
            s[(-a, -b)] = 0

        inv = 0
        if (-b, a) in s:
            inv += s[(-b, a)]
            s[(-b, a)] = 0
        if (b, -a) in s:
            inv += s[(b, -a)]
            s[(b, -a)] = 0

        bad *= (pow(2, v, MOD) + pow(2, inv, MOD) -1) % MOD
        bad %= MOD
        s[k] = 0

    ans = (bad + ab_zero -1) % MOD
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

input = sys.stdin.buffer.readline
MOD = 1000000007
N = int(input())
dd = defaultdict(int)
count = 1
iwashi = [list(map(int, input().split())) for _ in range(N)]


checked = defaultdict(bool)
zeros = 0

for i in range(N):
    if iwashi[i][0] == iwashi[i][1] == 0:
        zeros += 1
        continue
    iw = iwashi[i]
    gcd_iw = math.gcd(iw[0], iw[1])
    if gcd_iw != 0:
        iw = list(map(lambda x: x // gcd_iw, iw))
    if iw[0] < 0:
        iw = list(map(lambda x: -x, iw))
    if iw[0] == 0 and iw[1] < 0:
        iw = list(map(lambda x: -x, iw))
    dd[tuple(iw)] += 1

for key, val in dd.items():
    if checked[key]:
        continue
    vert_key = (key[1], -key[0]) if key[1] > 0 else (-key[1], key[0])
    vert_val = dd[vert_key] if vert_key in dd else 0
    count *= (pow(2, val, MOD) - 1) + (pow(2, vert_val, MOD) - 1) + 1
    count %= MOD
    checked[vert_key] = True

# 0匹入れる場合を除外
count -= 1

count += zeros
print(count % MOD)