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, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 1 ;count = 0 ;pro = 1
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

n = int(input())
def make_key0(a,b):
  if (a < 0 and b > 0) or (a > 0 and b < 0):hugou = 1
  else: hugou = -1
  a = abs(a)
  b = abs(b)
  G = gcd(a,b)
  return (hugou*(abs(a)//G),abs(b)//G)

def make_key1(a,b):
  if (a < 0 and b > 0) or (a > 0 and b < 0):hugou = -1
  else: hugou = 1
  a = abs(a)
  b = abs(b)
  G = gcd(a,b)
  return (hugou*(abs(b)//G),abs(a)//G)

C0 = collections.Counter()
C1 = collections.Counter()

for i in range(n):
  a,b = map(int,input().split())
  a0,b0 = make_key0(a,b)
  a1,b1 = make_key1(a,b)
  C0[(a0,b0)] += 1
  # C1[(a1,b1)] += 1
  # print(a0,b0,a1,b1)

S = set()
for key,val in C0.items():
  a0,b0 = key
  S.add((a0,b0))
  a1,b1 = make_key0(b0,a0)
  if (a1,b1) in S:continue
  # print((a0,b0))
  # print((a1,b1))
  # print((pow(2,val,mod) , pow(2,C0[(a1,b1)],mod)))
  # print((-1 if C0[(a1,b1)] else 0),C0[(a1,b1)])
  ans *= pow(2,val,mod) + pow(2,C0[(a1,b1)],mod) -1
  ans %= mod
print((ans-1)%mod)

# for key,val in C0.items():
#   print(key,val)

# for key,val in C1.items():
#   print(key,val)

Submission status: Runtime Error

Solution code:
import sys
n=int(input())
m=[]
groups=[]
INF=10**27
a0only=0
b0only=0
both0=0
negativecounter=0
for i in range(n):
  a,b=map(int,sys.stdin.readline().split())
  if b==0:
    if a==0:
      both0+=1
    else:
      b0only+=1
  elif a==0:
    a0only+=1
  else:
    m.append([a,b,a/b,-b/a])
  if a*b<0:
    negativecounter+=1
m1=sorted(m, key=lambda student: student[2])
m2=sorted(m, key=lambda student: student[3])
backcounter=0
done=set()
for i in range(len(m)):
  a=m1[i][0]
  b=m1[i][1]
  if len(groups)>0:
    if groups[-1][0]*b==a*groups[-1][1]:
      groups[-1][2]+=1
    else:
      if i in done:
        groups.append([a,b,1,0,0])
      else:
       	groups.append([a,b,1,0,-1])
  else:
    if i in done:
      groups.append([a,b,1,0,0])
    else:
      groups.append([a,b,1,0,-1])
  while backcounter<n and a/b>=-m2[backcounter][1]/m2[backcounter][0]:
    if m2[backcounter][0]*m1[i][0]+m2[backcounter][1]*m1[i][1]==0:
      groups[-1][3]+=1
      groups[-1][4]=0
    backcounter+=1
ans=1
donenumbers=[0]*len(groups)
for i in range(len(groups)):
  a=groups[i][0]
  b=groups[i][1]
  c=groups[i][2]
  d=groups[i][3]
  if groups[i][4]==0 and a*b<0:
    continue
  ans=(ans*((2**c+2**d)-1))%(10**9+7)
ans=(ans*(((2**a0only+2**b0only)-1+both0))%(10**9+7))
print(ans-1)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
import math
n = int(input())
vector_cnt_dict = dict()

for i in range(n):
    tmp1,tmp2 = map(int,input().split())
    if tmp2 != 0:
        a = Fraction(tmp1,tmp2)
        if a in vector_cnt_dict.keys():
            vector_cnt_dict[a] += 1
        else:
            vector_cnt_dict[a] = 1
    else:
        if (1,0) in vector_cnt_dict.keys():
            vector_cnt_dict[(1,0)] += 1
        else:
            vector_cnt_dict[(1, 0)] = 1

cnt = 1
neutral = 0
#dictのすべてのキーに対して、分母と分子を入れ替えて-1をかけたキーがあればその数分引いて、全数を足し合わせる

for k,v in vector_cnt_dict.items():
    if k != (1,0) and  k != Fraction(0,1):
        if Fraction(k.denominator*(-1),k.numerator) in vector_cnt_dict.keys():
            cnt *= (2**v) + (2**vector_cnt_dict[Fraction(k.denominator*(-1),k.numerator)] ) -1
        else:
            neutral += v
    else:
        neutral += v
cnt = math.sqrt(cnt)

print(int(((2**neutral * cnt)-1) % 1000000007))

Submission status: Runtime Error

Solution code:
from fractions import Fraction
import math
n = int(input())
vector_cnt_dict = dict()

for i in range(n):
    tmp1,tmp2 = map(int,input().split())
    if tmp2 != 0:
        a = Fraction(tmp1,tmp2)
        if a in vector_cnt_dict.keys():
            vector_cnt_dict[a] += 1
        else:
            vector_cnt_dict[a] = 1
    else:
        if (1,0) in vector_cnt_dict.keys():
            vector_cnt_dict[(1,0)] += 1
        else:
            vector_cnt_dict[(1, 0)] = 1

cnt = 1
neutral = 0
#dictのすべてのキーに対して、分母と分子を入れ替えて-1をかけたキーがあればその数分引いて、全数を足し合わせる

for k,v in vector_cnt_dict.items():
    if k != (1,0) and  k != Fraction(0,1):
        if Fraction(k.denominator*(-1),k.numerator) in vector_cnt_dict.keys():
            print(2 **v , 2**vector_cnt_dict[Fraction(k.denominator*(-1),k.numerator)])
            cnt *= (2**v) + (2**vector_cnt_dict[Fraction(k.denominator*(-1),k.numerator)] ) -1
        else:
            neutral += v
    else:
        neutral += v
cnt = math.sqrt(cnt)

print(int(((2**neutral * cnt)-1) % 1000000007))

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def f(v, k, L, K, A, S):
    if k == 0:
        t = 10 ** 20
    elif k == 10 ** 20:
        t = 0
    else:
        t = -1 / k

    if t in K:
        S.add(t)
        return len(K[t])

    if t in (0, 10 ** 20):
        return 0

    res = 0
    p = v[0]
    i = bisect.bisect_right(L, t)
    if i != len(L):
        q = K[L[i]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            res += K[L[i]]
            S.add(L[i])

    if i + 1 < len(L):
        q = K[L[i + 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            res += K[L[i + 1]]
            S.add(L[i + 1])
    
    if i > 0:
        q = K[L[i - 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            res += K[L[i - 1]]
            S.add(L[i - 1])

    return res


def main():
    N = int(input())
    A = read_lists(N)    

    K = {}
    zero = 0
    for i, a in enumerate(A):
        if a == [0, 0]:
            zero += 1
        if a[0] == 0:
            r = 10 ** 20
        else:
            r = a[1] / a[0]
        K.setdefault(r, []).append(i)

    L = sorted(list(K.keys()))    

    S = set()
    res = 1
    for k, v in K.items():
        if k in S:
            continue
        S.add(k)

        t = f(v, k, L, K, A, S)
        if t > 0:
            res *= (pow(2, len(v), mod) + pow(2, t, mod) - 1)
            res %= mod
        else:
            res *= 2
            res %= mod

    print((res + zero - 1) % mod)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import Counter as cc
    from fractions import gcd
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = cc(),cc()
    count= 0
    ans = 1
    for i in range(n):
        a,b = map(int, input().split())
        if a == 0 and b== 0:
            count += 1
        else:
            gcd_ab = gcd(a,b)
            a //= gcd_ab
            b //= gcd_ab
            if b == 0:
                count_zero_b += 1
            elif a == 0: 
                count_zero_a += 1
            else:
                if a/b>0:
                    C_p[a,b] += 1
                else:
                    C_n[a,b] += 1
    count_zero = count
    ans *= (2**count_zero_a + 2**count_zero_b -1)%mod
    count += count_zero_a + count_zero_b    
    for a,b in C_p:
        if (-b,a) in C_n:
            count += C_n[-b,a] + C_p[a,b]
            ans *= (2**C_n[-b,a] + 2**C_p[a,b] -1)%mod
    ans *= pow(2,n-count,mod)%mod
    ans += count -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    MOD = 1000000007
    N = int(input())
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    for i in range(N):
        a, b = map(int, input().split())
        _gcd = gcd(a, b)
        a = a // _gcd
        b = b // _gcd
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    groups = []
    for c, nc in C.items():
        a, b = c
        # 仲の悪いイワシの個数
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_b = -bad_b
            bad_a = -bad_a
        nBad = C.get((bad_a, bad_b), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        if nBad == 0:
            groups.append(2 ** nc)
            continue
        # 中の悪いグループがすでに調査済みなら何もしない
        elif flag[(bad_a, bad_b)]:
            continue

        # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
        # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
        # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
        # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
        groups.append((2 ** nc) + (2 ** nBad) - 1)
        flag[(a, b)] = True

    # 各グループの選択肢を掛け合わせ、-1する
    # (全て選択しないパターンを除外する)
    ans = 1
    for g in groups:
        ans *= g
    ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
 if n == 0:
  return 1
 K = 1
 while n > 1:
  if n % 2 != 0:
   K = K * x%mod
   x = x ** 2%mod
   n = (n - 1) // 2
  else:
   x = x ** 2%mod
   n = n // 2%mod
  return K * x # 指数を割り続け n が 1 に至ったら終了
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*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
 if n == 0:
  return 1
 K = 1
 while n > 1:
  if n % 2 != 0:
   K = K * x%mod
   x = x ** 2%mod
   n = (n - 1) // 2
  else:
   x = x ** 2%mod
   n = n // 2%mod
  return K * x # 指数を割り続け n が 1 に至ったら終了
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 k>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Runtime Error

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

N = int(input())
A = [0]*N
B = [0]*N
C = [[0]*2 for _ in range(N)]

for i in range(N):
    A[i],B[i] = map(int,(input().split()))
    if A[i] == 0 and B[i] == 0:
        C[i] = (0,0)
        zero = 1
    elif B[i] == 0:
        C[i] = (A[i],B[i])
    elif B[i] > 0:
        g = math.gcd(A[i],B[i])
        C[i] = (A[i]//g,B[i]//g)
    else:
        g = math.gcd(A[i],B[i])
        C[i] = (-A[i]//g,-B[i]//g)

d = defaultdict(int)

for i in range(N):
    if C[i] != (0,0):
        d[C[i]] += 1

ans = 1
for k in d.keys():
    if k[0] >= 0:
        if (-k[1],k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(-k[1],k[0])],MOD) - 1
            d[k],d[(-k[1],k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)
    else:
        if (k[1],-k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(k[1],-k[0])],MOD) -1
            d[k],d[(k[1],-k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)

print((zero)%MOD)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        
print(ans + zero - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from fractions import Fraction
def powmod(x, n,mod):
  if n == 0:
   return 1
  K = 1
  while n > 1:
   if n % 2 != 0:
    K = K * x%mod
    x = x ** 2%mod
    n = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod

  return K * x # 指数を割り続け n が 1 に至ったら終了
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 range(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 k>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[-1/Fraction(A,B)][1]+=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k][0],mod)+powmod(2,dic[k][1],mod) -1)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 1000000007
n = ni()
from collections import defaultdict
ab = defaultdict(int)
ba = defaultdict(int)

for i in range(n):
    a,b = na()
    if b == 0:
        ab[1000000000000] += 1
        ba[1000000000000] += 1
        continue
    ab[a/b] += 1
    ba[a/b] += 1

x = 1
c = 0

d = defaultdict(int)

for j,k in ab.items():
    if d[j] > 0:
        continue
    p = -1/j if j != 1000000000000 else 0
    if ba[p] > 0:
        m = ba[p]
        x *= pow(2, k, mod) + pow(2, m, mod) - 1
        x %= mod
        c += k+m
        d[p] += 1

ans = x * pow(2, n-c,mod)-1
print(ans%mod)

Submission status: Runtime Error

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 range(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 k>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: Runtime Error

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

mod = 1000000007
n = ni()
from collections import defaultdict
ab = defaultdict(int)
ba = defaultdict(int)

for i in range(n):
    a,b = na()
    if b == 0:
        ab[-1] += 1000000000000
        ba[-1] += 1000000000000
        continue
    ab[a/b] += 1
    ba[a/b] += 1

x = 1
c = 0

d = defaultdict(int)

for j,k in ab.items():
    if d[j] > 0:
        continue
    p = -1/j if j != 1000000000000 else 0
    if ba[p] > 0:
        m = ba[p]
        x *= pow(2, k, mod) + pow(2, m, mod) - 1
        x %= mod
        c += k+m
        d[p] += 1


ans = x * pow(2, n-c,mod)-1
print(ans%mod)

Submission status: Runtime Error

Solution code:
from math import gcd

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

t = []
d = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
print(result + d[0][0] - 1)

Submission status: Runtime Error

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


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def profile(fish):
    x, y = fish
    GCD = gcd(abs(x), abs(y))

    return (abs(x // GCD), abs(y // GCD), int((x >= 0) ^ (y >= 0)))


N = int(input())
F = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]
modFacts, invs = prepare(N)
B = [tuple(profile(f)) for f in F]

C0 = Counter()
C1 = Counter()
zero = 0
for f in F:
    if f == (0, 0):
        zero += 1
    else:
        x, y, flag = profile(f)
        if x == 0:
            C0[(0, 1, 0)] += 1
            C1[(0, 1, 0)] += 1
        elif y == 0:
            C0[(0, 1, 0)] += 1
            C1[(1, 0, 1)] += 1
        else:
            C1[(x, y, flag)] += 1
            if flag:
                x, y = y, x
                flag = 0
            C0[(x, y, flag)] += 1

ans = 1
for x, y, flag in C0.keys():
    b = C1[(y, x, flag ^ 1)]
    a = C0[(x, y, flag)] - b
    cnt = (pow(2, a, MOD) - 1) + (pow(2, b, MOD) - 1) + 1
    ans *= cnt
    ans %= MOD
ans -= 1
print(ans % MOD)

Submission status: Runtime Error

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


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def profile(fish):
    x, y = fish
    GCD = gcd(abs(x), abs(y))

    return (abs(x // GCD), abs(y // GCD), int((x >= 0) ^ (y >= 0)))


N = int(input())
F = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]
modFacts, invs = prepare(N)
B = [tuple(profile(f)) for f in F]

C0 = Counter()
C1 = Counter()
zero = 0
for f in F:
    x, y, flag = profile(f)
    if (x, y) == 0:
        zero += 1
    elif x == 0:
        C0[(0, 1, 0)] += 1
        C1[(0, 1, 0)] += 1
    elif y == 0:
        C0[(0, 1, 0)] += 1
        C1[(1, 0, 1)] += 1
    else:
        C1[(x, y, flag)] += 1
        if flag:
            x, y = y, x
            flag = 0
        C0[(x, y, flag)] += 1

ans = 1
for x, y, flag in C0.keys():
    b = C1[(y, x, flag ^ 1)]
    a = C0[(x, y, flag)] - b
    cnt = (pow(2, a, MOD) - 1) + (pow(2, b, MOD) - 1) + 1
    ans *= cnt
    ans %= MOD
ans -= 1
print(ans % MOD)

Submission status: Runtime Error

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    g=ggcd(abs(fish[i][0]),abs(fish[i][1]))
    a=fish[i][0]//g
    b=fish[i][1]//g
    if (b==0)and(a>0):
        a=1
    elif b<0:
        a=-a
        b=-b
    fishcomp.append([a,b])
    if (a!=0)and(b!=0):
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
    else:
        both0=both0+1
#print(d)
fishcomp=list(map(list,set(map(tuple,fishcomp))))
#print(fishcomp)
length=N-both0
sets=[]
for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    #print(a,b,val1)
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]
            sets.append([val1,val2])
            length=length-(val2+val1)
#print(sets,length)
pro=1
for i in sets:
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p
#print(pro)
print((pow(2,length,p)*pro-1+both0)%p)

Submission status: Runtime Error

Solution code:
import collections
import math

n = int(input())
m = 0
mod = 10 ** 6 + 7
c = []
d = []
frac = {}
tmp = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        tmp += 1
        m += 1
        continue
    try:
        if a == 0:
            frac['0'] += 1
        elif b == 0:
            frac['inf'] += 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = 1 if a * b > 0 else -1
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] += 1
    except KeyError:
        if a == 0:
            frac['0'] = 1
        elif b == 0:
            frac['inf'] = 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = a * b // abs(a * b)
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] = 1

n -= tmp

def inverse(key):
    if key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key == '0': continue
    if key[0] == '-': continue
    try:
        if key == float('inf'):
            d.append(frac['inf'])
        else:
            d.append(frac[inverse(key)])
        c.append(value)
    except KeyError:
        continue

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1)
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans = (ans * (m + 1) - 1) % mod

print(ans)

Submission status: Runtime Error

Solution code:
import collections
import math

n = int(input())
m = 0
mod = 10 ** 6 + 7
c = []
d = []
frac = {}
tmp = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        tmp += 1
        m += 1
        continue
    try:
        if a == 0:
            frac['0'] += 1
        elif b == 0:
            frac['inf'] += 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = a * b // abs(a * b)
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] += 1
    except KeyError:
        if a == 0:
            frac['0'] = 1
        elif b == 0:
            frac['inf'] = 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = a * b // abs(a * b)
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] = 1

n -= tmp

def inverse(key):
    if key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key == '0': continue
    if key != 'inf' and key[0] == '-': continue
    try:
        if key == float('inf'):
            d.append(frac['inf'])
        else:
            d.append(frac[inverse(key)])
        c.append(value)
    except KeyError:
        continue

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1)
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans = ans * (m + 1) - 1

print(ans)

Submission status: Runtime Error

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

N = int(input())
A = [0]*N
B = [0]*N
C = [[0]*2 for _ in range(N)]
zero = 0
for i in range(N):
    A[i],B[i] = map(int,(input().split()))
    if A[i] == 0 and B[i] == 0:
        zero += 1
    elif B[i] == 0:
        C[i] = (A[i],B[i])
    elif B[i] > 0:
        g = math.gcd(A[i],B[i])
        C[i] = (A[i]//g,B[i]//g)
    else:
        g = math.gcd(A[i],B[i])
        C[i] = (-A[i]//g,-B[i]//g)

d = defaultdict(int)

for i in range(N):
    d[C[i]] += 1

ans = 1
for k in d.keys():
    if k[0] >= 0:
        if (-k[1],k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(-k[1],k[0])],MOD) - 1
            d[k],d[(-k[1],k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)
    else:
        if (k[1],-k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(k[1],-k[0])],MOD) -1
            d[k],d[(k[1],-k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)

print((ans-1)*(zero+1)%MOD)