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: Runtime Error

Solution code:
import collections
import decimal
decimal.getcontext().prec = 6

def pow_k(x, n):
    """
    O(log n)
    """
    MOD = 10 ** 9 + 7
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= MOD
        x *= x
        x %= MOD
        n //= 2

    return K * x

n = int(input())

ab = []
l = [] #  b / aを格納
for _ in range(n):
	tmp = list(map(int,input().split()))
	ab.append(tmp)
	l.append(decimal.Decimal(tmp[1]) / decimal.Decimal(tmp[0]))

#print(l)

count = collections.Counter(l)

#print(count)
ans = 0
tmp = n
for i in range(n):
	num = decimal.Decimal(-1) / decimal.Decimal(l[i])
	if num in count:
		N = tmp - count[num] - 1
	else:
		N = tmp - 1
	ans += pow_k(2,N)
	ans %= 1000000007
	#print(N,num,ans)
	count[decimal.Decimal(l[i])] -= 1
	tmp -= 1
	#print(count)

print(ans)

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

    def root(self, x):
        # try:
        return self.v[x] < 0  # (負)は根
        # except:
        #     print(f'{x=}, {self.v=}')

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す


def main():
    from bisect import bisect_left
    from collections import defaultdict
    from math import acos, isclose, pi
    import sys
    input = sys.stdin.readline

    MOD = 10 ** 9 + 7

    N = int(input())
    fs = []
    for _ in range(N):
        a, b = map(int, input().split())
        fs.append((a, b))

    d = defaultdict(int)
    rt2 = 1 / pow(2, 0.5)
    rs = set()
    for a, b in fs:
        rad = acos((a + b) * rt2 / (a * a + b * b) ** 0.5)
        d[rad] += 1
        rs.add(rad)

    *rs, = sorted(rs)
    uf = UnionFind(len(rs))
    rs.append(1 << 10)
    for j, rad in enumerate(rs[:-1]):
        for rr in (pi * 3 / 2 - rad, pi / 2 - rad, rad + pi / 2, rad + pi * 3 / 2):
            i = bisect_left(rs, rr)
            if isclose(rs[i], rr):
                # print(f'{rr=},{rad=}')
                uf.unite(i, j)

    cnt = [1] * (len(rs) - 1)
    for v, rad in enumerate(rs[:-1]):
        if uf.root(v): continue
        root_node = uf.find(v)
        cnt[root_node] = (cnt[root_node] + d[rad]) % MOD

    ans = 1
    for v, c in enumerate(cnt):
        if uf.root(v):
            ans = ans * (c + 1) % MOD
    ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod
a_zero = 0
b_zero = 0
AB = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod)
        ans %= mod
        n -= 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        AB.append([a, b])
x = [a / b for a, b in AB]
y = [- b / a for a, b in AB]

j = 0
if a_zero:
    while j + 1 < b_zero:
        ans -= comb(b_zero, j + 2) * pow(2, n - (b_zero - (j+2)) - (j+2), mod)
        ans %= mod
        j += 1
    n -= b_zero
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1
for i in lst:
    j = 0
    while j + 1 < i:
        ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
        ans %= mod
        j += 1
    n -= i
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    from collections import Counter
    from math import gcd
    n, *ab = map(int, open(0).read().split())
    mod = 10 ** 9 + 7
    ans = pow(2, n, mod) - 1
    d = []

    for i, j in zip(*[iter(ab)] * 2):
        g = gcd(i, j)
        x = [i // g, j // g]
        d.append(x)

    vis = []

    tmp = 0
    for (i, j) in d:
        if [i, j] in vis:
            continue
        if [-j, i] in vis:
            continue
        if [j, -i] in vis:
            continue
        x = d.count([i, j])
        y = d.count([-j, i]) + d.count([j, -i])
        z = n - (x + y)
        i = pow(2, x, mod) - 1
        j = pow(2, y, mod) - 1
        k = pow(2, z, mod)
        tmp += i * j * k
        vis.append([i, j])
        vis.append([-j, i])
        vis.append([j, -i])

    ans -= (tmp // 2)
    tmp %= mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys

# import re
import math
import collections
# import decimal
# import bisect
# import itertools
# import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n = ni()

    d = []
    d_to_hi = {}
    hi = {}

    for i in range(n):
        a, b = ns()
        d.append((a, b))
        gcd = math.gcd(abs(a), abs(b))

        gcd_a = a // gcd
        gcd_b = b // gcd
        d_to_hi[(a, b)] = (gcd_a, gcd_b)

        if (gcd_a, gcd_b) in hi.keys():
            hi[(gcd_a, gcd_b)] += 1
        else:
            hi[(gcd_a, gcd_b)] = 1

    badcomb = 0
    for a, b in d:
        gcd_a, gcd_b = d_to_hi[(a, b)]
        if (gcd_b, -gcd_a) in hi.keys():
            badcomb += hi[(gcd_b, -gcd_a)]
        if (-gcd_b, gcd_a) in hi.keys():
            badcomb += hi[(-gcd_b, gcd_a)]

    badcomb //= 2
    badcomb %= MOD

    total = pow(2, n, MOD) - 1
    tmp = (pow(2, n - 2, MOD)) % MOD
    total -= badcomb * tmp % MOD
    total %= MOD
    print(total)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def search(num, tuuro):
    a = []
    b = []
    for i in tuuro:
        if num in i:
            if i[0] != num:
                ans[i[1]-2] = i[0]
                print("1", i, i[0], type(i[0]), type(num))
                b.append(search(i[0]))
            else:
                ans[i[0]-2] = i[1]
                print("2", i, i[1])
                b.append(search(i[1]))
        else:
            a.append(i)

    if 0 not in ans:
        return ans
    else:
        for i in b:
            return search(i, a)


n, m = map(int, input().split())
tuuro = [[int(a) for a in input().split()] for _ in range(m)]
ans = [0 for _ in range(n-1)]
search(1, tuuro)

Submission status: Runtime Error

Solution code:
N = int(input())
bad = 1
X = {}
Y = {}

for _ in range(N):
    a, b = map(int, input().split())
    if (a >= 0 and b >= 0) or (a < 0 and b < 0):
        a = abs(a)
        b = abs(b)

        test = str(a / b)
        testa = str(b / a)
        if test in X:
            X[test] += 1
        else:
            X[test] = 1
        if testa in Y:
            bad = bad * (Y[testa] + 1) / (Y[testa] + 2) * 2
    else:
        a = abs(a)
        b = abs(b)
        test = str(a / b)
        testa = str(b / a)
        if test in Y:
            Y[test] += 1
        else:
            Y[test] = 1
        if testa in X:
            bad = bad * (X[testa] + 1) / (X[testa] + 2) * 2
print(X)
print(Y)
print(int((2 ** N / bad - 1) % 1000000007))

Submission status: Runtime Error

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
 
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return
 
    def __str__(self):
        return  str(self.edges)
 
    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)
 
class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]
 
    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    prev=[0]*n
    q=[(j,i) for i,j in enumerate(d)]
    heapify(q)
    v=[False]*n
    # calc
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev


