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: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict

N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N)]
MOD = 10**9 + 7

d = defaultdict(int)
cnt_00 = 0
cnt_0b = 0
cnt_a0 = 0
for a,b in AB:
    if a == b == 0:
        cnt_00 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_0b += 1
    else:
        num_gcd = math.gcd(a,b)
        grad = 1 if a * b > 0 else -1

        d[(grad, abs(a // num_gcd), abs(b // num_gcd))] += 1

ks = tuple(d.keys())

ans = 1
for k in ks:
    if d[k] == 0:
        continue
    
    grad, a, b = k[0], k[1], k[2]
    if (-grad, b, a) in ks:
        
        # 傾き a/bのものを一つ以上選ぶ場合（-b/aは選ばない） + -b/aから一つ以上選ぶ場合（a/bは選ばない） + どちらからも選ばない場合
        ans *= (pow(2, d[(grad, a, b)], MOD)-1) + (pow(2, d[(-grad, b, a)], MOD)-1) + 1
        ans %= MOD
        d[(grad, a, b)] = 0
        d[(-grad, b, a)] = 0
    else:
        # a/bから0個以上選ぶ場合
        ans *= pow(2, d[(grad, a, b)], MOD)
        ans %= MOD
        d[(grad, a, b)] = 0

# a,bの一方のみ0の場合 + どちらからも選ばない場合
ans *= (pow(2, cnt_a0, MOD)-1) + (pow(2, cnt_0b, MOD)-1) + 1
ans %= MOD

# 0,0のみを１つだけ入れる場合
ans += cnt_00
# なにも選ばない場合を除く
ans -= 1

ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        q, r = divmod(b, a)
        a, b = r, a
        u, v = v - q * u, u
    if b < 0:
        v = -v
    if v < 0:
        v += P
    return v

pair_key = {0:-1, -1:0}

def to_key(a, b):
    if a == 0:
        return -1
    if b == 0:
        return 0
    x = inv_mod(a) * b % P
    y = P - (inv_mod(b) * a % P)
    pair_key[x] = y
    return x

  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key[key]
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        q, r = divmod(b, a)
        a, b = r, a
        u, v = v - q * u, u
    if b < 0:
        v = -v
    if v < 0:
        v += P
    return v

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    if v < 0:
        v += P
    return v

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % P

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow2[cnt]
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow2[x] + pow2[y] - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 61 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

@lru_cache(None)
def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % P

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow(2, cnt, MOD)
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow(2, x, MOD) + pow(2, y, MOD) - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from functools import lru_cache

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

@lru_cache(None)
def inv_mod(a):
    b = P
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % P

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow(2, cnt, MOD)
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow(2, x, MOD) + pow(2, y, MOD) - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a, b=P):
    b0 = b
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % b0

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow(2, cnt, MOD)
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow(2, x, MOD) + pow(2, y, MOD) - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from fractions import Fraction
def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N)]
    MOD = 10**9+7

    from collections import Counter
    ctr = Counter()
    az = bz = zz = 0
    for a,b in AB:
        if a==b==0:
            zz += 1
        elif a==0:
            az += 1
        elif b==0:
            bz += 1
        else:
            f = Fraction(a,b)
            ctr[f] += 1
    ans = pow(2,az,MOD) + pow(2,bz,MOD) - 1

    used = set()
    for f1,v in ctr.items():
        if f1 in used: continue
        f2 = -1/f1
        if f2 in ctr:
            used.add(f2)
        r = pow(2,v,MOD) + pow(2,ctr[f2],MOD) - 1
        ans *= r
        ans %= MOD
    ans += zz - 1
    ans %= MOD
    print(ans)
solve()

Submission status: Time Limit Exceeded

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

input=sys.stdin.readline
def main():
  ans=1
  mod=1000000007
  n0=0
  na=nb=0
  n=int(input())
  d={}

  for i in range(n):
      a,b=map(int,input().split())
      if b==0 and a==0:
          n0+=1
      elif b==0:
          nb+=1
      elif a==0:
          na+=1
      else:
          if Fraction(a, b) not in d:
              d[Fraction(a, b)]=1
          else:
              d[Fraction(a, b)]+=1

  for i in d.keys():
      if Fraction(-1,i) in d:
          if i>0:
              ans*=pow(2,d[Fraction(-1, i)])-1+pow(2,d[i])-1+1
              ans=ans%mod
      else:
          ans*=pow(2,d[i])
          ans=ans%mod
  ans*=pow(2,na)-1+pow(2,nb)-1+1
  print((ans-1+n0)%mod)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys,pprint
from fractions import Fraction
from collections import defaultdict

MOD = 1000000007
N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(int)
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
    elif bi == 0:
        zerodiv += 1
    else:
        t = Fraction(ai,bi)
        tilts[t] += 1

# print(tilts,file=sys.stderr)

