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 sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+1
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        else:
            t=float(A/B)
            d[t]=d.get(t,0)+1
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):

        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        elif k==m:
            ik=0
        elif k==0.0:    
            ik=m
        else:
            ik=-1.0/k

        if ik in ks:
            d1,d2=d[k],d[ik]
            tot*=((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)%mod
            tot%=mod
            d[ik]=-1

        else:
            tot*=pow(2,d[k],mod)
            tot%=mod

    tot-=1
    tot+=d.get(-m,0)%mod
    tot%=mod


        

    print(tot)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
dic={}
for i in range(n):
  a,b=map(int,input().split())
  x=a*1.0/b
  if x in dic.keys():
    dic[x] += 1
  else:
    dic[x] = 1
ans=1
for k,v in dic.items():
  if v==0:
    continue
  if (-1.0/k) not in dic:
    ans *= 2
  else:
    ans *= (2**v+2**(dic[-1.0/k])-1)
    dic[-1.0/k]=0
  
print((ans-1) % 1000000007)

Submission status: Runtime Error

Solution code:
M = 1000000007

from fractions import Fraction
from bisect import bisect_left

N = int(input())

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

#print(fish_list)

fish_table = {}
for f in fish_list:
	if f in fish_table:
		fish_table[f] += 1
	else:
		fish_table[f] = 1

fish_count_list = list(fish_table.items())
fish_count_list.sort()
fish_count_only_list = [f for f, c in fish_count_list]

#print(fish_count_list)

singles = 0
pair_list = []
checked = [False] * N

for i, (f, c) in enumerate(fish_count_list):
	x = -1 / f
	j = bisect_left(fish_count_only_list, x)
	if j != len(fish_count_only_list) and fish_count_only_list[j] == x:
		if checked[j] == False:
			f2, c2 = fish_count_list[j]
			pair_list.append((c, c2))
			checked[i] = True
	else:
		singles += 1

count = pow(2, singles, M)

for c1, c2 in pair_list:
	count = (count * (pow(2, c1, M) + pow(2, c2, M) - 1)) % M

count -= 1

print(count)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict

n = int(readline())
data = list(map(int,read().split()))
mod = 1000000007

it = iter(data)
a_b = defaultdict(lambda :[0,0])
a0 = 0
b0 = 0
nums = []
ans = 0
for a,b in zip(it,it):
    if(a==b==0):
        ans[i] = 1
        continue
    if(a*b==0):
        if(a==0):
            a0 += 1
        if(b==0):
            b0 += 1
    else:
        if(a/b > 0):
            a_b[a/b][0] += 1
        else:
            a_b[-1*b/a][1] += 1

exp2 = [1] * (n+1)
for i in range(n):
    exp2[i+1] = exp2[i] * 2
    exp2[i+1] %= mod


ans += (ans+1) * ( exp2[a0]-1  + exp2[b0]-1)
ans %= mod

for key,val in a_b.items():
    ans += (ans+1) * ( exp2[val[0]]-1  + exp2[val[1]]-1)
    ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())

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

from collections import defaultdict
dic = defaultdict(int)

for a,b in abl:
    dic[b / a] += 1
MOD = 1000000007
ans = 1
used = defaultdict(int)
for d in dic:
    if -(1/d) in dic:
        if used[-(1/d)] == 0:
            ans *= pow(2, dic[d], MOD) + pow(2, dic[-(1/d)], MOD)  - 1
            used[d] = 1
    else:
        ans *= (dic[d] + 1)
    ans %= 1000000007


