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:
#!/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, -1 / r))
        else:
            rpairs.add((-1 / r, r))
    ans = 1
    for (r1, r2) in rpairs:
        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())

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, -1 / r))
        else:
            rpairs.add((-1 / r, r))
    ans = 1
    for (r1, r2) in rpairs:
        p = pow(2, cnt_r[r1], MOD) + pow(2, cnt_r[r2], MOD) - 1
        ans *= p % MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans += cnt_ab0
    return (ans - 1) % MOD


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

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


def main():
    N = I()
    zero = 0
    cnts = defaultdict(int)
    used = set()

    for i in range(N):
        a, b = MI()
        if a == 0 and b == 0:
            zero += 1
            continue

        g = gcd(abs(a), abs(b))
        a = a // g
        b = b // g
        if b < 0:
            a = -a
            b = -b
        cnts[(a, b)] += 1

    # print(cnts)

    ans = 1
    for key, c in cnts.items():
        if key in used:
            continue
        a, b = key
        if a > 0:
            rev = (-b, a)
        else:
            rev = (b, -a)

        if rev in cnts:
            ans *= pow(2, cnts[key], MOD) + pow(2, cnts[rev], MOD) - 1
            # print(key, rev, ans)
            ans %= MOD
            used.add(rev)
        else:
            ans *= pow(2, cnts[key], MOD)

    ans += zero
    ans -= 1
    print(ans % MOD)
    # ans = 0
    # for i in range(2 ** N):
    #     groups = []
    #     for j in range(N):
    #         if ((i >> j) & 1):
    #             groups.append(j)

    #     if len(groups) == 0:
    #         continue

    #     c = 1
    #     for i in groups:
    #         for j in groups:
    #             if i == j:
    #                 continue
    #             if A[i] / float(B[i]) == (- B[j] / float(A[j])):
    #                 c = 0
    #                 break
    #     if c == 0:
    #         print(groups)
    #     ans += c
    # print(ans)

    # print(test1)
    # print(test2)
    # all = pow(2, N, MOD) - 1
    # red = 0
    # for i in range(N-1):
    #     left = A[i] / float(B[i])
    #     right = (- B[i] / float(A[i]))
    #     c = mr[left]
    #     if (N - i - 1 - c) >= 0 and c - 1 >= 0:
    #         red += pow(2, (N - i - 1 - c), MOD) * pow(2, c - 1, MOD)
    #         # print((N - i - 1 - c), c - 1)
    #         # print('red', red, 'left', left)
    #         red %= MOD
    #     # print(mr, mr[left])
    #     if ml[left] > 0:
    #         ml[left] -= 1
    #     if mr[right] > 0:
    #         mr[right] -= 1

    # # print(red)
    # print(all - red)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1
done = []
for (i0,i1), din in d.items():
    if (i1,-i0) in done or (-i1,i0) in done:
        continue
    w = d.get((i1,-i0),0) + d.get((-i1,i0),0)
    aaa = (twoxxn(w,mod)+twoxxn(din,mod)-1)%mod
    ans = (ans*aaa)%mod
    done.append((i0,i1))

if len(d.keys()) == 0:
    print(iw0)
    exit()

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

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
twofac=[1]
for i in range(N+1):
    twofac.append(twofac[-1]*2%mod)
twoifac=[pow(mod-2,mod) for i in twofac]

for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=twofac[x]
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=twofac[x]
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=twofac[x]
        x=data[b*idle_max-a]
        if x:
            P*=twofac[x]
    #print(Z,P)
    P%=mod
    c+=P
    c%=mod
    Z+=P
    Z%=mod
    data[a*idle_max+b]+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
twofac=[1]
for i in range(N+1):
    twofac.append(twofac[-1]*2%mod)
twoifac=[pow(mod-2,mod) for i in twofac]

for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=twofac[x]
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=twofac[x]
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=twofac[x]
        x=data[b*idle_max-a]
        if x:
            P*=twofac[x]
    #print(Z,P)
    c+=P
    c%=mod
    Z+=P
    Z%=mod
    data[a*idle_max+b]+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


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

mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0 or a>0 and n<0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
data=defaultdict(int)
c=0
M=0
Z=1
twofac=[1]
for i in range(N+1):
    twofac.append(twofac[-1]*2%mod)
twoifac=[pow(mod-2,mod) for i in twofac]

for i in range(N):
    a,b=AB[i]
    P=Z
    flag=1
    if a==0 and b==0:
        continue
    elif a and b==0:
        x=data[-a]
        if x:
            P*=twofac[x]
    elif a==0 and b:
        x=data[-b*idle_max]
        if x:
            P*=twofac[x]
    else:
        x=data[-b*idle_max+a]
        if x:
            P*=twofac[x]
        x=data[b*idle_max-a]
        if x:
            P*=twofac[x]
    #print(Z,P)
    c+=P
    c%=mod
    Z+=P
    data[a*idle_max+b]+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[str(Fraction(a, b))] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = str(Fraction(a, b))
    if done[k]: continue
    rk = str(Fraction(-b, a))
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from fractions import Fraction
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[Fraction(a, b)] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = Fraction(a, b)
    if done[k]: continue
    rk = Fraction(-b, a)
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
ans %= MOD
print((ans-1)%MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from collections import Counter
slope=Counter()
slope_zero=0
slope_inf=0
both_zero=0
n=int(input())
for _ in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        both_zero+=1
    else:
        if a==0:
            slope_zero+=1
        elif b==0:
            slope_inf+=1
        else:
            sign=(a//abs(a))*(b//abs(b))
            a=abs(a)
            b=abs(b)
            gc=gcd(a,b)
            a//=gc
            b//=gc
            if sign==1:
                slope[(a,b)]+=1
            else:
                slope[(-a,b)]+=1
ans=1
mod=10**9+7
for a,b in slope.keys():
    if slope[(a,b)]>0:
        aa=-b
        bb=a
        if bb<0:
            bb*=-1
            aa*=-1
        if slope[(aa,bb)]>0:
            ans*=(pow(2,slope[(a,b)],mod)+pow(2,slope[(aa,bb)],mod)-1+mod)%mod
            ans%=mod
            slope[(aa,bb)]=0
        else:
            ans*=(pow(2,slope[(a,b)],mod))%mod
            ans%=mod
ans*=(pow(2,slope_zero,mod)+pow(2,slope_inf,mod)-1+mod)%mod
ans%=mod
ans+=both_zero
if ans>=mod:
    ans%=mod
print((ans-1+mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

#from math import gcd
from fractions import Fraction as Fc

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        f = Fc(a,b)
        cnd[f] = cnd.get(f,0)+1


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
    ans = 1
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod

#print(cnd)
for k,item in cnd.items():
#    print(k)
    if k>0:
        m = cnd.get(Fc(-1,k),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get(Fc(-1,k),False)
#        print(m,k,Fc(-1,k))
        if not m:
            noreg += item
#    print(ans,noreg)
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  dic[Fraction(A,B)][0]+=1
  dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 if k>0:
  ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
  ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import math

n = int(input())


ab = []
ba = []

a0 = 0
b0 = 0
ab0 = 0

for i in range(n):
    a, b = map(int, input().split())
    if a != 0 and b != 0:
        ab.append(Fraction(a, b))
        ba.append(Fraction(-b, a))
    elif a == 0 and b == 0:
        ab0 += 1
    elif a == 0 and b != 0:
        a0 += 1
    elif a != 0 and b == 0:
        b0 += 1


d_ab = dict()
d_ba = dict()

# d_done = dict()

for i in range(len(ab)):
    cur = ab[i]
    if cur in d_ab:
        d_ab[cur] += 1
    else:
        d_ab[cur] = 1

    cur = ba[i]
    if cur in d_ba:
        d_ba[cur] += 1
    else:
        d_ba[cur] = 1

mod = 1000000007
ans = 1

d_done = set()

for k, v in d_ab.items():
    x = v
    if k in d_ba:
        if k in d_done:
            continue
        else:
            y = d_ba[k]
            kake = 0
            kake += ((2**x) % mod + (2**y) % mod - 1)
            ans *= kake
            ans %= mod
            # d_done[Fraction(-k.denominator, k.numerator)] = 1
            d_done.add(Fraction(-k.denominator, k.numerator))
    else:
        kake = (2**x) % mod
        ans *= kake
        ans %= mod

ans *= ((2**a0) % mod+(2**b0) % mod-1)
ans %= mod

ans -= 1

ans += ab0
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
p=12231472983974394769
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,p-2,p)%p)
  elif a*b<0:
    AA.append(a*pow((-b),p-2,p)%p)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from fractions import Fraction

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1
#print(cnd)
for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]%mod+2**item[1]%mod-1)%mod
        ans %= mod
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    flip = 0
    while not (a > 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
p=313991399371199131139799331911377
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,p-2,p)%p)
  elif a*b<0:
    AA.append(a*pow((-b),p-2,p)%p)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = {}
  dd_flag = {}
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      ba = Fraction(-b, a)
      ab = Fraction(a, b)
      if ba in dd_ba:
        dd_ba[ba] += 1
      else:
        dd_ba[ba] = 1
      
      if not(ab in dd_ba):
        dd_ba[ab] = 0
        
      dd_flag[ba] = False
      dd_flag[ab] = False

  ans = (2**zero_one_count + 2**one_zero_count -1)

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