ans = 1
f1 = Fraction(0,1)
if f1 in tilts:
    ans *= 1+pow(2,tilts[f1],MOD)-1 + pow(2,zerodiv,MOD)-1
    del tilts[f1]
else:
    ans *= 1 + pow(2,zerodiv,MOD)-1
ans %= MOD

klist = list(tilts.keys())
for k in klist:
    kinv = Fraction(-1*k.denominator,k.numerator)
    if kinv in tilts:
        #print(k,kinv, file=sys.stderr)
        ans *= 1+pow(2,tilts[k],MOD) -1+pow(2,tilts[kinv],MOD)-1
        ans %= MOD
        del tilts[k]
        del tilts[kinv]
    else:
        ans *= 1+pow(2,tilts[k],MOD)-1
        ans %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys,pprint
from fractions import Fraction
from collections import defaultdict

N = int(input())
params =[]
hatemasks = []
tilts = defaultdict(int)
zerozero = 0
zerodiv = 0
for i in range(N):
    (ai, bi) = map(int,input().split())
    if ai == 0 and bi == 0:
        zerozero += 1
    elif bi == 0:
        zerodiv += 1
    else:
        t = Fraction(ai,bi)
        tilts[t] += 1

print(tilts,file=sys.stderr)

ans = 1
f1 = Fraction(0,1)
if f1 in tilts:
    ans *= 1+pow(2,tilts[f1])-1 + pow(2,zerodiv)-1
    del tilts[f1]
else:
    ans *= 1 + pow(2,zerodiv)-1

klist = list(tilts.keys())
for k in klist:
    kinv = Fraction(-1*k.denominator,k.numerator)
    if kinv in tilts:
        #print(k,kinv, file=sys.stderr)
        ans *= 1+pow(2,tilts[k]) -1+pow(2,tilts[kinv])-1
        del tilts[k]
        del tilts[kinv]
    else:
        ans *= 1+pow(2,tilts[k])-1

print((ans + zerozero -1)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd
from fractions import Fraction

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    inf = 10**18+1
    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for i, (ai, bi) in enumerate(zip(it, it)):
        if ai * bi  == 0:
            if ai != 0:
                ai = inf
                bi = 1
            elif bi != 0:
                ai = -1
                bi = inf
            else:
                z0 += 1
                continue
        val = Fraction(ai, bi)
        d1[0 if val >= 0 else 1][val] += 1

    a1, a2 = d1
    ans = 1
    for k, v in a1.items():
        ik = -1/k
        if ik in a2:
            v2 = a2[ik]
            ans *= pow(2, v+v2, mod) - (pow(2, v, mod)-1)*(pow(2, v2, mod)-1)
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for k, v in a2.items():
        ik = -1/k
        if not ik in a1:
            ans *= pow(2, v, mod)
            ans %= mod

    print(ans-1+z0)



if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases += 1
    elif a * b >=0 and b != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans+zero_cases-1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque, Counter, defaultdict
from fractions 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: Time Limit Exceeded

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

INF = int(1e10)
MOD = int(1e9 + 7)

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    n = int(input())
    count = 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:
            count += 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
    ans -= 1
    ans += count
    ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import collections
import fractions
from fractions import Fraction
from collections import defaultdict
import math

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        x=i
        y=j
        i //= math.gcd(x, y)
        j //= math.gcd(x, y)
        b[Fraction(i,j)]+=1
        c[Fraction(j,i)]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0,mod)-1)*(pow(2,b0,mod)-1))


for k,v in b.items():
    if c[-k]!=0:
        ans*=(pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1))
        w.append((pow(2,c[-k]+v,mod)-(pow(2,c[-k],mod)-1)*(pow(2,v,mod)-1)))
        ans%=mod
    else:
        ans*=pow(2,v,mod)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import collections
import fractions
from fractions import Fraction
from collections import defaultdict
import math

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    if i!=0 and j!=0:
        x=i
        y=j
        i //= math.gcd(x, y)
        j //= math.gcd(x, y)
        b[Fraction(i,j)]+=1
        c[Fraction(j,i)]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0)-1)*(pow(2,b0)-1))