print(ans - 1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+1
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        else:
            t=float(A/B)
            d[t]=d.get(t,0)+1
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):

        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        elif k==m:
            ik=0
        elif k==0.0:    
            ik=m
        else:
            ik=-1.0/k

        if ik in ks:
            d1,d2=d[k],d[ik]
            tot*=((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)%mod
            tot%=mod
            d[ik]=-1

        else:
            tot*=pow(2,d[k],mod)
            tot%=mod

    tot-=1
    tot+=d.get(-m,0)


        

    print(tot)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.par = [i for i in range(n)]
        self.height = [0] * n
        self.size = [1] * n

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def getsize(self, x):
        return self.size[self.find(x)]

    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.height[x] < self.height[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = self.par[x]
            self.size[x] += self.size[y]
            if self.height[x] == self.height[x]:
                self.height[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

gcd = lambda a, b: a if b == 0 else gcd(b, a%b)

mod = 10**9+7
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = defaultdict(int)
ab = [None]*N
for i, (A, B) in enumerate(AB):
    g = gcd(A, B)
    A //= g
    B //= g
    if cnt[(-A, -B)] > 0:
        a, b = -A, -B
    elif cnt[(-B, A)] > 0:
        a, b = -B, A
    elif cnt[(B, -A)] > 0:
        a, b = B, -A
    else:
        a, b = A, B
    cnt[(a, b)] += 1
    ab[i] = (a, b)
ans = 0
f = 1
for v in cnt.values():
    f *= pow(2, v, mod)
    f %= mod
for v in cnt.values():
    f *= pow(pow(2, v, mod), mod-2, mod)
    ans += v * f
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter
N = int(input())
A_B = []
mod = 1000000007
for _ in range(N):
    A, B = map(int, input().split())
    if A < 0:
        A = -A
        B = -B
    C = math.gcd(abs(A), abs(B))
    A_B.append((A//C, B//C))
A_B_C = Counter(A_B)


hate_couple = 0
ans = 1
Done = set([])
for key, value in A_B_C.items():
    if key in Done:
        continue
    keya, keyb = key
    a = 0
    if keyb < 0:
        keya = -keya
        keyb = -keyb
    if (keyb, -keya) not in A_B_C:
        a = pow(2, value, mod)
    else:
        a = (pow(2, value, mod) - 1) + (pow(2, A_B_C[(keyb, -keya)], mod) - 1) + 1
        Done.add((keyb, -keya))
    ans *= a
    ans %= mod
    Done.add(key)

print((ans - 1)%mod)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7
MAX = 2 * 10**5 + 1
sqr = [1 for _ in range(MAX)]
for i in range(1, MAX):
    sqr[i] = sqr[i-1] * 2
    sqr[i] %= MOD

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

n = int(input())
d = defaultdict(lambda: 0)
ans = 1
flt = FLT()

for i in range(n):
    a, b = map(int, input().split())
    tmp1 = format(- b / a, '.10f').rstrip('0')
    cnt = d[tmp1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    tmp2 = format(a / b, '.10f').rstrip('0')
    d[tmp2] += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 998244353
from fractions import *
def inverse(f):
    return Fraction(f.denominator,f.numerator)


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    iwashis = []
    for i in range(n):
        iwashis.append(getList())

    fr = defaultdict(int)
    for iw in iwashis:
        if iw[0] != 0:
            fr[Fraction(iw[1], iw[0])] += 1
        else:
            fr["INF"] += 1

    used = defaultdict(int)
    ans = 1
    for k, v in fr.items():
        if k == "INF":
            pass
        elif k not in used:
            if - inverse(k) in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[- inverse(k)], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[- inverse(k)] += 1
        elif k == 0:
            if "INF" in fr:
                ans *= pow(2, v, MOD) + pow(2, fr["INF"], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
        # print(k, v, ans, -inverse(k))
    # print(fr)
    print((ans-1) % MOD)
    # bun.sort()
    # ans = 0
    # for iw in iwashis:
    #     cur = iw[0]/ iw[1]
    #     ans += bisect_right(bun, -cur) - bisect_left(bun, -cur)
    #     print(iw, cur, ans)
    #
    # print(ans/2)
    # print(bun)
    #
    # tmp = 0
    # for i in range(n-1):
    #     for j in range(1+1, n):
    #         iw1, iw2 = iwashis[i], iwashis[j]
    #         if iw1[0] * iw2[0] + iw1[1] + iw2[1] == 0:
    #             print(iw, iw2)
    #             tmp += 1
    #
    # print(tmp)
def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+1
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        else:
            t=float(A/B)
            d[t]=d.get(t,0)+1
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):

        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        elif k==m:
            ik=0
        elif k==0.0:    
            ik=m
        else:
            ik=-1.0/k

        if ik in ks:
            d1,d2=d[k],d[ik]
            tot*=(pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1
            d[ik]=-1
        else:
            tot*=pow(2,d[k],mod)
    tot-=1
    tot+=pow(2,d.get(-m,0),mod)-1

        

    print(tot)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
MOD = 10**9 + 7

n = int(input())
fish = dict() 
for _ in range(n):
    a, b = map(int, input().split())
    a_abs = abs(a); b_abs = abs(b)
    g = math.gcd(a_abs, b_abs)
    if (a > 0 and b > 0) or (a < 0 and b < 0): 
        key = (a_abs // g, b_abs // g)
    else:
        key = (a_abs // g, -b_abs // g)
    if key not in fish:
        fish[key] = 1
    else:
        fish[key] += 1

ans = 1
for a, b in fish:
    if fish[(a, b)] == 0:
        continue
    if b < 0:
        inv_key = (-b, a)
    else:
        inv_key = (b, -a)
    if inv_key in fish:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        val2 = ans * (pow(2, fish[inv_key], MOD) - 1)
        fish[inv_key] = 0
        ans = val1 + val2 + ans
    else:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        ans = val1 + ans
    ans %= MOD
print((ans - 1) % MOD)

Submission status: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        g=gcd(abs(a),abs(b))
        a=a//g
        b=b//g
        if (a,b) in d:
            d[(a,b)]+=1
             
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k,d[k]))


    for i in range(len(L)):
        k=L[i][0]
        v=d[k]
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if (-b,a) in d:
            v2=d[(-b,a)]
            if v2!=0:
                temp+=pow(2,v2)-1
                d[(-b,a)]=0
        if (b,-a) in d:
            v2=d[(b,-a)]
            if v2!=0:
                temp+=pow(2,v2)-1
                d[(b,-a)]=0
        ans=(ans*temp)%mod
        
        
        

        
    print(ans-1)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+1
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        else:
            t=float(A/B)
            d[t]=d.get(t,0)+1
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):

        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        elif k==m:
            ik=0
        elif k==0.0:    
            ik=m
        else:
            ik=-1.0/k

        if ik in ks:
            d1,d2=d[k],d[ik]
            tot*=(pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1
            d[ik]=-1
        else:
            tot*=pow(2,d[k],mod)
        tot-=1
        tot+=pow(2,d.get(-m,0),mod)-1

        

    print(tot)




if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys,math,bisect
input = sys.stdin.readline

mod = 1000000007
eps = 0.001

n = int(input())

ab = []
ang = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0:
        ang.append((90.0,i))
    else:
        ang.append((math.degrees(math.atan(b/a)),i))
ang.sort()

res = 1
used = [False]*n


rest = n

for i in range(n):
    e,idx = ang[i]
    if used[idx]:
        continue
    used[idx] = True
    
    cnt = 1
    k = idx + 1
    while k < n:
        if abs(e-ang[k][0]) <= eps:
            p = ang[k][1]
            if ab[p][0]*ab[idx][1] == ab[p][1]*ab[idx][0]:
                cnt += 1
                used[ang[k][1]] = True
            k += 1
        else:
            break
    
    tmp = pow(2,cnt,mod)

    cnt2 = 0

    ok = n-1
    ng = idx
    while ok-ng > 1:
        mid = (ok+ng)//2
        if ang[mid][0] >= e+90-eps:
            ok = mid
        else:
            ng = mid
    k = ok
    while k < n:
        if abs(e+90-ang[k][0]) <= eps:
            p = ang[k][1]
            if ab[p][0]*ab[idx][0] + ab[p][1]*ab[idx][1] == 0:
                cnt2 += 1
                used[ang[k][1]] = True
            k += 1
        else:
            break

    if cnt2 != 0:
        res = res*(tmp + pow(2,cnt2,mod)-1)%mod
        rest -= cnt+cnt2

res = res*pow(2,rest,mod)%mod - 1
print(res)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from functools import cmp_to_key
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
n00 = 0
n0x = 0
nx0 = 0
nxy = 0
ls = []
for i in range(n):
  if a[i][0] == a[i][1] == 0:
    n00 += 1
  elif a[i][0] == 0:
    n0x += 1
  elif a[i][1] == 0:
    nx0 += 1
  else:
    nxy += 1
    if a[i][0] < 0 and a[i][1] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    elif a[i][0] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    ls.append(a[i])
def sorting(x,y):
  if x[0]*y[1]-x[1]*y[0] == 0:
    return 0
  if x[0]*y[1]-x[1]*y[0] > 0:
    return 1
  else:
    return -1
ls.sort(key = cmp_to_key(sorting))
tls = []
t = 1
for i in range(1,n):
  if sorting(ls[i],ls[i-1]) == 0:
    t += 1
  else:
    tls.append([t,*ls[i-1]])
    t = 1
tls.append([t,*ls[n-1]])
for i in range(len(tls)):
  if tls[i][2] < 0:
    tls = tls[:i]+tls[len(tls)-1:i-1:-1]
    break

l = 0
r = len(tls)-1
banned = []
while l < r:
  la,lb = tls[l][1:]
  ra,rb = tls[r][1:]
  if la*ra + lb*rb == 0:
    banned.append((tls[l][0],tls[r][0]))
    l += 1
    r -= 1
  elif la*ra + lb*rb > 0:
    r -= 1
  else:
    l += 1
sm = sum([banned[i][0]+banned[i][1] for i in range(len(banned))])
def p2(x):
  return pow(2,x,mod)
ans = p2(n-sm)
for i,j in banned:
  ans = (ans*(p2(i)+p2(j)-1))%mod
k = p2(n0x)+p2(nx0)-1
ans *= k
ans += n00-1
print(ans%mod)

Submission status: Runtime Error

Solution code:
import fractions
from collections import Counter
N = int(input())
A_B = []
mod = 1000000007
for _ in range(N):
    A, B = map(int, input().split())
    if A < 0:
        A = -A
        B = -B
    C = fractions.gcd(abs(A), abs(B))
    A_B.append((A//C, B//C))
A_B_C = Counter(A_B)


hate_couple = 0
ans = 1
Done = set([])
for key, value in A_B_C.items():
    if key in Done:
        continue
    keya, keyb = key
    a = 0
    if keyb < 0:
        keya = -keya
        keyb = -keyb
    if (keyb, -keya) not in A_B_C:
        a = pow(2, value, mod)
    else:
        a = (pow(2, value, mod) - 1) + (pow(2, A_B_C[(keyb, -keya)], mod) - 1) + 1
        Done.add((keyb, -keya))
    ans *= a
    Done.add(key)

print(ans - 1)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import Counter
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

mod = 10**9 + 7


def modpow(a, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = ret * a % mod
        a = a * a % mod
        n >>= 1
    return ret


col = []
row = []
for a, b in A:
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g

    if a < 0:
        a *= -1
        b *= -1

    if a >= 0 and b > 0:
        col.append((a, b))
    elif a > 0 and b <= 0:
        row.append((-b, a))


C = Counter(col)
D = Counter(row)
S = set(col) | set(row)

ans = 1
for s in S:
    if s in C:
        if s in D:
            mul = modpow(2, C[s], mod) + modpow(2, D[s], mod) - 1
        else:
            mul = modpow(2, C[s], mod)
    elif s in D:
        mul = modpow(2, D[s], mod)

    ans *= mul
    ans %= mod

ans -= 1
ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7
MAX = 2 * 10**5 + 1
sqr = [1 for _ in range(MAX)]
for i in range(1, MAX):
    sqr[i] = sqr[i-1] * 2
    sqr[i] %= MOD

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

n = int(input())
d = defaultdict(lambda: 0)
ans = 1
flt = FLT()

for i in range(n):
    a, b = map(int, input().split())
    tmp1 = - b / a
    cnt = d[tmp1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    tmp2 = a / b
    d[tmp2] += 1
print(ans-1)

Submission status: Runtime Error

Solution code:
n=int(input())
mod = 1000000007
gp = []
gm = []
ga0  =0
gb0 = 0
ans = 1
cnt = 0
for _ in range(n):
    a,b= map(int,input().split())
    if a == 0 and b == 0:
        cnt += 1
    elif  a == 0:
        ga0 += 1
    elif b == 0:
        gb0 += 1
    elif b/a > 0:
        gp.append(b/a)
    elif b/a<0:
        gm.append(b/a)
    else:
        print('what')

gp.sort()
gm.sort()

lp,lm=0,0
cntall = 0
while lp < len(gp) and lm < len(gm):
    cal = gp[lp]*gm[lm]
    if cal == -1:
        cntp,cntm = 1,1
        while lp +1 < len(gp) and  gp[lp] == gp[lp+1]:
            cntp += 1
            lp+=1
        while lm +1 < len(gp) and  gm[lm] == gm[lm+1]:
            cntm += 1
            lm+=1
        ans *= (pow(2,cntp,mod)+pow(2,cntm,mod))%mod-1
        ans %= mod
        lp+=1
        lm+=1
        cntall += cntp+cntm
    elif cal > -1:
        lp += 1
    else:
        lm += 1

ans *= (pow(2,ga0,mod)+pow(2,gb0,mod))%mod-1
ans %= mod
n -= ga0+gb0+cntall+cnt
ans *= pow(2,n,mod)
ans %= mod
ans += cnt
print(ans-1)

Submission status: Runtime Error

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

N = Int()
AB = []
mod = 1000000007
ans = 1
C = 0

from collections import defaultdict
XX = defaultdict(list)
YY = defaultdict(list)

for i in range(N):
    A,B = Ints()
    if A!=0 or B!=0:
        AB.append([A,B])
        C += 1
        XX[A/B].append(i)
        YY[-B/A].append(i)

D = {}

for key in XX:
    if not key in D:
        l = len(XX[key])
        m = len(YY[key])
        ans *= (pow(2,l,mod)+pow(2,m,mod)-1)
        ans %= mod
        D[key] = 1
        D[-1/key] = 1
    
ans -= 1
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
MOD = 1000000007

n = int(input())

# la = []
# lb = []
# for _ in range(n):
#     a, b = map(int, input().split())
#     la.append(a)
#     lb.append(b)


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


def normalize(a, b):
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g

    if a < 0:
        a *= -1
        b *= -1

    if a != 0 and b == 0:
        a, b = 1, 0
    if a == 0 and b != 0:
        a, b = 0, 1

    return a, b


dv = {}
for _ in range(n):
    a, b = map(int, input().split())
    a, b = normalize(a, b)
    dv[(a, b)] = dv.get((a, b), 0) + 1


counted = {k: False for k in dv.keys()}
nc = 1
for k, v in dv.items():
    if not counted[k]:
        a0, b0 = k
        a1, b1 = normalize(b0, -a0)
        w = dv.get((a1, b1), 0)

        nc *= 1 + (2 ** v - 1) + (2 ** w - 1)
        nc %= MOD

        counted[(a0, b0)] = True
        counted[(a1, b1)] = True

nc -= 1
print(nc)

Submission status: Runtime Error

Solution code:
MOD = 1000000007

def solve(N, ABs):
    groups = {}
    for a, b in ABs:
        k = a / b
        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)
        m = - (1.0 / k)
        if m in groups.keys():
            p += pow(2, groups[m], MOD)
            visited.add(m)
            p -= 1
        possibles.append(p % MOD)

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


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