from fractions import Fraction

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a*b == 0:
        if a == 0 and b != 0:
            azero += 1
        elif a != 0 and b == 0:
            bzero += 1
        else:
            allzero += 1
    else:
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        check = cnd.get(-1*Fraction(1,ratio),False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        elif check:
            cnd[-1*Fraction(1,ratio)] = [check[0],check[1]+1]
        else:
            cnd[ratio] = [1,0]

cnd[0] = [azero,bzero]
noreg = 0
ans = 1
#print(cnd)
for item in cnd.values():
    if item[0] == 0  or item[1] == 0:
        noreg += max(item[0],item[1])
    else:
        ans *= (2**item[0]%mod+2**item[1]%mod-1)%mod
        ans %= mod
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif (a > 0) ^ (b > 0):
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if Fraction(A,B)>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  iterator = dd_ba.copy().items()
  for key,value in iterator:
    if dd_flag[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

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

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction
import math

n = int(input())


ab = []
ba = []

a0 = 0
b0 = 0
ab0 = 0

for i in range(n):
    a, b = map(int, input().split())
    if a != 0 and b != 0:
        ab.append(Fraction(a, b))
        ba.append(Fraction(-b, a))
    elif a == 0 and b == 0:
        ab0 += 1
    elif a == 0 and b != 0:
        a0 += 1
    elif a != 0 and b == 0:
        b0 += 1


d_ab = dict()
d_ba = dict()

d_done = dict()

for i in range(len(ab)):
    cur = ab[i]
    if cur in d_ab:
        d_ab[cur] += 1
    else:
        d_ab[cur] = 1

    cur = ba[i]
    if cur in d_ba:
        d_ba[cur] += 1
    else:
        d_ba[cur] = 1

mod = 1000000007
ans = 1

for k, v in d_ab.items():
    x = v
    if k in d_ba:
        if k in d_done:
            continue
        else:
            y = d_ba[k]
            kake = 0
            kake += ((2**x) % mod + (2**y) % mod - 1)
            ans *= kake
            ans %= mod
            d_done[Fraction(-k.denominator, k.numerator)] = 1
    else:
        kake = (2**x) % mod
        ans *= kake
        ans %= mod

ans *= ((2**a0) % mod+(2**b0) % mod-1)
ans %= mod

ans -= 1

ans += ab0
ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from fractions import Fraction

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
  from fractions import Fraction
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool, {})

  iterator = list(dd_ba.items())
  for key,value in iterator:
    if flag_dd[key]:
      continue
    x = Fraction(key.denominator, -(key.numerator))
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[x] = True

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

if __name__=='__main__':
  main()