for k,v in b.items():
    if c[-k]!=0:
        ans*=((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        w.append((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        ans%=mod
    else:
        ans*=pow(2,v)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)

    pow2 = [1] * (N + 1)
    for i in range(1, N + 1):
        pow2[i] = (pow2[i - 1] << 1) % MOD

    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow2[cnt_r[r1]] + pow2[cnt_r[r2]] - 1
        ans *= p % MOD
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0 - 1
    return ans % MOD


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
# INF = 1e18+10

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

n = int(input())

a_b = [() for i in range(n)]
m_b_a = [() for i in range(n)]

a_b_value_indices = {}
m_b_a_value_indices = {}

a_b_value_rep = {}
m_b_a_value_rep = {}

used = [False for _ in range(n)]
zeroes = 0
is_zero = [False for _ in range(n)]

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

	if a == 0 and b == 0:
		zeroes += 1
		used[i] = True
		is_zero[i] = True
	else:
		if a == 0:
			a_b[i] = (0, 1)
			m_b_a[i] = (1, 0)
		elif b == 0:
			a_b[i] = (1, 0)
			m_b_a[i] = (0, 1)
		else:
			neg = False
			if a*b < 0:
				neg = True
			d = gcd(abs(a), abs(b))
			a = abs(a) // d
			b = abs(b) // d

			if neg:
				a_b[i] = (-a, b)
				m_b_a[i] = (b, a)
			else:
				a_b[i] = (a, b)
				m_b_a[i] = (-b, a)

		# a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		a_b_value_indices[a_b[i]] = a_b_value_indices.get(a_b[i], []) + [i]
 
		# m_b_a_value_count[m_b_a[i]] = m_b_a_value_count.get(m_b_a, 0) + 1
		m_b_a_value_indices[m_b_a[i]] = m_b_a_value_indices.get(m_b_a[i], []) + [i]
		if a_b[i] not in a_b_value_rep:
			a_b_value_rep[a_b[i]] = i
		if m_b_a[i] not in m_b_a_value_rep:
			m_b_a_value_rep[m_b_a[i]] = i

ans = 1
for i in range(n):
	if not is_zero[i] and not used[a_b_value_rep[a_b[i]]]:
		# if not connected
		if a_b[i] not in m_b_a_value_indices:
			ans *= pow(2, len(a_b_value_indices[a_b[i]]), MODULO)
			ans %= MODULO
			used[a_b_value_rep[a_b[i]]] = True
			# for j in a_b_value_indices[a_b[i]]:
			# 	used[j] = True
		else:
			s = len(a_b_value_indices[a_b[i]])
			t = len(m_b_a_value_indices[a_b[i]])
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO

			used[a_b_value_rep[a_b[i]]] = True
			used[m_b_a_value_rep[a_b[i]]] = True
			# for j in m_b_a_value_indices[a_b[i]]:
			# 	used[j] = True
 
			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)
 
 
# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
# INF = 1e18+10

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

n = int(input())

a_b = [() for i in range(n)]
m_b_a = [() for i in range(n)]

a_b_value_indices = {}
m_b_a_value_indices = {}
used = [False for _ in range(n)]
zeroes = 0

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

	if a == 0 and b == 0:
		zeroes += 1
		used[i] = True
	else:
		if a == 0:
			a_b[i] = (0, 1)
			m_b_a[i] = (1, 0)
		elif b == 0:
			a_b[i] = (1, 0)
			m_b_a[i] = (0, 1)
		else:
			neg = False
			if a*b < 0:
				neg = True
			d = gcd(abs(a), abs(b))
			a = abs(a) // d
			b = abs(b) // d

			if neg:
				a_b[i] = (-a, b)
				m_b_a[i] = (b, a)
			else:
				a_b[i] = (a, b)
				m_b_a[i] = (-b, a)

		# a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		a_b_value_indices[a_b[i]] = a_b_value_indices.get(a_b[i], []) + [i]
 
		# m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1
		m_b_a_value_indices[m_b_a[i]] = m_b_a_value_indices.get(m_b_a[i], []) + [i]

ans = 1
for i in range(n):
	if not used[i]:
		# not connected
		if a_b[i] not in m_b_a_value_indices:
			ans *= pow(2, len(a_b_value_indices[a_b[i]]), MODULO)
			ans %= MODULO
			for j in a_b_value_indices[a_b[i]]:
				used[j] = True
		else:
			s = len(a_b_value_indices[a_b[i]])
			t = len(m_b_a_value_indices[a_b[i]])
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO
 
			for j in a_b_value_indices[a_b[i]]:
				used[j] = True
			for j in m_b_a_value_indices[a_b[i]]:
				used[j] = True
 
			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)
 
 
# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)
    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow(2, cnt_r[r1], MOD) + pow(2, cnt_r[r2], MOD) - 1
        ans *= p % MOD
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0 - 1
    return ans % MOD


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
A, B = [], []
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    A.append(a)
    B.append(b)
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)
    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow(2, cnt_r[r1], MOD) + pow(2, cnt_r[r2], MOD) - 1
        ans *= p
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans += cnt_ab0 - 1
    return ans % MOD


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
A, B = [], []
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = {}

for i in range(N):
    a, b = nm()
    A.append(a)
    B.append(b)
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        if r not in cnt_r:
            cnt_r[r] = 0
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)
    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow(2, cnt_r.get(r1, 0), MOD) + pow(2, cnt_r.get(r2, 0), MOD) - 1
        ans *= p % MOD
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0 - 1
    return ans % MOD


if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
A, B = [], []
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    A.append(a)
    B.append(b)
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)
    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow(2, cnt_r[r1], MOD) + pow(2, cnt_r[r2], MOD) - 1
        ans *= p % MOD
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0
    return (ans - 1) % MOD


if __name__ == "__main__":
    print(solve())