show_flg=False
show_flg=True
ans=0

n=I()
ans=pow(2,n,mo)-1

dp=[[0]*2 for i in range(n+1)]
dp[0][1]=1
m=defaultdict(int)
L=10**19
for i in range(n):
    a,b=LI()

    g=gcd(a,b)
    x,y=a//g,b//g
    if y<0:
        x*=-1
        y*=-1

    m[x*L+y]+=1
    u,v=-y,x
    if v<0:
        u*=-1
        v*=-1
    kp=x*L+y
    kq=u*L+v
    p=m[x*L+y]
    q=0
    if kq in m:
        q=m[kq]
    dp[i+1][0]=sum(dp[i])
    ng=1
    #ng*=pow(2,p-1,mo)
    ng*=(pow(2,q,mo)-1)
    ng*=pow(2,i-(p-1)-q,mo)
    dp[i+1][1]=sum(dp[i])-ng%mo
    
    #show(a,b,g,(x,y),x*L+y,ng)

#print('DP',dp)
ans=sum(dp[n])-1

print(ans)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    # A = []
    # B = []
    C = []
    for i in range(n):
        a,b = map(int, input().split())
        C.append(a/b)
    import numpy as np
    # A = np.array(A)
    # B = np.array(B)
    C = np.array(C)
    C_p = C[C>=0]
    C_n = C[C<0]
    from collections import Counter as cc
    C_p,C_n = cc(C_p),cc(C_n)
    num = 0
    count= 0
    re = 1
    for c in C_p:
        if -1/c in C_n:
            num = C_n[-1/c] + C_p[c]
            count += num
            re *= (2**C_n[-1/c] + 2**C_p[c] -1)%mod
    ans = pow(2,n-count,mod)*re%mod -1
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

    
    
n = int(input())
a_list = []
b_list = deque()
mod = 10 ** 9 + 7
p = [1] * (n + 1)
for i in range(n):
    p[i + 1] = p[i] * 2 % mod

for _ in range(n):
    a, b = map(int, input().split())
    a_list.append((a * pow(b, mod - 2, mod)) % mod)
    b_list.append((b * pow(a, mod - 2, mod)) % mod)
count = n
out = 0
for aa in a_list:
    num = b_list.count((aa * (-1)) % mod)
    out += p[count - num - 1]
    out = out % mod
    count -= 1
    b_list.pop(0)
print(out)

Submission status: Runtime Error

Solution code:
from decimal import *
getcontext().prec = 30
MOD = 1000000007

def solve(N, ABs):
    groups = {}
    zero_count = 0
    for a, b in ABs:
        if a == 0 and b == 0:
            zero_count += 1
            continue
        if b == 0:
            k = "INF"
        else:
            k = Decimal(a) / Decimal(b)
            k = k.quantize(Decimal("0.00000000000000000000001"))
        groups.setdefault(k, 0)
        groups[k] += 1

    visited = set()
    possibles = []
    for k, v in groups.items():
        if k in visited:
            continue
        p = 0
        p += pow(2, v, MOD)
        if k == "INF":
            m = 0
        elif k == 0:
            m = "INF"
        else:
            m = -(Decimal(1) / Decimal(k))
            m = m.quantize(Decimal("0.00000000000000000000001"))
            # print(m)
        if m in groups.keys() and m not in visited:
            p += pow(2, groups[m], MOD)
            visited.add(m)
            p -= 1
        visited.add(k)
        possibles.append(p % MOD)

    ans = 1
    for p in possibles:
        ans *= p
        ans %= MOD

    if zero_count:
        ans += zero_count
        ans %= MOD
    return (ans - 1) % MOD


