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:
N = int(input())
AB = []
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    AB.append(Atmp/Btmp)

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

from collections import Counter
C = Counter(AB)

kaburi = []
forsum = []
for key in C:
    if key<0:
        if C[-1/key]!=0:
            kaburi.append([C[key],C[-1/key]])
            forsum.append(C[key]+C[-1/key])

p = 10**9+7

free = N-sum(forsum)
free2 = power_func(2,free,p)
L = len(kaburi)

out = 1
for i in range(len(kaburi)):
    X = kaburi[i][0]
    Y = kaburi[i][1]
    B = power_func(2,X,p)
    C = power_func(2,Y,p)
    out *= (B+C-1)%p
    out = out%p
print((out*free2-1)%p)

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

Solution code:
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, j in st.items():
    if i in alr:
        pass
    else:
        g = -1/i
        if g in st:
            ans *= (2**j+2**(st[g])-1)
            alr |= {g,i}
for i in alr:
    del st[i]
s = 0
for key, value in st.items():
    s += value
ans2 = pow(2,s,1000000007)
ans *= ans2
print((ans-1+dz)%1000000007)

Submission status: Runtime Error

Solution code:

n = int(input())
mod = 10**9+7
l1 = []
l2 = []
l3 = []
for i in range(n):
    a,b = map(int,input().split())
    s1 = -b/a
    s2 = a/b
    if s2 in l1:
        l3[l1.index(s2)] += 1
    else:
        l1.append(s2)
        l2.append(-1)
        l3.append(1)
        if s1 in l1:
            ind = l1.index(s1)
            l2[-1] = ind
            l2[ind] = len(l1)-1

done = set()
ans = 1
for i in range(len(l2)):
    if l2[i] < 0:
        ans *= 2
        ans %= mod
    else:
        if l2[i] in done:
            continue
        c1 = l3[i]
        c2 = l3[l2[i]]
        count = (pow(2,c1,mod)+pow(2,c2,mod)-1)%mod
        ans *= count
        ans %= mod
        done.add(i)
        done.add(l2[i])

print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import gcd
n = int(input())
same, diff, zero_a, zero_b = 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

def change(a, b):
    x = gcd(a, b)
    return a // x, b // x

for _ in range(n):
    a, b = map(int, input().split())
    x = gcd(a, b)
    a, b = a // x, b // x
    if a == b == 0:
        continue
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod) % mod

ans = ans * (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) - 1
print(ans % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from bisect import bisect_left
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

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

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない
    # イワシをソートする
    theta = [0]*N
    for i, (a, b) in enumerate(zip(A, B)):
        if a != 0:
            theta[i] = math.degrees(math.atan2(b, a))
        elif b > 0:
            theta[i] = math.pi/2
        else:
            theta[i] = -math.pi/2
    # print(theta)

    abtheta = sorted(zip(theta, A, B))
    # print(*abtheta, sep="\n")
    # 順にイワシを見てグループを探す。二分探索で探す。
    uf = UnionFind(N)

    nisyu = [th for th, _, _ in abtheta]*2
    nisyuni = abtheta*2

    start, end = 0, 0
    end2 = None
    for i in range(N):
        # イワシiと90度、180度、270度角度が異なるものはありますか
        # しゃくとりで
        th, a, b = abtheta[i]

        # print("A")
        # 90度の関係にあるもの
        while end <= N+i:
            thi, ai, bi = nisyuni[end]
            if ai*a+bi*b <= 0:
                break
            end += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end % N)
            end += 1
            thi, ai, bi = nisyuni[end]

        if end2 == None:
            end2 = end

        # print("B")
        # 270度の関係にあるもの
        while end2 <= N+i:
            thi, ai, bi = nisyuni[end2]
            if ai*a+bi*b >= 0:
                break
            end2 += 1

        # print("C")
        while ai*a+bi*b == 0:
            uf.unite(i, end2 % N)
            end2 += 1
            thi, ai, bi = nisyuni[end2]

        if end == start + 1:
            end += 1

    # UFにグループ情報が格納されたので計算していく
    # print(uf.tree)

    # for i in range(N):
    #     _, ai, bi = abtheta[i]
    #     for j in range(i+1, N):
    #         _, aj, bj = abtheta[j]
    #         if ai*aj+bi*bj == 0:
    #             print("あるやん")
    #             print((ai, bi), (aj, bj))

    # return
    # デフォルトディクトに変換する
    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(abtheta[i])

    ans = 1
    for key in d:
        # 各グループをさらに二つに分類
        maru = 1
        batu = 0
        th0, a0, b0 = d[key][0]
        for th, a, b in d[key][1:]:
            if a0 * a + b0*b == 0:
                batu += 1
            else:
                maru += 1
        buf = pow(2, maru, MOD)
        buf += pow(2, batu, MOD)
        buf -= 1
        buf %= MOD
        ans *= buf

    # print(d)
    print(ans-1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
kaori=[tuple(map(int,input().split())) for _ in range(n)]
ee=10e-8

kaori=[tuple(tup[0]/(tup[1]+ee),-tup[1]/(tup[0]+ee)) for tup in kaori]

cout=0

for i in range(n-1):
  for j in range(i+1,n):
    if kaori[i][0]==kaori[j][1]:
      pass
    else:cout+=1
      
      
print(cout%1000000007)

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 1000000007
s = {}

for _ in range(N):
    A, B = map(int, input().split())
    if s.get(A/B) == None:
        s[A/B] = 1
    else:
        s[A/B] += 1

f, ans = 0, 1
while len(s) > 0:
    k1, v1 = s.popitem()
    if -1/k1 in s.keys():
        v2 = s.pop(-1/k1)
        ans = (ans * ((pow(2, v1, MOD) + pow(2, v2, MOD) - 1) % MOD)) % MOD
        # pow(2, n, MOD) は二項定理による組み合わせの総和
    else:
        f += v1

ans = ((ans * (pow(2, f, MOD) % MOD)) % MOD - 1) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

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

t = []
d = {}
for a, b in AB:
    i = gcd(a, b)
    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))
    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 - 1)

