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:
from collections import Counter
import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

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

p = []
for i, (a, b) in enumerate(AB) :
  g = gcd(a, b)
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) +  pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

print(ret - 1)

Submission status: Runtime Error

Solution code:
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
d = dict()
for _ in range(N):
    a, b = tuple(map(int, input().split()))
    g = gcd(a, b) * (a // abs(a))
    p = a // g, b // g
    d[p] = d.get(p, 0) + 1
counts = dict()
for k, v in d.items():
    a, b = k
    if counts.get((b, -a), False) or counts.get((-b, a), False):
        continue
    counts[k] = v, d.get((b, -a), 0) + d.get((-b, a), 0)
total = 1
for a, b in counts.values():
    total = (total * (pow(2, a, MOD) + pow(2, b, MOD) - 1)) % MOD
print((total + MOD - 1) % MOD)

Submission status: Runtime Error

Solution code:
import math
N = int(input())
mod = 1000000007
degs = {}
ans = 1
for i in range(N):
    A,B = map(int,input().split())
    if(A!=0):
        ab = B/A
    else:
        ab = "mugen"
    if(ab!=0):
        nakawaru = (-1)/ab
    else:
        nakawaru = "mugen"
    if(ab not in degs.keys()):
        degs[ab] = 1
    else:
        degs[ab] += 1
    if(nakawaru not in degs.keys()):
        ans = ans*2%mod
    else:
        ans = (ans + pow(2,i-degs[nakawaru],mod))%mod
print(ans-1)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,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

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        #nCrの一覧を返す。rの上限も
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res



#グローバル変数MODを決めてあげてください
MOD = 1000000007

N = int(input())
#双方ノンゼロ...
#Ai*Aj = - Bi* Bj　⇔　Ai/Bi == -Bj/Ai
#絶対値が同じやつら
#片方ゼロ→ノンゼロとは食い合わないがもう片方がゼロならダメ
#両方ゼロ→単騎で選ぶしかない
#ノンゼロ組、片方ゼロ組、両方ゼロ組に分ける
#ノンゼロ*(1 + Aだけゼロ + Bだけゼロ) + 両方ゼロ単騎
#1,1組→ 
NonZeroPlus = []
NonZeroMinus = []
AZero = 0
BZero = 0
TwoZero = 0
TwoOne = 0
for n in range(N):
    A,B = [int(hoge) for hoge in input().split()]
    if A!=0 and B!=0:
        G = math.gcd(abs(A),abs(B))
        if B < 0:
            G *= -1
            #B//Gが必ず正
        if A//G > 0:
            NonZeroPlus.append((A//G,B//G))
        else:#A//B < 0
            NonZeroMinus.append((B//G,-A//G))
    elif A==B==0:
        TwoZero += 1
    elif A == 0:
        AZero += 1
    else:
        BZero += 1
P = Counter(NonZeroPlus)
M = Counter(NonZeroMinus)
NonZero = ModInt(1)
Daburazu = ModInt(0)
for k in P.keys():
    X,Y = P[k],M[k]
    a = ModInt(2)
    b = ModInt(2)
    if Y:
        NonZero *= (a**X -1) + (b**Y -1) + 1 
    else:
        Daburazu += X
for k in M.keys():
    X,Y = P[k],M[k]
    a = ModInt(2)
    if X == 0:
        Daburazu += Y

#ノンゼロ組…コレ(0含む)
NonZero *= a**Daburazu
NonZero *= (a**AZero -1) + (b**BZero -1) + 1
NonZero += TwoZero
print(NonZero -1)

Submission status: Runtime Error

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = inpm()
        m = gcd(a,b)
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            a //= m
            b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        rev = ' '.join([str(-b),str(a)])
        flag = 0
        cnt = 0
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        cnt += dic1[rev]
        rev = ' '.join([str(b),str(-a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        cnt += dic1[rev]
        if flag:
            continue
        if a == 0 or b == 0:
            continue
        n1 = pow(2,dic[e],mod)-1
        n2 = pow(2,cnt,mod)-1
        if n1 == 0:
            ans *= (n2+1)
        elif n2 == 0:
            ans *= (n1+1)
        else:
            ans *= (n1+n2+1)
        ans %= mod
    num = dic['1 0'] + dic['0 1'] + dic['0 0']
    if num != 0:
        ans *= num
        ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math
import collections

def getGreatestCommonDivisor(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return getGreatestCommonDivisor(y, x % y)


N = int(input())
fishes = []
for _ in range(N):
    fishes.append([int(s) for s in input().split()])

# fishes = [
#           (3, 2),
# (3, 2),
# (-1 ,1),
# (2 ,-1),
# (-3 ,-9),
# (-8 ,12),
# (7 ,7),
# (8, 1),
# (8 ,2),
# (8, 4),
# ]

slopeCount = collections.defaultdict(int)
for x, y in fishes:
    gcl = getGreatestCommonDivisor(abs(x), abs(y))
    x //= gcl
    y //= gcl
    if x < 0:
        x = -x
        y = -y
    slopeCount[(x, y)] += 1

# print(slopeCount)

reversedPairs = dict()
independentCount = 0
for slope, count in slopeCount.items():
    x, y = slope
    rx, ry = (y, -x) if y >= 0 else (-y, x)
    if (x, y) in reversedPairs or (rx, ry) in reversedPairs:
        continue
    if (rx, ry) not in slopeCount:
        independentCount += count
        continue
    reversedPairs[(x, y)] = (count, slopeCount[(rx, ry)])
    

# print(reversedPairs, independentCount)

M = 1000000007
def subsetNum(count):
    r = 1
    for _ in range(count):
        r *= 2
        r %= M
    return r

result = subsetNum(independentCount)
if len(reversedPairs) == 0:
    result -= 1
    result %= M
    print(result)
else:
    for c1, c2 in reversedPairs.values():
        result *= (subsetNum(c1) - 1 + subsetNum(c2) - 1 + 1)
        result %= M
    result -= 1
    result %= M
    print(result)

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
import math

n = int(input())
a=[0]*n
b = [0]*n
for i in range(n):
    a[i],b[i] = map(int, input().split())

d=dict()
for i in range(n):
    g=math.gcd(a[i],b[i])
    if g!=1:
        a[i]//=g
        b[i]//=g
    if b[i]<0:
        a[i]*=-1
        b[i]*=-1
    if a[i]==0 or b[i]==0:
        a[i]=0
        b[i]=0
    try:
        d[(a[i],b[i])]+=1
    except:
        d[(a[i],b[i])]=1
ok=n
ls=[]
for ap,bp in d.keys():
    now = d[ap,bp]
    try:
        anow = ap
        bnow = bp
        if a[i]<0:
            anow*=-1
            bnow*=-1
        ok = ok-now-d[(-bnow,anow)]
        ng = d[(-bnow,anow)]
        ls.append(mint(pow(2,now,MOD))+mint(pow(2,ng,MOD)-1))
        d[ap,bp]=0
        d[(-bnow,anow)]=0
    except:
        pass

ans=mint(pow(2,ok,MOD))
for i in ls:
    ans*= i

ans-=1

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

def main():
    N = int(input())
    mod = 10**9 + 7
    AB = {}
    pos = set()
    for _ in range(N):
        a, b = map(int, input().split())
        g = gcd(a, b)
        a, b = a // g, b // g
        if a * b < 0 and a > 0:
            a, b = -a, -b
        if a * b > 0 and a < 0:
            a, b = -a, -b
        if a * b == 0:
            a, b = abs(a), abs(b)
        if a * b > 0:
            pos.add((a, b))
        AB[(a, b)] = AB.get((a, b), 0) + 1
    t = N - AB.get((0, 0), 0)
    r = 1
    for a, b in pos:
        p = AB[(a, b)]
        n = AB.get((-b, a), 0)
        r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
        r %= mod
        t -= (p + n)
    p = AB.get((0, 1), 0)
    n = AB.get((1, 0), 0)
    r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
    t -= (p + n)
    r *= pow(2, t, mod)
    r -= 1

    if (0, 0) in AB:
        r += AB[(0, 0)]

    return r % mod

print(main())

Submission status: Runtime Error

Solution code:
from fractions import gcd

MOD = 1000000007


def pow2(e):
    res = 1
    b = 2
    while e:
        if e & 1:
            res = res * b % MOD
        e >>= 1
        b = b * b % MOD
    return res


N = int(input())
counts = {}
for _ in range(N):
    a, b = map(int, input().split())
    g = gcd(a, b)
    a /= g
    b /= g
    if b == 0 and a != 0:
        a = 1
    if a == 0 and b != 0:
        b = 1
    if a < 0:
        a *= -1
        b *= -1
    counts[(a, b)] = counts.get((a, b), 0) + 1

res = 1
while counts:
    (a, b), cnt = counts.popitem()
    c, d = -b, a
    if c < 0:
        c *= -1
        d *= -1
    cnt2 = counts.pop((c, d), 0)
    res = res * (pow2(cnt) + pow2(cnt2) - 1) % MOD
print((res - 1) % MOD)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())
a = []
b = []

for i in range(n):
    l = list(map(int, input().split()))
    a.append(l[0])
    b.append(l[1])

a = np.array(a)
b = np.array(b)

l = np.dot(a.reshape((len(a), 1)), a.reshape((1, len(a)))) + np.dot(b.reshape((len(b), 1)), b.reshape((1, len(b))))
l = l.flatten()

print(np.sum(l == 0))

Submission status: Runtime Error

Solution code:
import math,sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
MOD = 1000000007
d = defaultdict(int)
for i in range(n):
  a,b = map(int,input().split())
  g = math.gcd(a,b)
  a,b = a//g,b//g
  if a<0:
    a,b = -a,-b
  d[str(a)+':'+str(b)] += 1
c = 1
for i in d.keys():
  if d[i] != 0:
    cur = pow(2,d[i],MOD)
    if '-' in i:
      ind = i.index(':')
      ci = i[ind+2:] + ':' + i[:ind]
    else:
      ind = i.index(':')
      ci = i[ind+1:] + ':-' + i[:ind]
    if ci in d.keys():
      cur += pow(2,d[ci],MOD)-1
      d[ci] = 0
    c = (c*cur)%MOD
print(c-1)

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)

# a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

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


print(ans - 1)

Submission status: Runtime Error

Solution code:
n = int(input())
A_B_dict = {}
for i in range(n):
    a, b = map(int,input().split())
    temp = a/b
    if temp in A_B_dict:
        A_B_dict[temp] += 1
    else:
        A_B_dict[temp] = 1
net_dict = {}
if 0 in A_B_dict:
    net_dict[0] = A_B_dict[0]
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = A_B_dict[i] + A_B_dict[temp] +1
        else:
            pass
    else:
        net_dict[temp] = A_B_dict[i] + 1
ans = 1
for k in net_dict.values():
    ans = (ans*k)%1000000007
print((ans-1))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7
MAX = 3*(10**5)
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, '.14f').rstrip('0').rstrip('.')
    cnt = d[tmp1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    tmp2 = format(a / b, '.14f').rstrip('0').rstrip('.')
    d[tmp2] += 1
# print(d)
print(ans-1)

Submission status: Runtime Error

Solution code:
from functools import cmp_to_key

MOD = 10 ** 9 + 7


def func(a, b):
    if a[0] * b[1] == a[1] * b[0]:
        return 0
    elif a[0] * b[1] < a[1] * b[0]:
        return - 1
    else:
        return 1


n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
    if a[i] < 0:
        a[i] = -a[i]
        b[i] = -b[i]
    if a[i] == 0 and b[i] < 0:
        b[i] = -b[i]
l = sorted(zip(a, b), key=cmp_to_key(func))
li = [[1, 0, l[0][0], l[0][0]]]
for i in range(n - 1):
    a, b = l[i]
    c, d = l[i + 1]
    if b <= 0:
        break
    if a * d == b * c:
        li[-1][0] += 1
    else:
        li.append([1, 0, c, d])
else:
    a, b = l[-2]
    c, d = l[-1]
    if b > 0:
        if a * d == b * c:
            li[-1][0] += 1
        else:
            li.append([1, 0, c, d])
        i = n
idx = 0
cnt = 0
for j in range(i, n):
    a, b = l[j]
    a, b = -b, a
    while idx < len(li) and li[idx][2] * b < li[idx][3] * a:
        idx += 1
    if idx < len(li) and li[idx][2] * b == li[idx][3] * a:
        li[idx][1] += 1
    else:
        cnt += 1
ans = 1
for a, b, c, d in li:
    ans *= (pow(2, a, MOD) + pow(2, b, MOD) - 1)
    ans %= MOD
print(((ans) * (pow(2, cnt, MOD)) // 2 - 1) % MOD)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import gcd
from collections import defaultdict


n = readint()

mod = 1000000007

d = defaultdict(int)

for i in range(n):
    a,b = readints()
    g = gcd(a,b)
    a//=g
    b//=g
    if a<0:
        a*=-1
        b*=-1
    d[(a,b)]+=1

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

print(ans-1)

Submission status: Runtime Error

Solution code:
n=int(input())
mod=10**9+7
pow2=[1]
for i in range(n+10):
    pow2.append(pow2[-1]*2%mod)

P=[] #[比較する数,正負の場合分け]
Q=[]
zero=0
for i in range(n):
    a,b=map(int,input().split())
    if a*b==0:
        zero+=1
    elif a*b>0:
        P.append([a/b,0])
    else:
        P.append([-b/a,1])
P.sort()
#print(P)

now=P[0][0]
cnt0=0
cnt1=0
d=n
ans=1
for p in P:
    if now!=p[0]:
        if cnt0*cnt1>0:
            d-=cnt0+cnt1
            ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod
            #print(cnt0,cnt1,d,ans)
        cnt0=0
        cnt1=0
    now=p[0]
    if p[1]==0:
        cnt0+=1
    else:
        cnt1+=1
if cnt0*cnt1>0:
    d-=cnt0+cnt1
    ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod

if zero>1:
    d-=zero
    ans=ans*(zero+1)%mod
ans=ans*pow2[d]%mod
print(ans-1)

Submission status: Runtime Error

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

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

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

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[p] = True
            k += 1
        else:
            break


    cnt2 = 0

    ok = n-1
    ng = i+1
    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]) <= 0.002:
            p = ang[k][1]
            if ab[p][0]*ab[idx][0] + ab[p][1]*ab[idx][1] == 0:
                cnt2 += 1
                used[p] = True
            k += 1
        else:
            break

    if cnt2 != 0:
        res = res*(pow(2,cnt,mod) + 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
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    for x, y in F:
      	if x == 0 and y == 0: tan = "NG"
        elif x != 0: tan = y / x
        else: tan = "Inf"
        if tan in D: D[tan] += 1
        else: D[tan] = 1

    ans = 1
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            if key == "Inf":
                op = (0 if 0 not in D else D[0])
                used |= {0}
            elif key == 0: 
                op = (0 if "Inf" not in D else D["Inf"])
                used |= {"Inf"}
            else: 
                op = (0 if -1 / key not in D else D[-1 / key])
                used |= {-1 / key}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    if "NG" in D: ans += D["NG"]
    ans = (ans - 1) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

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)
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
ans = 0
f = 1
p = [None]*len(cnt)
vs = cnt.values()
for i, v in enumerate(vs):
    p[i] = pow(2, v, mod)    
    f = f * p[i] % mod
for i, v in enumerate(vs):
    f = f * pow(p[i], mod-2, mod) % mod
    ans += v * f
    ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
st = {}
dz = 0
for i in range(N):
    a, b = map(int,input().split())
    if a == 0 and b == 0:
        dz += 1
    elif b == 0:
        if 'inf' in st:
            st['inf'] += 1
        else:
            st['inf'] = 1
    else:
        c = a / b
        if c in st:
            st[c] += 1
        else:
            st[c] = 1
ans = 1
if 'inf' in st and 0 in st:
    ans *= (2**(st['inf']+2**(st[0])-1))
    del st['inf']
    del st[0]
alr = set()
for i in st:
    if i in alr:
        pass
    else:
        g = -1/i
        if g in st:
            ans *= (2**(st[i])+2**(st[g])-1)
            alr |= {g,i}
for i in alr:
    del st[i]
for key, value in st.items():
    ans *= 2**value
print(ans-1+dz)

Submission status: Runtime Error

Solution code:
import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    for x, y in F:
        if x == y == 0: tan = "NG"
        elif x == 0: tan = "Inf"
        elif y == 0: tan = 0
        else: tan = Fraction(y, x)

        if tan in D: D[tan] += 1
        else: D[tan] = 1

    ans = 1
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            if key == "Inf":
                op = (0 if 0 not in D else D[0])
                used |= {0}
            elif key == 0: 
                op = (0 if "Inf" not in D else D["Inf"])
                used |= {"Inf"}
            else: 
                nu, de = key.numerator, key.denominator
                op = (0 if Fraction(-de, nu) not in D else D[Fraction(-de, nu)])
                used |= {Fraction(-de, nu)}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    if "NG" in D: ans += D["NG"]
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import math
MOD = 1000000007
N = int(input())
A = []
d = {}
for i in range(N):
	a,b = map(int,input().split())
	g = math.gcd(a,b)
	if a < 0:
		a *= -1
		b *= -1
	if a == 0 and b < 0:
		b *= -1
	a = a // g
	b = b // g
	if (a,b) in d:
		d[(a,b)] += 1
	else:
		d[(a,b)] = 1

ans_sp = 0
if (0,0) in d:
	ans_sp += d[(0,0)]

def pow(n, k):
	ret = 1
	while k > 0:
		if k % 2 == 1:
			ret = ret * n % MOD
		n = n * n % MOD
		k = k // 2
	return ret

ans = 1
for k in d:
	a,b = k[0], k[1]
	v = d[k]
	x,y = b,-a
	if x < 0:
		x *= -1
		y *= -1
	if (x,y) in d:
		if  b > y:
			continue
		tmp = (pow(2,v) + pow(2,d[(x,y)]) - 1) % MOD
		ans = (ans * tmp) % MOD
	else:
		ans = (ans * pow(2,v)) % MOD
print(ans_sp + ans - 1)

Submission status: Runtime Error

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

adivb = [ab[i][0] / ab[i][1] for i in range(n)]
bdiva = [float('inf') if ab[i][0] == 0 else ab[i][1] / ab[i][0]
         for i in range(n)]

print(adivb, bdiva)
ans = pow(2, n) - 1

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from math import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    d=defaultdict(lambda:[0,0])
    for _ in range(N):
        a,b=map(int,input().split())
        g=gcd(a,b)
        a//=g
        b//=g
        if a<0:
            a*=-1
            b*=-1
        if a*b>0:
            d[(a,b)][0]+=1
        elif a*b<0:
            d[(-b,a)][1]+=1
        else:
            d[0][0]+=1
    l=[]
    zero=0
    other=0
    for k,a in d.items():
        if k==0:
            zero=a[0]
        else:
            if a[0] and a[1]:
                l.append((a[0],a[1]))
            else:
                other+=sum(a)
    ans=pow(2,other,MOD)*(zero+1)
    ans%=MOD
    dp=[[0]*2 for _ in range(len(l)+1)]
    dp[0][0]=1
    for i in range(len(l)):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        dp[i+1][1]=(dp[i][0]+dp[i][1])*(pow(2,l[i][0],MOD)+pow(2,l[i][1],MOD)-2)
        dp[i+1][0]%=MOD
        dp[i+1][1]%=MOD
    ans*=sum(dp[-1])
    ans-=1
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()