def slow_solve(N, ABs):
    import itertools
    ans = 0
    for k in range(1, 2**N):
        b = ("{:0" + str(N) + "b}").format(k)
        taken = []
        for i, c in enumerate(b):
            if c == "1":
                taken.append(ABs[i])

        if len(taken) == 1:
            ans += 1
        elif all(comb[0][0] * comb[1][0] + comb[0][1] * comb[1][1] != 0
                 for comb in itertools.combinations(taken, 2)):
            ans += 1
    return ans % MOD

# print(slow_solve(3,
#       [(1, 2), (-1, 1), (2, -1)]))
#
# print(slow_solve(10,
#       [(3, 2), (3, 2), (-1, 1), (2, -1), (-3, -9), (-8, 12), (7, 7), (8, 1), (8, 2), (8, 4)]))
#
# print(slow_solve(3, [(7, 9), (-9, 7), (-4, -2)]))
# print(solve(3, [(7, 9), (-9, 7), (-4, -2)]))

# print(slow_solve(2,
# [(96, 84), (7, -8)]))
# print(solve(2,
# [(96, 84), (7, -8)]))
# input()



if __name__ == "__main__":
    N = int(input())
    ABs = [tuple(map(int, input().split(" "))) for _ in range(N)]
    print(solve(N, ABs))

Submission status: Runtime Error

Solution code:
from decimal import Decimal, getcontext

n = int(input())
nlist = {}
for i in range(n):
    a,b=map(int,input().split())
    div= Decimal(a)/Decimal(b) if b!=0 else "v"
    try:
        nlist[div]=nlist[div] +1
    except KeyError:
        nlist[div]=1
    
for i in nlist.keys():
    div=i
    if div=='v':
        to=Decimal(1)/div if div!=Decimal(0) else "v"
    else:
        to=Decimal(0)
    try:
        nlist[to]=nlist[to]*nlist[div]
    except KeyError:
        pass

ans=0
for i in nlist.values():
    ans+=i
print((2**n-ans)%1000000007)

Submission status: Runtime Error

Solution code:
n=int(input())
import fractions
def f(x,y):
    if x!=0:
        return fractions.Fraction(y,x)
    else:
        return 'inf'
def g(x):
    if x!=0 and x!='inf':
        return (-1)*fractions.Fraction(1,x)
    elif x==0:
        return 'inf'
    else:
        return 0
A=[1]*n #傾きの個数
B=[1]*n #傾きの対立の個数
C=[0]*n #傾きの値
D=[0]*n #傾きの対立の値
for i in range(n):
    a,b=map(int,input().split())
    t=f(a,b)
    if t in C:
        k=C.index(t)
        A[k]=A[k]*2%1000000007
    elif t in D:
        k=D.index(t)
        B[k]=B[k]*2%1000000007
    else:
        k=A.index(1)
        C[k]=t
        D[k]=g(t)
        A[k]=A[k]*2%1000000007
s=0
j=1
for i in range(n):
    (A[i]+B[i])%1000000007=x
    s=(s+j*(x-2))%1000000007
    j=j*(x-1)%1000000007
print(s)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N = int(sys.stdin.readline().strip())

fact = [1 for i in range(N+1)]
for i in range(1, N):
    fact[i+1] = (fact[i] * (i+1)) % mod

# math.factroialでは速度が足りない
def nCr(n, r, mod=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    if n == 0 or r == 0:
        return 1

    """
    a = math.factorial(n) % mod
    b = math.factorial(r) % mod
    c = math.factorial(n - r) % mod
    """
    a = fact[n]
    b = fact[r]
    c = fact[n-r]

    inv = modinv(b*c, mod)
    ans = a * inv

    return ans % mod

fishes = []
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    gcd = math.gcd(a, b)
    fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)

calculated = set()
ans = 0
# 全組み合わせ
for i in range(1, N+1):
    ans += nCr(N, i)
    ans %= mod
# print("all", ans)

# 除外すべき組み合わせを計算
for ((a, b), count) in counter.items():
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が良いものだけの組み合わせ
    good = 0
    for i in range(1, count+1):
        good += nCr(count, i)
        good %= mod
        
    # 仲が悪いものだけの組み合わせ
    bad = 0
    for i in range(1, bad_count+1):
        bad += nCr(bad_count, i)
        bad %= mod

    others = 0
    others_count = N - count - bad_count 
    for i in range(others_count + 1):
        others += nCr(others_count, i)

    # goodから1匹以上、othersから0匹以上、badから1匹以上の組み合わせを除外
    bad_choices = good * others * bad
    # print(good, others, bad, bad_choices)
    ans -= bad_choices
    # print(ans)
    ans %= mod

print(ans)