Submission status: Runtime Error

Solution code:
mod=10**9+7
n=int(input())
fact=[1]
fact_inv=[1]
for i in range(n+1):#<< Nの最大値
    new_fact=fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))

def mod_comb(n,k,mod):
    return fact[n]*fact_inv[k]%mod*fact_inv[n-k]%mod

ab=[list(map(int,input().split())) for _ in range(n)]
k=[]
for i in range(n):
    a,b=ab[i]
    k.append(b/a)
k.sort()
print(k)
from bisect import bisect_left, bisect_right
ans=pow(2,n,mod)-1
d={}
dd={}
for x in k:
    y=1/x
    c=bisect_right(k,-y)-bisect_left(k,-y)
    cc=bisect_right(k,x)-bisect_left(k,x)
    dame=0
    if c==0:
        continue
    for i in range(2,c+2):
        dame+=pow(2,n-i,mod)*mod_comb(c,i-1,mod)*mod_comb(cc,i-1,mod)
        dame%=mod
    x=max(x,-y)
    if x in d:
        d[x]+=1
    else:
        d[x]=1
    if x in dd:
        pass
    else:
        dd[x]=dame
for v in dd.values():
    ans-=v
print(ans)

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())
    #a,b = 1,1
    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)
    else:
        gm.append(b/a)
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 - 1
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def main():
    n = int(input())
    mat = [list(map(int, readline().split())) for _ in range(n)]
    x = [a / b for a, b in mat]
    y = [-b / a for a, b in mat]

    from collections import Counter

    dislike = {i: [] for i in range(1, n + 1)}
    cx = Counter()
    cy = Counter()
    uf = UnionFind(n)

    for i, p in enumerate(x, 1):
        for j, q in enumerate(y, 1):
            if p == q:
                uf.union(i - 1, j - 1)
    sub = 0
    rem = n

    for val in uf.all_group_members().values():
        l = len(val)
        rem -= l
        if l >= 2:
            com = pow(2, l, MOD) - (l + 1)
            sub += (com * pow(2, rem, MOD) % MOD)

    ans = (pow(2, n, MOD) - 1 - sub) % MOD
    print(ans)


if __name__ == '__main__':
    main()

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
print(st,dz)
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, j in st.items():
    if i in alr:
        pass
    else:
        g = -1/i
        if g in st:
            ans *= (2**j+2**(st[g])-1)
            alr |= {g,i}
for i in alr:
    del st[i]
