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 math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1

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 //= 2
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        b = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a == 0 and b == 0:
        continue
    else:
        p1 = str(a//g)+" "+str(b//g)
        if p1 in d:
            d[p1] += 1
        else:
            d[p1] = 1

for i in d.keys():
    i0, i1 = map(int,i.split())
    if str(i1)+" "+str(-i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i1)+" "+str(-i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(i1)+" "+str(-i0)] = 0
    elif str(-i1)+" "+str(i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(-i1)+" "+str(i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(-i1)+" "+str(i0)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod

if ans == 1:
    print(1)
    exit()
ans = (ans-1)%mod
print(ans)

Submission status: Runtime Error

Solution code:
import math 

MOD = 10**9 + 7
N = int(input())
ABC = []
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        print(0/0)
    if a * b >=0 and a != 0:
        ABC.append([ math.atan2(abs(b),abs(a)), abs(a), abs(b),1])
    else:
        ABC.append([math.atan2(abs(a),abs(b)), abs(b), abs(a), -1])
ABC.sort()
current_arg = ABC[-1][0]
current_x = ABC[-1][1]
current_y = ABC[-1][2]
group = []
daiich = 0
daini = 0
while ABC:
    current = ABC.pop()
    di = {}
    if current[0] == current_arg:
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
    else:
        group += [[daiich, daini]]
        daiich = 0
        daini = 0
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
        if ABC:
            current_arg = current[0]
            current_x = current[1]
            current_y = current[2]
else:
    group += [[daiich, daini]]
    daiich = 0
    daini = 0

ans = 1
for u, v in group:
    ans *= (2**u + 2**v -1)
    ans %= MOD
print(ans-1)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
N = int(input())
iwpos = []
iwneg = []
for i in range(N):
    a, b = map(int,input().split())
    if a*b > 0:
        iwpos.append((a,b))
    else:
        iwneg.append((a,b))

cnt = 0
for ap, bp in iwpos:
    for an, bn in iwneg:
        if ap * an + bn * bp == 0:
            cnt += 1
            break
#print(cnt)
ans = (2**(N-2*cnt)*3**cnt-1)%mod            
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from math import gcd
from collections import Counter
# # def input(): return sys.stdin.readline().rstrip()
# # input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)
MOD = 1000000007

N = int(input())
ab = []
for i in range(N):
    a,b = map(int, input().split())
    gcd_ab = gcd(a,b)
    a //= gcd_ab
    b //= gcd_ab
    if a<0:     # aは常に正にする
        a *= -1
        b *= -1
    ab.append((a,b))
Cnt = Counter(ab)
# print(Cnt)

ans = 1
done = set()
for (a, b), c in Cnt.items():
    # print(a,b,c)
    if (a,b) in done: continue
    if b < 0:
        if (-b, a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(-b,a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((-b,a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
    else:
        if (b, -a) in Cnt.keys():
            ans *= (pow(2,c,MOD)-1) + (pow(2,Cnt[(b,-a)],MOD)-1) + 1
            ans %= MOD
            done.add((a,b))
            done.add((b,-a))
        else:
            ans *= pow(2,c,MOD)
            ans %= MOD
            done.add((a,b))
# print(done)
ans -= 1
ans % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

n = int(input())
MOD = 10**9+7
p_map = {}
n_map = {}
z_map = 0
for _ in range(n):
    ab = list(map(int, input().split()))
    ab_gcd = gcd(ab[0], ab[1])
    a = ab[0]//ab_gcd
    b = ab[1]//ab_gcd
    key = "{}_{}".format(a, b)
    if a*b > 0:
        if key not in p_map:
            p_map[key] = 1
        else:
            p_map[key] += 1
    elif a*b == 0:
        z_map += 1
    else:
        if key not in n_map:
            n_map[key] = 1
        else:
            n_map[key] += 1

ans = 1
for k, v in p_map.items():
    
    a = int(k.split("_")[0])
    b = int(k.split("_")[1])
    n_num = 0
    key_a = "{}_{}".format(-b, a)
    key_b = "{}_{}".format(b, -a)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    if key_b in n_map:
        n_num += n_map.pop(key_b)
    res = 0
    res += pow(2, v, MOD)-1
    if n_num > 0:
        res += pow(2, n_num, MOD)-1
    res += 1
    ans *= res
    ans %= MOD

n_num = sum(n_map.values())
ans *= pow(2, n_num, MOD)
ans %= MOD
ans -= 1

if z_map > 0:
    ans += z_map
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import math
import itertools

n = int(input())

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

    key = (0, 0)
    if a * b < 0:
        key = (abs(b) // gcd, abs(a) // gcd)
    else:
        key = (abs(a) // gcd, abs(b) // gcd)

    if key not in vectors:
        vectors[key] = [i]
    else:
        vectors[key].append(i)

mod = 1000000007
# total = (pow(2, len(vectors)) - 1) % mod

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

total = 1
for vec in vectors.values():

    comb = (combinations_count(len(vec), 2) if len(vec) >= 2 else 0)
    total *= (2+comb) % mod

print(total- 1)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
MAX_A = 10**18+1
DELIM = 1000000007

def kaijo(N):
    if(N==0):
        return 1
    if(N%2==1):
        return (2 * ((kaijo(N//2) ** 2)%DELIM)) % DELIM
    else:
        return ((kaijo(N//2) % DELIM) ** 2) % DELIM

def main():
    N = int(input())
    AB = [[0] * 2 for i in range(N)]
    X = [0] * N
    no_count_comb = 0
    A_Zeros = []
    B_Zeros = []
    X_Dict = dict()
    for i in range(N):
        A, B = map(int, input().split())
        if(A == 0):
            A_Zeros.append(i)
            no_count += len(B_Zeros)
        if(B == 0):
            B_Zeros.append(i)
            no_count += len(A_Zeros)
            X[i] = MAX_A

        else:
            X = A / B
            if(X in X_Dict):
                X_Dict[X] += 1
            else:
                X_Dict[X] = 1

            if(-1 / X in X_Dict):
                no_count_comb += X_Dict[-1/X]
        

    total = kaijo(N) - 1
    no_count = kaijo(N-2)
    print((total - no_count_comb * no_count)%DELIM)

main()

Submission status: Runtime Error

Solution code:
N = int(input())
P = [[int(i) for i in input().split()] for  _ in range(N)]

import numpy as np
from collections import deque

Pmat = np.matrix(P)


badmat = Pmat.T@Pmat
badmat = np.where(badmat ==0)


graph = [deque([]) for _ in range(N + 1)]
for i in range(N):
    graph[i].extend(badmat[1][badmat[0]==i])


arrive_time = [0] * N # 到着時刻
visit = [-1]*(N)

# 深さ優先探索
def dfs(v):
    s = 1
    stack = [v]
    arrive_time[v] = 1
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visit[w] == -1:
                visit[w] = 1
                s+=1
                stack.append(w)
        else:
            stack.pop()
    return s

ans=[]
# 孤立している頂点対策
for i in range(N):
    if visit[i] == -1:
        ans.append(dfs(i))

def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res

kotae = 0
for a in ans:
    kotae+=power_func(2,a,1000000007)
    kotae = kotae % 1000000007
print(kotae-1)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
rad_dic = {}
ans = 0
for i in range(N):
    A,B = map(int,input().split())
    a = A//math.gcd(abs(A), abs(B))
    b = B//math.gcd(abs(A), abs(B))
    if (a,b) not in rad_dic:
        rad_dic[(a,b)]= 1
        c = 0
    else:
        c = rad_dic[(a,b)]
        rad_dic[(a,b)] += 1
    n = 0
    if (-b,a) in rad_dic:
        n += rad_dic[(-b,a)]
    if (b,-a) in rad_dic:
        n += rad_dic[(b,-a)]
    if n == 0:
        ans *= 2
    else:
        ans += ans//2 + (2**n-1)*2**(i-n-c)
    ans %= 1000000007
print((pow(2,N)-1-ans)%1000000007)

Submission status: Runtime Error

Solution code:
n = int(input())
zen=[]
ab=[]
ba=[]
for i in range(n):
    a,b=map(int, input().split())
    zen.append([a,b])
    ab.append(a/b)
    ba.append(b/a)

ba=sorted(ba)
from bisect import bisect_left, bisect_right
from collections import defaultdict
kosudic=defaultdict(int)
for i in range(n):
    a,b=zen[i][0],zen[i][1]
    x=-a/b
    #print(x)
    l=bisect_left(ba, x)
    r=bisect_right(ba, x)
    #print(l,r)
    search=ba[l:r]
    kosu=sum([1 for j in search if abs(j-x)<10**(-10)])
    kosudic[kosu]+=1

ans=1
maxs=max(kosudic.keys())
#print(kosudic)

for i in range(maxs,-1,-1):
    if kosudic[i]!=0 and i!=1:
        ans*=(i**2+1)**kosudic[i]
        kosudic[1]-=i
    if i==1:
        ans*=3**(kosudic[1]//2)
    if i==0:
        ans*=2**kosudic[0]

print(ans-1)

Submission status: Runtime Error

Solution code:
MAX_A = 10**18+1
DELIM = 1000000007

def kaijo(N):
    if(N==0):
        return 1
    if(N%2==1):
        return (2 * ((kaijo(N//2) ** 2)%DELIM)) % DELIM
    else:
        return ((kaijo(N//2) % DELIM) ** 2) % DELIM

def main():
    N = int(input())
    AB = [[0] * 2 for i in range(N)]
    X = [0] * N
    no_count_comb = 0
    A_Zeros = []
    B_Zeros = []
    X_Dict = dict()
    for i in range(N):
        A, B = map(int, input().split())
        if(A == 0):
            A_Zeros.append(i)
            no_count += len(B_Zeros)
        if(B == 0):
            B_Zeros.append(i)
            no_count += len(A_Zeros)
            X[i] = MAX_A

        else:
            X = A / B
            if(X in X_Dict):
                X_Dict[X] += 1
            else:
                X_Dict[X] = 1

            if(-1 / X in X_Dict):
                no_count_comb += X_Dict[-1/X]
        

    total = kaijo(N) - 1
    no_count = kaijo(N-2)
    print((total - no_count_comb * no_count_comb)%DELIM)

main()

Submission status: Runtime Error

Solution code:
N = int(input())
abp = []
abm = []
abz = []
bad_naka = []
for i in range(N):
    q,qq = map(int,input().rstrip().split(" "))
    if q == 0 or qq == 0:
        abz.append(0)
    elif q / qq < 0:
        abm.append(q / qq)
    else:
        abp.append(q / qq)

abm.sort()

abp.sort()

c_p = 0
c_m = 0

bnc = 1
bnc_2 = 1

ans = 0

nokori = N

while c_p != len(abp) -1 or c_m != len(abm) -1:
    if abp[c_p] * abm[c_m] == -1:
        if c_p + 1 <= len(abp) - 1 and abs(abp[c_p + 1]) == abs(abp[c_p]):
            c_p += 1
            bnc += 1
        elif c_m + 1 <= len(abm) -1 and abs(abm[c_m + 1]) == abs(abm[c_m]):
            c_m += 1
            bnc_2 += 1
        else:
            bad_naka.append([bnc,bnc_2])
            if c_m >= len(abm) - 1:
                c_p += 1
            else:
                c_m += 1
            bnc = 1
            bnc_2 = 1

    elif abs(abp[c_p]) * abs(abm[c_m]) < 1 or c_m >= len(abm) - 1:
        c_p += 1
    else:
        c_m += 1

ans += len(abz)
nokori -= len(abz)
for i in range(len(bad_naka)):
    by = (bad_naka[i][1] * (bad_naka[i][1] + 1)) / 2 + (bad_naka[i][0] * (bad_naka[i][0] + 1)) / 2
    nokori -= bad_naka[i][1] + bad_naka[i][0]
    ans *= by + 1
    ans += by
    ans %= 10 ** 10 + 7
for i in range(nokori):
    ans *= 2
    ans += 1
    ans %= 10 ** 10 + 7
    
print(int(ans))

Submission status: Runtime Error

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

n = int(input())
a = dict()
b = dict()
cnt = 1
cnt2 = 1
cnt3, cnt4 = 0, 0

for _ in range(n):
    x, y = map(int, input().split())

    if y == 0:
        cnt3 += 1
    elif x / y in a.keys():
        a[x / y] += 1
    else:
        a[x / y] = 1

    if x == 0:
        cnt4 += 1
    elif -y / x in b.keys():
        b[-y / x] += 1
    else:
        b[-y / x] = 1

for x in a:
    if x in b.keys():
        cnt *= (2 ** a[x] + 2 ** b[x] - 1)
        cnt2 *= (2 ** a[x] + 2 ** b[x] - 1)
    else:
        cnt *= 2 ** a[x]

cnt *= (2 ** cnt3 + 2 ** cnt4 - 1)
print((int(cnt // (cnt2 ** (1/2))) - 1) % 1000000007)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
C=[]
for i in range(N):
  A,B=list(map(int,input().split()))
  C.append(A/B)
count=0
for i in range(len(C)):
  for j in range(i,len(C)):
    if C[i]==1/C[j]:
      count+=1
      
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print((combinations_count(N, 2)-count)%1000000007)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
C=[]
for i in range(N):
  A,B=list(map(int,input().split()))
  C.append(A/B)
count=0
for i in range(len(C)):
  for j in range(i,len(C)):
    if C[i]==1/C[j]:
      count+=1
      
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print((combinations_count(N, 2)-count)%10007)

Submission status: Runtime Error

Solution code:
from collections import defaultdict as dd
MOD = 10**9+7
N=int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
res = 0
left_dic = dd(int)
center_dic = dd(int)
right_dic = dd(int)
for a,b in ab:
    if a==b or -a==b:
        center_dic[a/b] += 1
    elif abs(a)>abs(b):
        left_dic[a/b] += 1
    elif abs(a)<abs(b):
        right_dic[b/a] += 1
comp = []
# center
if center_dic[1.0]>0 and center_dic[-1.0]>0:
    comp.append((center_dic[1.0],center_dic[-1.0]))
# print(left_dic)
# print(right_dic)
# left,right
left = sorted(left_dic.keys(),reverse=True)
right = sorted(right_dic.keys())
idx_left = 0
idx_right = 0
S = len(left)
T = len(right)
# left:+, right:-
while 1:
    if idx_left>=S or idx_right>=T:
        break
    l = left[idx_left]
    r = -right[idx_right]
    if l<0 or r<0:
        break
    if l==r:
        comp.append((left_dic[l], right_dic[-r]))
        idx_left += 1
        idx_right += 1
    elif l>r:
        idx_left += 1
    else:
        idx_right += 1
if idx_right<S and idx_left<T:
    left = [-val for val in left if val < 0]
    # left = left[::-1]
    right = [val for val in right if val > 0]
    S = len(left)
    T = len(right)
    idx_left = 0
    idx_right = 0
    while 1:
        if idx_left >= S or idx_right >= T:
            break
        l = left[idx_left]
        r = right[idx_right]
        if l < 0 or r < 0:
            break
        if l == r:
            comp.append((left_dic[-l], right_dic[r]))
            idx_right += 1
            idx_left += 1
        elif l < r:
            idx_left += 1
        else:
            idx_right += 1
res2 = 0
rest = N
buff = 1
for s,t in comp:
    rest -= s+t
    # tmp = s*t
    tmp = (2**(s+t)-2**s-2**t+1)%MOD
    res2 = (res2 + buff*tmp*pow(2,rest,MOD))%MOD
    buff = (2**(s+t)-tmp)%MOD
res2 += 1
res = (pow(2,N,MOD)-res2)%MOD
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
rad_dic = {}
ans = 0
for i in range(N):
    A,B = map(int,input().split())
    a = A//math.gcd(abs(A), abs(B))
    b = B//math.gcd(abs(A), abs(B))
    if (a,b) not in rad_dic:
        rad_dic[(a,b)]= 1
        c = 0
    else:
        c = rad_dic[(a,b)]
        rad_dic[(a,b)] += 1
    n = 0
    if (-b,a) in rad_dic:
        n += rad_dic[(-b,a)]
    if (b,-a) in rad_dic:
        n += rad_dic[(b,-a)]
    if n == 0:
        ans *= 2
    else:
        ans += ans//2 + (2**n-1)*2**(i-n-c)
    ans %= 1000000007
print((pow(2,N)-1-ans)%1000000007)

Submission status: Runtime Error

Solution code:
decimal.getcontext().prec = 40

PRIME = 1000000007
n = int(input())

fish = {}
taste_0 = 0
flavor_0 = 0

for i in range(n):
  a, b = map(int, input().split())
  if a != 0 and b != 0:
    if a / b in fish:
      fish[a / b] = fish[a / b] + 1
    else:
      fish[a / b] = 1
  elif a == 0 and b != 0:
    taste_0 += 1
  elif a != 0 and b != 0:
    flavor_0 += 1

cnt = 0
if taste_0 != 0 and flavor_0 != 0:
  ans = pow(2, taste_0, PRIME)
  ans += pow(2, flavor_0, PRIME) - 1
  ans %= PRIME
else:
  cnt += taste_0
  cnt += flavor_0
  ans = 1

for f in fish:
  if - 1 / f in fish and fish[f] > 0:
    ans1 = pow(2, fish[f], PRIME)
    ans1 += pow(2, fish[-1 / f], PRIME) - 1
    ans *= ans1
    ans %= PRIME
    fish[f] = 0
    fish[-1 / f] = 0
  elif -1 / f not in fish:
    cnt += fish[f]

ans *= pow(2, cnt, PRIME)
ans %= PRIME

ans += PRIME - 1
ans %= PRIME

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
import itertools

n = int(input())
ab = [input().split() for l in range(n)]
npab=np.array(ab, dtype=int)

#print (n)
#print (npab)

nptable = np.zeros((n,n))
for i in range(0,n):
  for j in range(i+1,n):
    nptable[i,j]=npab[i,0]*npab[j,0]+npab[i,1]*npab[j,1]

#print (nptable)

count=n

for i in range(2,n+1):
  base = list(itertools.combinations(range(0,n),i))
#  print (base)

  for j in base:
    flag=1
    base2=list(itertools.combinations(j,2))
    for k in base2:
      if (nptable[k[0],k[1]] == 0 and flag == 1): flag=0
#      print (j, j[k],j[k+1], nptable[j[k],j[k+1]], flag)
#    if (nptable[j[0],j[ll-1]] == 0 and flag == 1): flag=0
        
    if (flag == 1): count=count+1
    
print (count % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

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

N = int(input())
d = {}
for i in range(N):
    A, B = map(int, input().split())
    g = my_gcd(abs(A), abs(B))
    
    if A*B > 0:
        key = (abs(A)//g, abs(B)//g)
        if key not in d:
            d[key] = [0, 0]
        d[key][0] += 1
    else:
        key = (abs(B)//g, abs(A)//g)
        if key not in d:
            d[key] = [0, 0]
        d[key][1] += 1

MOD = 10 ** 9 + 7
ans = 1
for k, v in d.items():
    temp = (pow(2, v[0], MOD) + pow(2, v[1], MOD) - 1) % MOD
    ans = (ans * temp) % MOD
ans = ans - 1
if ans < 0:
    ans += MOD
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
# -*- coding: utf-8 -*-
N = int(input())
X = np.zeros((N, 2))
for i in range(N):
    X[i,:] = list(map(int, input().split()))
print("{0}".format((((X @ X.T)[np.triu_indices(N, 1)] > 0).sum() + N)% 1000000007) )

Submission status: Runtime Error

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

MOD = 1000000007
from collections import defaultdict
dd = defaultdict(int,{})
for a,b in AB:
  dd[-b/a] += 1
  
ans = 0
N -= 1
for a,b in AB:
  if N - dd[a/b]>=0:
    ans += pow(2,(N - dd[a/b]),MOD)
    ans %= MOD
  dd[-b/a] -= 1
  N -= 1
  
print(ans%MOD)

Submission status: Runtime Error

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

mod = 1000000007
n = int(input())

a_per_b = defaultdict(int)
minus_b_per_a = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    x = Fraction(a, b)
    y = -Fraction(b, a)
    a_per_b[x] += 1
    minus_b_per_a[y] += 1


def inverse(f):
    return Fraction(f.denominator, f.numerator)


ans = 1
calculated = set()
for key, count in a_per_b.items():
    if key in calculated:
        continue

    if key in minus_b_per_a:
        bad_count = minus_b_per_a[key]
        ans *= pow(2, count+bad_count, mod) - (pow(2, count, mod) - 1) * (pow(2, bad_count, mod) - 1) % mod
        ans %= mod
        calculated.add(-inverse(key))
    else:
        ans *= pow(2, count, mod)
        ans %= mod

print(ans - 1)

Submission status: Runtime Error

Solution code:
N=int(input())
C=[]
for i in range(N):
  A,B=list(map(int,input().split()))
  C.append(A/B)
count=0
for i in range(C):
  for j in range(i,C):
    if C[i]==1/C[j]:
      count+=1
      
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print((combinations_count(N, 2)-count)/1000000007)

Submission status: Runtime Error

Solution code:
import math
mod = 1000000007
d = {}
X = []
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        b = 1
    else:
        g = math.gcd(a,b)
        a = a//g
        b = b//g
    c = b
    d = a
    if c < 0:
        c = -c
        d = -d    
        if (a,b) in X:
            d[(a,b)] += 1
        else:
            d[(a,b)] = 1
            d[(c,d)] = 0
            (a,b).append(X)
n = N
a = []
for (a,b) in X:
    c = b
    d = a
    if c < 0:
        c = -c
        d = -d
    x = d[(a,b)]
    y = d[(c,d)]
    if y > 0:
        a.append([x,y])
        n = n - x - y
for x,y in a:
    a.pop(0)
    z = 0
    p = len(a)
    for i in 2**p:
        for j in range(p)
            if bin((i>>p) & 1):
                s = 1
            else:
                s = 0

Submission status: Runtime Error

Solution code:
N = int(input())
a = [0]*N
b = [0]*N
for i in range(N):
    a[i],b[i] = map(int, input().split())
    
from collections import defaultdict
counter1 = defaultdict(int)
counter2 = defaultdict(int)
counter3 = defaultdict(int)


for i in range(N):
    a_b = a[i]/b[i]
    b_a = -b[i]/a[i]
    counter1[a_b] += 1
    counter2[b_a] += 1

counter3 = defaultdict(int)
counter4 = defaultdict(int)

for i in counter1:
    if i > 0:
        j = -1/i
        counter3[i] += counter1[i]
    if i > 0:
        j = -1/i
        counter4[i] += counter1[j]
        

for i in counter1:
    if i<0:
        if counter3[i]==0:
            j = -1/i
            counter4[i] += counter1[j]
ans = 1
for i in counter1:
    x = abs(i)
    y = (counter3[x]+1)*(counter4[x]+1)-1
    ans = ans * y %1000000007
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque


def main():
    N, M = list(map(int, input().split()))
    graphs = [[] for i in range(N)]
    for i in range(M):
        a, b = list(map(int, input().split()))
        graphs[a-1].append(b-1)
        graphs[b-1].append(a-1)

    INF = 100000000

    distance = [INF for i in range(N)]
    visited = [False] * N
    #    distance = [[None]*field_x_length]*field_y_length
    visited[0] = True
    distance[0] = 0

    def bfs():
        queue = deque([0])
        distance[0] = 0

        while queue:
            x = queue.popleft()
            for y in graphs[x]:
                if visited[y]:
                    continue
                else:
                    distance[y] = x
                    visited[y] = True
                    queue.append(y)
        return distance

    d = bfs()
    for i in range(N):
        if not visited[i]:
            print("No")
            exit()
    print("Yes")
    for i in range(1, N):
        print(d[i]+1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
MAX_A = 10**18+1
DELIM = 1000000007

def kaijo(N):
    if(N==0):
        return 1
    if(N%2==1):
        return (2 * ((kaijo(N//2) ** 2)%DELIM)) % DELIM
    else:
        return ((kaijo(N//2) % DELIM) ** 2) % DELIM

def main():
    N = int(input())
    AB = [[0] * 2 for i in range(N)]
    X = [0] * N
    no_count_comb = 0
    A_Zeros = []
    B_Zeros = []
    X_Dict = dict()
    for i in range(N):
        A, B = map(int, input().split())
        if(A == 0):
            A_Zeros.append(i)
            no_count += len(B_Zeros)
        if(B == 0):
            B_Zeros.append(i)
            no_count += len(A_Zeros)
            X[i] = MAX_A

        else:
            X = A / B
            if(X in X_Dict):
                X_Dict[X] += 1
            else:
                X_Dict[X] = 1

            if(1 / X in X_Dict):
                no_count_comb += X_Dict[1/X]
        

    total = kaijo(N) - 1
    no_count = kaijo(N-2)
    print((total - no_count_comb * no_count_comb)%DELIM)

main()

Submission status: Runtime Error

Solution code:
tmp = input().split()
N = int(tmp[0])
S = [0 for i in range(N)]
T = [0 for i in range(N)]

for n in range(N):
    tmp = input().split()
    S[n] = int(tmp[0])
    T[n] = int(tmp[1])


#total 
mod =  1000000007

dp[0] = 0

for i in range(N):
    
    out = 0
    for k in range(i):
        if S[k]*S[i]+T[k]*T[i] == 0:
            ++out
    pd[i+1] = dp[i]*2 - out 
    pd[i+1] = pd[i+1] %mod
print(dp[N])

Submission status: Runtime Error

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

n = int(input())
a = dict()
b = dict()
cnt = 1
cnt2 = 1
cnt3, cnt4 = 0, 0

for _ in range(n):
    x, y = map(int, input().split())

    if y == 0:
        cnt3 += 1
    elif x / y in a.keys():
        a[x / y] += 1
    else:
        a[x / y] = 1

    if x == 0:
        cnt4 += 1
    elif -y / x in b.keys():
        b[-y / x] += 1
    else:
        b[-y / x] = 1

for x in a:
    if x in b.keys():
        cnt *= (2 ** a[x] + 2 ** b[x] - 1)
        cnt2 *= (2 ** a[x] + 2 ** b[x] - 1)
    else:
        cnt *= 2 ** a[x]

print((int(cnt // (cnt2 ** (1/2))) - 1) % 1000000007)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(20000)

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

N = int(input())
d = {}
for i in range(N):
    A, B = map(int, input().split())
    g = my_gcd(abs(A), abs(B))
    
    if A*B > 0:
        key = (abs(A)//g, abs(B)//g)
        if key not in d:
            d[key] = [0, 0]
        d[key][0] += 1
    else:
        key = (abs(B)//g, abs(A)//g)
        if key not in d:
            d[key] = [0, 0]
        d[key][1] += 1

MOD = 10 ** 9 + 7
ans = 1
for k, v in d.items():
    temp = (pow(2, v[0], MOD) + pow(2, v[1], MOD) - 1) % MOD
    ans = (ans * temp) % MOD
ans = ans - 1
if ans < 0:
    ans += MOD
print(ans)