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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd

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

t = set()
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.add((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
if (0, 0) in t:
    t.remove((0, 0))

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

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

MOD = 1000000007

box = defaultdict(int)
zeros = 0
for a, b in AB:
  if a == b == 0:
    zeros += 1
  else:
    if a != 0 and b == 0:
      box[(-1, 1, 0)] += 1
    elif a == 0 and b != 0:
      box[(1, 0, 1)] += 1
    else:
      g = gcd(a, b)
      ga = a // g
      gb = b // g
      if (a // b) < 0:
        s = -1
      else:
        s = 1
      box[(s, abs(ga), abs(gb))] += 1
   
nakawaru = dict()
others = 0

for (s, i, j), v in box.items():
    if (-s, j, i) in box.keys():
        if (s, i, j) not in nakawaru.keys() and (-s, j, i) not in nakawaru.keys():    
            nakawaru[(s, i, j)] = (box[(s, i, j)], box[(-s, j, i)])
    else:
        others += v

seed = 1
for i, j in nakawaru.values():
    seed *= (pow(2, i, MOD) + pow(2, j, MOD) - 1)
    seed %= MOD

ans = zeros + pow(2, others, MOD) * seed - 1
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

n = int(input())

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


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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    zero = 0
    d = defaultdict(lambda: defaultdict(int))
    for i in range(N):
        A, B = map(int, input().split())
        if A == 0 and B == 0:
            zero += 1
            continue
        if B < 0:
            A = -A
            B = -B
        flag = False
        if A <= 0:
            A, B = B, -A
            flag = True
        g = gcd(A,B)
        A //= g
        B //= g
        if flag:
            d[(A,B)]['first'] += 1
        else:
            d[(A,B)]['second'] += 1
    ans = 1
    for i, j in d.items():
        now = 1
        now += pow(2,j['first'],MOD) - 1
        now += pow(2,j['second'],MOD) - 1
        ans *= now
        ans %= MOD
    ans -= 1
    ans += zero
    ans %= MOD
    print(ans)




    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数(計算で使用したらカウント)
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict
n=int(input())
A=defaultdict(int)
AA=defaultdict(int)
B=[]
C=[]
X=[]
mod=10**9+7
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    l=a*b//gcd(a,b)
    A[str(l//b)+":"+str(l//a)]+=1
  elif a*b<0:
    l=a*(-b)//gcd(a,-b)
    AA[str(l//a)+":"+str(l//(-b))]+=1
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
E=set(list(A.keys())+list(AA.keys()))
a=1
for i in E:
  a=(a*(2**A[i]+2**AA[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict
MOD = 10**9+7
n = int(input())
cnt = defaultdict(lambda: [0, 0])
zeros = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    if a < 0 or (a == 0 and b < 0):
        a *= -1
        b *= -1
    g = gcd(a, b)
    a //= g
    b //= g
    if b > 0:
        cnt[(a, b)][0] += 1
    else:
        cnt[(-b, a)][1] += 1

ans = 1
for v, v2 in cnt.values():
    ans *= 1+pow(2, v, MOD)-1+pow(2, v2, MOD)-1
    ans %= MOD
ans = (ans+zeros-1) % MOD
print(ans)

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict

def preproc(a,b): # a != 0 or b != 0
    if a < 0:
        a,b = -a,-b
    if a == 0 or b == 0:
        return (a, b)
    GCD = math.gcd(a,b)
    return (a // GCD, b // GCD)

n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
mod = 1000000007
dic = defaultdict(int)
A = 0
B = 0
AB = 0
for k,(a,b) in enumerate(ab):
    if a == 0 and b == 0:
        AB += 1
        n -= 1
        continue
    a,b = preproc(a,b)
    if a == 0:
        A += 1
        n -= 1
    elif b == 0:
        B += 1
        n -= 1
    else:
        dic[(a,b)] += 1
ok = (pow(2,A,mod) + pow(2,B,mod) - 1) % mod
c = copy.copy(dic)
for k,v in c.items():
    if not dic[k]:
        continue
    a,b = k
    pair = (b,-a) if b > 0 else (-b,a)
    if dic[pair]:
        ok *= pow(2,v,mod) + pow(2,dic[pair],mod) - 1
        ok %= mod
        n -= v + dic[pair]
        dic[pair] = 0
ans = ok * pow(2,n,mod) - 1 + AB
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict
MOD = 10**9+7
n = int(input())
cnt = defaultdict(lambda: [0, 0])
zeros = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    if a < 0:
        a *= -1
        b *= -1
    g = gcd(a, b)
    a //= g
    b //= g
    if b > 0:
        cnt[(a, b)][0] += 1
    else:
        if a == 0 and b < 0:
            cnt[(a, -b)][0] += 1
        else:
            cnt[(-b, a)][1] += 1

ans = 1
for v, v2 in cnt.values():
    ans *= 1+pow(2, v, MOD)-1+pow(2, v2, MOD)-1
    ans %= MOD
ans = (ans+zeros-1) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math
double_zero_cnt = 0
a_zero_cnt = 0
b_zero_cnt = 0
d = defaultdict(list) # [a, b] ngのそれぞれの個数
a_b = []
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    elif a == 0:
        a_zero_cnt += 1
        continue
    elif b == 0:
        b_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        b *= (-1)
        a *= (-1) # 必ずbは正
    a_b.append((a, b))
c = Counter(a_b)
key_list = list(c.keys())
for key in key_list:
    a, b = key
    if a < 0:
        a_ = a*(-1)
        b_ = b*(-1)
    else:
        a_ = a
        b_ = b
    if d[(-b_, a_)] != []:
        continue
    if c[(-b_, a_)] != 0:
        d[(a, b)] = [c[(a, b)], c[(-b_, a_)]]
ans = 1
used_cnt = double_zero_cnt
for key in d.keys():
    if d[key] == []:
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod
    ans *= mul
    ans %= mod
if a_zero_cnt > 0 and b_zero_cnt > 0:
    ans *= (pow(2, a_zero_cnt, mod) + pow(2, b_zero_cnt, mod) - 1)
    ans %= mod
    used_cnt += a_zero_cnt + b_zero_cnt
elif a_zero_cnt > 0:
    ans *= pow(2, a_zero_cnt, mod)
    ans %= mod
    used_cnt += a_zero_cnt
elif b_zero_cnt > 0:
    ans *= pow(2, b_zero_cnt, mod)
    ans %= mod
    used_cnt += b_zero_cnt
ans *= pow(2, n - (used_cnt), mod)
ans %= mod
ans -= 1
ans += double_zero_cnt
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

mod=10**9+7
n=int(input())
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    else:
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a!=0 and b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)],mod)
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      ans*=(pow(2,cnt1,mod)+pow(2,cnt2,mod)-1)%mod
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)],mod)
      ans%=mod
print((ans+cnt-1)%mod)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction
from collections import Counter
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


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)


def fract(a, b):
    if a == 0 and b == 0:
        return (0, 0)
    if b == 0:
        return (1, 0)
    f = Fraction(a, b)
    return f.numerator, f.denominator


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        k = fract(a, b)
        adb[k] += 1
    M = Mod(1000000007)
    ans = 1
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        kk = fract(-b, a)
        done.add(k)
        done.add(kk)

        n = adb[kk]
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)
    ans = M.add(ans, adb[(0, 0)])
    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: Accepted

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction
from collections import Counter
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 fract(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:
        k = fract(a, b)
        adb[k] += 1
    M = Mod(1000000007)
    ans = 1
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        kk = fract(-b, a)
        done.add(k)
        done.add(kk)

        n = adb[kk]
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)
    ans = M.add(ans, adb[(0, 0)])
    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: Accepted

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, 0))
        elif a == 0:
            A_B.append((0, INF))
        else:
            tmp = math.gcd(a,b)
            if a / b > 0 :v = 1
            else: v = -1
            A_B.append((abs(a//tmp), v * abs(b//tmp)))

    comb_dict = defaultdict(lambda:[0,0])

    for ai, bi in A_B:
        if ai == INF:
            comb_dict[0][1] += 1
        elif bi == INF:
            comb_dict[0][0] += 1
        elif bi < 0:
            comb_dict[(ai,bi)][0] += 1
        else:
            comb_dict[(bi, -ai)][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: Accepted

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 fract(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:
        k = fract(a, b)
        adb[k] += 1
    M = Mod(1000000007)
    ans = 1
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        kk = fract(-b, a)
        done.add(k)
        done.add(kk)

        n = adb[kk]
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)
    ans = M.add(ans, adb[(0, 0)])
    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: Accepted

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
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            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)
    ans = M.add(ans, adb[(0, 0)])
    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: Accepted

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
    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:
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//G,y//G))

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

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

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

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 = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

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)