s = 0
for key, value in st.items():
    s += value
ans2 = pow(2,s,1000000007)
ans *= ans2
print((ans-1+dz)%1000000007)

Submission status: Runtime Error

Solution code:
from collections import Counter
from math import gcd
n = int(input())
same, diff, zero_a, zero_b = 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

def change(a, b):
    x = gcd(a, b)
    return a // x, b // x

for _ in range(n):
    a, b = map(int, input().split())
    x = gcd(a, b)
    a, b = a // x, b // x
    if a == b == 0:
        continue
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod)

ans = ans * (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) - 1
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import Fraction as fra
P=10**9+7

n=int(input())
G=[]
for index1 in range(n):
    a,b=map(int,input().split())
    if a<0 and b>0:
        G.append((-a,-b))
    elif a<0 and b<0:
        G.append((-a,-b))
    else:
        G.append((a,b))

D={}
S=set()
for i in range(n):
    x=G[i][0]
    y=G[i][1]
    temp=fra(x,y)
    if y>0:
        temp_over=fra(y,-x)
    else:
        temp_over=fra(-y,x)
    
    if temp in S:
        D[temp][0]+=1
    elif temp_over in S:
        D[temp_over][1]+=1
    else:
        D[temp]=[1,0]
        S.add(temp)



def culc(List):
    return (pow(2,List[0],P)+pow(2,List[1],P)-1)%P


ans=1
while S:
    now=S.pop()
    obj=D[now]
    ans=(ans*culc(obj))%P

print((ans-1)%P)

Submission status: Runtime Error

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from fractions import Fraction as Fra, gcd
from collections import Counter

def solve(N, A):
    MOD = 10 **9 + 7
    # Cant if dot product is 0
    count = Counter()
    for x, y in A:
        g = gcd(x, y)
        x //= g
        y //= g
        count[x, y] += 1

    # x,y = -y,x
    ans = 1
    for (x, y), c1 in count.iteritems():
        px, py = -y, x
        pg = gcd(px, py)
        px//=pg; py//=pg;
        c2 = count[px, py]
        if not c2:
            ans *= pow(2, c1, MOD)
        elif (x,y) < (px,py):
            f = pow(2, c1, MOD) + pow(2, c2, MOD) - 1
            ans *= f
    return ans - 1
    
    
N = rri()
A = [rrm() for _ in xrange(N)]
print solve(N, A)

Submission status: Runtime Error

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

mod = 1000000007
eps = 0.00001

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)
    else:
        ang.append(math.degrees(math.atan(b/a)))
ang.sort()

used = [False]*n
res = 1
rest = n

i = 0
while True:
    if i >= n:
        break
    if used[i]:
        continue
    val = ang[i]
    if val > 2*eps:
        break
    cnt = bisect.bisect_right(ang,val+eps) - i
    cnt2 = bisect.bisect_right(ang,val+90+eps) - bisect.bisect_left(ang,val+90-eps)
    if cnt2 > 0:
        rest = rest - cnt - cnt2
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
    i += cnt

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

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))
if l[0][1] > 0:
    li = [[1, 0, l[0][0], l[0][1]]]
else:
    li = []
i = -1
for i in range(1, n):
    a, b = l[i - 1]
    c, d = l[i]
    if d <= 0:
        break
    if a * d == b * c:
        li[-1][0] += 1
    else:
        li.append([1, 0, c, d])
idx = 0
cnt = 0
for j in range(n):
    a, b = l[j]
    if b > 0:
        continue
    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)) - 1) % MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    AB.append(Atmp/Btmp)

from collections import Counter
C = Counter(AB)

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

kaburi = []
forsum = []
for key in C:
    if key<0:
        if C[-1/key]!=0:
            kaburi.append([C[key],C[-1/key]])
            forsum.append(C[key]+C[-1/key])

p = 10**9+7

free = N-sum(forsum)
free2 = power_func(2,free,p)
L = len(kaburi)

out = 1

for i in range(len(kaburi)):
    X = kaburi[i][0]
    Y = kaburi[i][1]
    B = power_func(2,X,p)
    C = power_func(2,Y,p)
    out *= (B+C-1)%p
    out = out%p
print((out*free2-1)%p)

Submission status: Runtime Error

Solution code:
import math
def heikatu(A,B):
    if A % abs(B) ==0:
        return (A//abs(B),B//abs(B))
    if abs(B) % A == 0:
        return (1,B//A)
    
    c = 2
    while c <=math.sqrt(max(A,abs(B))):
        while A % c ==0 and B% c ==0:
            A //=c
            B//=c
        c+=1

    return (A,B)


def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod



def resolve():
    N = int(input())

    kp = dict()
    km = dict()
    zero = [0,0]
    for i in range(N):
        A,B = map(int,input().split())
        if A <0:
            A *= -1
            B *= -1


        xx = heikatu(A,B)

        if A == 0:
            zero[0]+=1
            continue
        if B == 0:
            zero[1]+=1
            continue

        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    tx = []
    if zero != [0,0]:
        tx.append(zero)

    for key in kp:
        A,B = key
        cou = kp[key]    
        if (B,-A) in km:
            tx.append([cou,km[(B,-A)]])
            km.pop((B,-A))
        else:
            tx.append([cou,0])
    for key in km:
        tx.append([0,km[key]])

    ans = 1
    mod = 1000000007
    for a,b in tx:
        xxx = 0
        if a != 0:
            xxx+=pow_r(2,a)
        if b != 0:
            xxx+=pow_r(2,b)
        if a !=0 and b!=0:
            xxx-=1
        ans = (ans*xxx) % mod

    ans = (ans+mod-1) % mod 

    print(ans)       


        







resolve()

Submission status: Runtime Error

Solution code:

from collections import defaultdict
from math import gcd

P=defaultdict(lambda :0)
n=int(input())
AB=[tuple(map(int,input().split()))for i in range(n)]



for a,b in AB:
    g=gcd(a,b)
    if a<0:
        a//=-g
        b//=-g
    else:
        a//=g
        b//=g
    P[(a,b)]+=1

ans=1
others=n
mod=1000000007
from copy import copy
k=copy(list(P.keys()))
for p in k:
    me=P[p]
    if me==0:
        continue
    a,b=p
    oppidx=(-b,a) if b<0 else (b,-a)
    opp=P[oppidx]
    if P[oppidx]!=0:
        others-=me+opp
        ans*=pow(2,me,mod)+pow(2,opp,mod)-1
        ans%=mod
    P[p]=0
    P[oppidx]=0

ans*=pow(2,others,mod)
ans
ans%=mod

print(ans-1)

Submission status: Runtime Error

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

M = 1000000007

# AB = [A / B for A, B in AB_list]
# BA = [-B / A for A, B in AB_list]
groups = dict()
group_keys = set()
ans_L = []

# print(AB_list)
# print(AB)
# print(BA)

def prepare(n, MOD):
 
    # 1! - n! の計算
    f = 2
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
     
    return factorials, invs

fac, invs = prepare(N, M)

def comb(n, r):
    return fac[n] * invs[r] * invs[n-r] % M

def all_comb(n):
    ret = 1
    for i in range(1, n+1):
        ret += comb(n, i)
    return ret


for _ in range(N):
    a,b = map(int, input().split())
    AB = a / b
    BA = -b / a
    if BA in group_keys:
        groups[BA][1] += 1
    elif AB in group_keys:
        groups[AB][0] += 1
    else:
        groups[AB] = [1, 0]
        group_keys.add(AB)

for i, j in groups.values():
    comb_i = all_comb(i)
    if j == 0:
        ans_L.append(comb_i)
    else:
        comb_j = all_comb(j)
        ans_L.append((comb_i + comb_j - 1) % M)

ans = 1
for i in ans_L:
    ans *= i % M
print(ans % M - 1)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import bisect
from math import gcd
n = int(input())
l = [None] * n
for i in range(n):
    a,b = map(int, input().split())
    g = gcd(a,b)
    l[i] = (a//g, b//g)

l.sort()
M = 1000000007
seen = [False] * n
vals = []

def sub(item):
    item1 = (item[1], -item[0])
    item2 = (-item[1], item[0])
    tmp = None
    count = 0
    li = bisect.bisect_left(l, item1)
    ri = bisect.bisect_right(l, item1)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
        
    li = bisect.bisect_left(l, item2)
    ri = bisect.bisect_right(l, item2)
    count += (ri-li)
    for v in range(li, ri):
        seen[v] = True
    if ri>li:
        tmp = l[li]
    
    return count, tmp

for i,item in enumerate(l):
    if seen[i]:
        continue
    count,tmp = sub(item)
    if count>0:
        count2, tmp = sub(tmp)
        vals.append((pow(2,count,M)+pow(2,count2,M)-1)%M)
    else:
        vals.append(2)
ans = 1
for v in vals:
    ans *= v
    ans %= M
print(ans-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
MOD = 10**9+7
# MOD = 998244353

n = int(input())
E = [list(map(int, input().split())) for i in range(n)]
d = defaultdict(int)
for e in E:
    if e[0] == 0 and e[1] == 0:
        d[(0, 0)] += 1
    elif e[0] == 0:
        k = 1 if e[1] > 0 else -1
        d[(0, k)] += 1
    elif e[1] == 0:
        k = 1 if e[0] > 0 else -1
        d[(k, 0)] += 1
    else:
        gcd = math.gcd(e[0], e[1])
        a, b = e[0]//gcd, e[1]//gcd
        if b < 0:
            a, b = -a, -b
        d[(a, b)] += 1

pd = 1
non = n
for k in d:
    if k[0] >= 0 and (-k[1], k[0]) in d:
        a, b = d[k], d[(-k[1], k[0])]
        pd = (pd*(pow(2, a, MOD) + pow(2, b, MOD) - 1))%MOD
        # print(a, b, pd)
        non -= (a+b)

# print(non, pd)
total = (pow(2, non, MOD)*pd - 1)%MOD
print(total)

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    mod = 10**9+7
    d = {}
    l1 = []
    l2 = []
    for i in range(n):
        a,b = map(int,input().split())
        s1 = -b/a
        s2 = a/b
        if s2 in d:
            d[s2] += 1
        else:
            l1.append(s2)
            l2.append(-1)
            d[s2] = 1
            if s1 in d:
                ind = l1.index(s1)
                l2[-1] = ind
                l2[ind] = len(l1)-1

    done = set()
    ans = 1
    for i in range(len(l2)):
        if l2[i] < 0:
            ans *= 2
            ans %= mod
        else:
            if l2[i] in done:
                continue
            c1 = d[l1[i]]
            c2 = d[l1[l2[i]]]
            count = (pow(2,c1,mod)+pow(2,c2,mod)-1)%mod
            ans *= count
            ans %= mod
            done.add(i)
            done.add(l2[i])

    print(ans-1)
            
if __name__ =="__main__":
    main()

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) if a else 1)
    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:
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, j in st.items():
    if i in alr:
        pass
    else:
        g = -1/i
        if g in st:
            ans *= (2**j+2**(st[g])-1)
            alr |= {g,i}
for i in alr:
    del st[i]
s = 0
for key, value in st.items():
    s += value
ans2 = pow(2,s,1000000007)
ans *= ans2
print((ans-1+dz)%1000000007)

Submission status: Runtime Error

Solution code:
N = int(input())
S = [input().split() for _ in range(N)]
count = N
for i in range(N-1):
    # print(int(S[i][0])/int(S[i][0]) - int(S[i][0])/int(S[i][0]))
    if int(S[i][0])/int(S[i][0]) != -(int(S[i][0])/int(S[i][0])):
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
from math import gcd
from collections import defaultdict

def sign(a):
    if a == 0:
        return 0
    else:
        return a//abs(a)

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

d = defaultdict(lambda: [0, 0])
zeros = 0

for i in range(n):
    g = gcd(a[i], b[i])
    a[i] //= g
    b[i] //= g
    if a[i]*b[i] > 0:
        d[(abs(a[i]), abs(b[i]))][0] += 1
    elif a[i]*b[i] < 0:
        d[(abs(b[i]), abs(a[i]))][1] += 1
    elif a[i] == 0 and b[i] != 0:
        d[(0, 1)][0] += 1
    elif b[i] == 0 and a[i] != 0:
        d[(0, 1)][1] += 1
    elif a[i] == b[i] == 0:
        zeros += 1

mod = 1000000007
cnt = 1
for pair in d.values():
    cnt *= pow(2, pair[0], mod) + pow(2, pair[1], mod) - 1
    cnt %= mod
cnt += zeros - 1
print(cnt)