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
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math
double_zero_cnt = 0
a_zero_cnt = 0
b_zero_cnt = 0
d = defaultdict(list) # [a, b] ngのそれぞれの個数
a_b = []
b_a = []
for a, b in ab:
    if a == 0 and b == 0:
        double_zero_cnt += 1
        continue
    elif a == 0:
        a_zero_cnt += 1
        continue
    elif b == 0:
        b_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        b *= (-1)
        a *= (-1) # 必ずbは正
    a_b.append((a, b))
c = Counter(a_b)
key_list = list(c.keys())
for key in key_list:
    a, b = key
    if a < 0:
        a *= (-1)
        b *= (-1)
    if d[(-b, a)] != []:
        continue
    if c[(-b, a)] != 0:
        d[(a, b)] = [c[(a, b)], c[(-b, a)]]
ans = 1
used_cnt = double_zero_cnt
for key in d.keys():
    if d[key] == []:
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod
    ans *= mul
    ans %= mod
if a_zero_cnt > 0 or b_zero_cnt > 0:
    ans *= (pow(2, a_zero_cnt, mod) + pow(2, b_zero_cnt, mod) - 1)
    ans %= mod
    used_cnt += a_zero_cnt + b_zero_cnt
ans *= pow(2, n - (used_cnt), mod)
ans %= mod
ans -= 1
ans += double_zero_cnt
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math
double_zero_cnt = 0
a_zero_cnt = 0
b_zero_cnt = 0
d = defaultdict(list) # [a, b] ngのそれぞれの個数
a_b = []
b_a = []
for a, b in ab:
    if a == 0 and b == 0:
        double_zero_cnt += 1
        continue
    elif a == 0:
        a_zero_cnt += 1
        continue
    elif b == 0:
        b_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        b *= (-1)
        a *= (-1) # 必ずbは正
    a_b.append((a, b))
c = Counter(a_b)
for key in c.keys():
    a, b = key
    if a < 0:
        a *= (-1)
        b *= (-1)
    if d[(-b, a)] != []:
        continue
    if c[(-b, a)] != 0:
        d[(a, b)] = [c[(a, b)], c[(-b, a)]]
ans = 1
used_cnt = double_zero_cnt
for key in d.keys():
    if d[key] == []:
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod
    ans *= mul
    ans %= mod
if a_zero_cnt > 0 or b_zero_cnt > 0:
    ans *= (pow(2, a_zero_cnt, mod) + pow(2, b_zero_cnt, mod) - 1)
    ans %= mod
    used_cnt += a_zero_cnt + b_zero_cnt
ans *= pow(2, n - (used_cnt), mod)
ans %= mod
ans -= 1
ans += double_zero_cnt
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque
import math

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


from  fractions import Fraction

def frac(a, b):
    if a== 0 and b == 0:
        return (0, 0)
    if b == 0:
        return (1, 0)
    f = Fraction(a, b)
    a = f.numerator
    b = f.denominator
    return a, b


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, AB):
    adb = Counter()
    for a, b in AB:
        a, b = frac(a, b)
        adb[(a, b)] += 1
    M = Mod(1000000007)
    ans = 1 + adb[(0, 0)]
    done = {(0, 0)}
    for k, v in adb.items():
        if k in done:
            continue
        a, b = k
        f = Fraction(b, a)
        kk = (-f.numerator, f.denominator)
        n = adb[kk]
        done.add(k)
        done.add(kk)
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.sub(ans, 1)


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# E

import sys
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

# 再起回数上限変更
# sys.setrecursionlimit(1000000)
N = int(input())
data = defaultdict(int)


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

# a, b = (0,0)はそれを入れるのみなので，
# カウントから抜かして(a,b)の数を最後に足せば良い
# どちらかが0の場合は，
# a=0ならb=0のモノが対比となる

cnt_zero = 0

for i in range(N):
    a, b = map(int, input().split())
    div = gcd(abs(a), abs(b))

    # マイナスはaだけ
    if a <0 and b <0:
        a, b = -a, -b
    elif b < 0:
        a, b = -a, -b

    if a ==0 and b==0:
        cnt_zero += 1
        continue

    if a ==0:
        data[(0, 1)] += 1
        data[(1, 0)] += 0
        continue

    if b ==0:
        data[(1, 0)] += 1
        data[(0, 1)] += 0
        continue

    data[(a//div, b//div)] += 1
    if a > 0:
        data[(-b//div, a//div)] += 0
    else:
        data[(b // div, -a // div)] += 0

mod = 1000000007
res = 1


for d in data:
    if d[0]>=0 and d[1]>=0:
        val = data[d]
        a1 = data[(-d[1], d[0])]
        # print(d, val, a1)
        if val == 0:
            res *= pow(2, a1, mod)
        elif a1 > 0:
            res *= pow(2, val, mod) + pow(2, a1, mod) - 1
            data[(-d[1], d[0])] = 0
        else:
            res *= pow(2, val, mod)
        res %= mod
        # print(res)


print(res+cnt_zero-1)

Submission status: Runtime Error

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd
from fractions import Fraction

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    d1 = [defaultdict(int), defaultdict(int)]
    for i, (ai, bi) in enumerate(zip(it, it)):
        val = Fraction(ai, bi)
        d1[0 if val >= 0 else 1][val] += 1

    a1, a2 = d1
    ans = 1
    for k, v in a1.items():
        ik = -1/k
        if ik in a2:
            v2 = a2[ik]
            ans *= pow(2, v+v2, mod) - (pow(2, v, mod)-1)*(pow(2, v2, mod)-1)
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for k, v in a2.items():
        ik = -1/k
        if not ik in a1:
            ans *= pow(2, v, mod)
            ans %= mod

    print(ans-1)



if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import math

n = int(input())
mod = 10**9+7
d = {}
l = []
s = set()
zero = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        s1 = (0,1)
        s2 = (1,0)
    elif b == 0:
        s1 = (1,0)
        s2 = (0,1)
    else:
        
        g = math.gcd(a,b)
        if b > 0:
            a //= g
            b //= g
            s1 = (a,b)
            if a > 0:
                
                s2 = (-b,a)
            else: 
                
                s2 = (b,-a)
        else:
            a //= g
            b //= g
            s1 = (-a,-b)
            if a < 0:
                
                s2 = (b,-a)
            else:
                
                s2 = (-b,a)
    if s1 in d:
        d[s1] += 1
    else:
        d[s1] = 1
    if s1 in s:
        continue
    else:
        if s2 in d:
            l.append([s1,s2])
            s.add(s1)
            s.add(s2)
    
ans = 1
for a,b in l:
    count = (pow(2,d[a],mod)+pow(2,d[b],mod)-1)%mod
    ans *= count
    ans %= mod
for i,j in d.items():
    if i in s:
        continue
    else:
        ans *= pow(2,j,mod)
        ans %= mod

print(ans+zero-1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math
d = defaultdict(int)
n = int(input())
mod = 10**6+7
for i in range(n):
  a, b = map(int, input().split())
  if a ==0:
    A = 0
    B = 1
  elif b ==0:
    A = 1
    B = 0
  if b > 0:
    A = a//math.gcd(a,b)
    B = b//math.gcd(a,b)
  else:
    A = -a//math.gcd(a,b)
    B = -b//math.gcd(a,b)
  d[(A, B)] += 1

def pair(key):
  if key == (1, 0):
    return (0, 1)
  A, B = key
  return (B, -A)

for i in d:
  j = pair(i)
  
  ans += d[i]%mod * d[j]%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
n = int(input())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
di = {}
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return abs(a)
for a, b in ab:
    g = gcd(a, b)
    a, b = a//g, b//g
    if a*b>0:
        ind = (abs(a), abs(b))
    elif a*b<0:
        ind = (abs(b), abs(a))
    else:
        ind = 0
    if ind in di:
        x, y = di[ind]
    else:
        x = y = 0
    if a*b==0:
        if b!=0:
            di[0] = (x+1, y)
        elif a!=0:
            di[0] = (x, y+1)
    else:
        if a*b>0:
            di[ind] = (x+1, y)
        else:
            di[ind] = (x, y+1)
mod = 10**9+7
ans = 1
for i, j in di.values():
    ans *= (pow(2, i, mod)+pow(2, j, mod)-1)
    ans %= mod
print(ans-1)

Submission status: Runtime Error

Solution code:
import math
mod=1000000007
n=int(input())
iwashi_group={}

#傾きを第1象限(True)と第4象限(False)の座標で管理する
for i in range(n):
    a,b=map(int,input().split())
    
    if a*b>0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(a)//GCD,abs(b)//GCD)
        flag=True
    
    elif a*b<0:
        GCD=math.gcd(abs(a),abs(b))
        iwashi=(abs(b)//GCD,abs(a)//GCD)
        flag=False

    elif a==0 and b==0:
        Flag=True
        continue

    elif a==0:
        iwashi=(0,1)
        flag=True
    
    elif b==0:
        iwashi=(0,1)
        flag=False
  
    if iwashi in iwashi_group:
        if flag:
            iwashi_group[iwashi][0]+=1
        else:
            iwashi_group[iwashi][1]+=1
    else:
        if flag:
            iwashi_group[iwashi]=[1,0]
        else:
            iwashi_group[iwashi]=[0,1]

ans=1
for a,b in iwashi_group.values():
    ans=ans*(2**a+2**b-1)%mod
if Flag:
    print(ans)
else:
    print(ans-1)

Submission status: Runtime Error

Solution code:
from flactions import gcd 
from collections import defaultdict

def to_irreducible(a, b):
    if a == 0:
        return [0, 1]
    GCD = gcd(a, b)
    return [a//GCD, b//GCD]

MOD = 10**9 + 7
N = int(input())
daiichi_dict = defaultdict(int)
daini_dict = defaultdict(int)
zero_cases = 0

for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_cases += 1
    elif a * b >=0 and b != 0:
        a, b = to_irreducible(abs(a), abs(b))
        daiichi_dict[(a,b)] += 1
    else:
        a, b = to_irreducible(abs(b), abs(a))
        daini_dict[(a,b)] += 1
        daiichi_dict[(a,b)] += 0


ans = 1 
for key, value_daiichi in daiichi_dict.items():
    value_daini = daini_dict[key]
    ans *= (2**value_daiichi + 2**value_daini -1)
    ans %= MOD
print((ans+zero_cases-1) % MOD)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
MOD = 1000000007
n = int(input())
a = [0] * n
b = [0] * n
fractions = {}
for i in range(n):
    _a, _b = map(int, input().split())
    a[i], b[i] = _a, _b
    if _b == 0 and _a != 0:
        if 0 not in fractions:
            fractions[0] = 0
        fractions[0] += 1
        continue
    if (frac := Fraction(_a, _b)) not in fractions:
        fractions[frac] = 0
    fractions[frac] += 1

revs = {}

for frac in fractions:
    if frac in revs:
        continue
    if frac == Fraction(0):
        rev = 0
        revs[frac] = rev
        revs[rev] = frac
    elif (rev := Fraction(-1) / frac) in revs:
        revs[frac] = rev
        revs[rev] = frac
    else:
        revs[frac] = None

result = 1

checked = set()
for frac, val in fractions.items():
    if frac in checked:
        continue
    checked.add(frac)
    if (rev := revs[frac]) is None:
        result *= pow(2, val, MOD)
        result %= MOD
    else:
        checked.add(rev)
        result *= pow(2, val, MOD) + pow(2, fractions[rev], MOD) - 1
        result %= MOD

print(result - 1)

Submission status: Runtime Error

Solution code:
n = int(input())

md = 10*9+7
dic = {}
for i in range(n):
    a,b = map(int,input().split())
    k = a/b 
    if(k in dic):
        dic[k] += 1
    else:
        dic[k] = 1
print(dic)

cnt = 0
for i in dic.keys():
    if(i < 0):
        continue
    else:
        k = -i
        if(k in dic):
            cnt += dic[k]

ans = (2**n - 1)%md - (2**(n-2)*cnt)%md
print(ans%md)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
MOD = 1000000007
n = int(input())
a = [0] * n
b = [0] * n
fractions = {}
for i in range(n):
    _a, _b = map(int, input().split())
    a[i], b[i] = _a, _b
    if _b == 0 and _a != 0:
        if 0 not in fractions:
            fractions[0] = 0
        fractions[0] += 1
        continue
    if (frac := Fraction(_a, _b)) not in fractions:
        fractions[frac] = 0
    fractions[frac] += 1

revs = {}

for frac in fractions:
    if frac in revs:
        continue
    if (rev := Fraction(-1) / frac) in revs:
        revs[frac] = rev
        revs[rev] = frac
    else:
        revs[frac] = None

result = 1

checked = set()
for frac, val in fractions.items():
    if frac in checked:
        continue
    checked.add(frac)
    if (rev := revs[frac]) is None:
        result *= pow(2, val, MOD)
        result %= MOD
    else:
        checked.add(rev)
        result *= pow(2, val, MOD) + pow(2, fractions[rev], MOD) - 1
        result %= MOD

print(result - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from math import gcd
count = defaultdict(int)
N = int(sys.stdin.readline())

zeros = 0
for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A == B == 0:
        zeros += 1
        continue
    if A == 0:
        angle = (0, 1)
    elif B == 0:
        angle = (1, 0)
    else:
        sgn = A / abs(A)
        g = gcd(A, B)
        angle = (A / sgn / g, B / sgn / g)

    count[angle] += 1
# print(count)

pairs = {}
solos = []
for k1 in count:
    if k1 in pairs:
        continue
    if k1 == (0, 1):
        if (1, 0) in count:
            pairs[(1, 0)] = k1
        else:
            solos.append(k1)
        continue

    A, B = k1
    sgn = -B / abs(B)
    k2 = (-B / sgn, A / sgn)
    if k2 in count:
        pairs[k2] = k1
    else:
        solos.append(k1)
# print(pairs, solos)

P = 1000000007


def pow2(n):
    # if n < 30:
    #     return 2 ** n

    # p = pow2(n // 2)
    # pp = (p * p) % P
    # if n % 2 == 1:
    #     return (2 * pp) % P
    # else:
    #     return pp
    return pow(2, n, P)


result = 1
for p in pairs:
    # print("pair", p, count[p], pairs[p], count[pairs[p]])
    n = count[p]
    m = count[pairs[p]]
    result = result * ((pow2(n) - 1) + (pow2(m) - 1) + 1) % P
for k in solos:
    # print("solo", k, count[k])
    result = result * pow2(count[k]) % P

print(result + zeros - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
from math import gcd
count = defaultdict(int)
N = int(sys.stdin.readline())

zeros = 0
for i in range(N):
    A, B = [int(x) for x in input().split()]
    if A == B == 0:
        zeros += 1
        continue
    if A == 0:
        angle = (0, 1)
    elif B == 0:
        angle = (1, 0)
    else:
        sgn = A / abs(A)
        g = gcd(A, B)
        angle = (A / sgn / g, B / sgn / g)

    count[angle] += 1


pairs = {}
solos = []
for k1 in count:
    if k1 in pairs:
        continue
    if k1 == (0, 1):
        if (1, 0) in count:
            pairs[(1, 0)] = k1
        continue

    A, B = k1
    sgn = -B / abs(B)
    k2 = (-B / sgn, A / sgn)
    if k2 in count:
        pairs[k2] = k1
    else:
        solos.append(k1)
# print(pairs, solos)

P = 1000000007


def pow2(n):
    # if n < 30:
    #     return 2 ** n

    # p = pow2(n // 2)
    # pp = (p * p) % P
    # if n % 2 == 1:
    #     return (2 * pp) % P
    # else:
    #     return pp
    return pow(2, n, P)


result = 1
for p in pairs:
    # print("pair", p, count[p], pairs[p], count[pairs[p]])
    n = count[p]
    m = count[pairs[p]]
    result = result * ((pow2(n) - 1) + (pow2(m) - 1) + 1) % P
for k in solos:
    # print("solo", k, count[k])
    result = result * pow2(count[k]) % P

print(result + zeros - 1)

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 = []
lst = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod)
        ans %= mod
        n -= 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        if a_zero:
            lst.append(b_zero)
        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

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:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

mod=10**9+7

#初期値が0の辞書

pp = {} 
pm = {} 

from fractions import gcd
zero=0
for _ in range(n):
    a,b=map(int,input().split())

    if a*b!=0:
        tmp=gcd(a,b)
        a=a//tmp
        b=b//tmp

        if a*b>0:
            if (a,b) in pp:
                pp[(a,b)]+=1
            else:
                pp[(a,b)]=1
        else:
            if (a,b) in pm:
                pm[(a,b)]+=1
            else:
                pm[(a,b)]=1

    elif a==0 and b==0:
        zero+=1
    else:
        if (a,b) in pp:
            pp[(a,b)]+=1
        else:
            pp[(a,b)]=1

            

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    pm_v=pm[(-1*b,a)]+pm[(b,-1*a)]
    if pm_v>0:
        result=result*((2**pp_v-1)+(2**pm_v-1)+1)
    else:
        result=result*(2**pp_v)

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    pp_v=pp[(-1*b,a)]+pp[(b,-1*a)]

    if pp_v==0:
        result=result*(2**pm_v)

print(result-1+zero)

Submission status: Runtime Error

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
C = Counter()
for i in range(N):
    a, b = MAP()
    g = gcd(a, b)
    ga, gb = a // g, b // g
    C[((a < 0) ^ (b < 0), abs(ga), abs(gb))] += 1

ans = 1
for k, v in C.items():
    if v == 0:
        continue
    op, a, b = k
    ans *= pow(2, C[(op, a, b)], MOD) + pow(2, C[(1-op, b, a)], MOD) - 1
    ans %= MOD
    if (1-op, b, a) in C:
        C[(1-op, b, a)] = 0
print((ans-1)%MOD)

Submission status: Runtime Error

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
C = Counter()
for i in range(N):
    a, b = MAP()
    g = gcd(a, b)
    ga, gb = a // g, b // g
    C[((a < 0) ^ (b < 0), abs(ga), abs(gb))] += 1

ans = 1
for k, v in C.items():
    if v == 0:
        continue
    op, a, b = k
    ans *= pow(2, C[(op, a, b)], MOD) + pow(2, C[(1-op, b, a)], MOD) - 1
    if (1-op, b, a) in C:
        C[(1-op, b, a)] = 0
print(ans)

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 -= 1
    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

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:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from cmath import phase
from math import gcd
from collections import Counter
def resolve():
    n = int(input())
    zero = 0
    counter = Counter()
    for _ in range(n):
        x, y = map(int, input().split())
        # eliminate 0 vector
        if x == 0 and y == 0:
            zero += 1
            continue
        # standardize (0 <= arg(z) < pi)
        g = gcd(x, y)
        x //= g
        y //= g
        if y < 0:
            x *= -1
            y *= -1
        elif y == 0:
            x, y = 1, 0
        counter[complex(x, y)] += 1

    k = len(counter)
    C = list(counter.items())
    C.sort(key = lambda tup:phase(tup[0]))
    vector = [tup[0] for tup in C]
    count = [tup[1] for tup in C]

    res = 0
    dp = [0] * (k + 1)
    dp[0] = 1
    for i in range(k):
        z = vector[i]
        vert = z.imag - z.real * 1j
        dp[i + 1] += dp[i]
        dp[i + 1] += (pow(2, count[i], MOD) - 1) * dp[i] * pow(2, -counter[vert] % (MOD - 1), MOD)
        dp[i + 1] %= MOD

    res = dp[k]
    res -= 1
    res += zero
    assert(zero > 0)
    print(res % MOD)
resolve()

Submission status: Runtime Error

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    i//=math.gcd(i,j)
    j//=math.gcd(i,j)
    if i!=0 and j!=0:
        b[i/j]+=1
        c[j/i]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0)-1)*(pow(2,b0)-1))


for k,v in b.items():
    if c[-k]!=0:
        ans*=((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        w.append((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        ans%=mod
    else:
        ans*=pow(2,v)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

Submission status: Runtime Error

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

n=int(input())
a= [list(map(int, input().split())) for i in range(n)]
b=defaultdict(int)
c=defaultdict(int)
b0=0
c0=0
mod=1000000007
ans=1
cnt=0
for i,j in a:
    i/=math.gcd(i,j)
    j/=math.gcd(i,j)
    if i!=0 and j!=0:
        b[i/j]+=1
        c[j/i]+=1
    elif i==0 and j!=0:
        b0+=1
    elif i!=0 and j==0:
        c0+=1
    else:
        cnt+=1
w=[]
if c0!=0 or b0!=0:
    ans*=pow(2,c0+b0)-((pow(2,c0)-1)*(pow(2,b0)-1))


for k,v in b.items():
    if c[-k]!=0:
        ans*=((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        w.append((pow(2,c[-k]+v)-(pow(2,c[-k])-1)*(pow(2,v)-1)))
        ans%=mod
    else:
        ans*=pow(2,v)
        ans%=mod

w=collections.Counter(w)
w=list(w.most_common())

for i,j in w:
    for k in range(j//2):
        ans*=pow(i,mod-2,mod)
ans+=cnt-1
print(int(ans%mod))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2147483647)


n=int(input())

mod=10**9+7

#初期値が0の辞書
from collections import defaultdict
pp = defaultdict(lambda: 0) 
pm = defaultdict(lambda: 0) 

from fractions import gcd

for _ in range(n):
    a,b=map(int,input().split())
    tmp=gcd(a,b)
    a=a//tmp
    b=b//tmp

    if a*b>0:
        pp[(a,b)]+=1
    else:
        pm[(a,b)]+=1
            
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = mod #割る数
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#print(pp_k,pm_k)
result=1
for key in pp.keys():
    pp_v=pp[key]
    a,b=key[0],key[1]
    pm_v=pm[(-1*b,a)]+pm[(b,-1*a)]
    result=result*((2**pp_v-1)+(2**pm_v-1)+1)

for key in pm.keys():
    pm_v=pm[key]
    a,b=key[0],key[1]
    pp_v=pp[(-1*b,a)]+pp[(b,-1*a)]

    if pp_v==0:
        result=result*(2**pm_v)

print(result-1)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import setrecursionlimit
from queue import deque
from math import factorial
setrecursionlimit(10 ** 7)

mod = 10**9+7

dic = {}
p = 0

n = int(stdin.readline().rstrip())
for i in range(n):
    a,b = map(int,stdin.readline().rstrip().split())
    if a == 0 and b == 0:
        p += 1
        continue
    if b == 0:
        if "s" not in dic:
            dic["s"] = 1
        else:
            dic["s"] += 1
        continue
    if str(-a/b) in dic:
        dic[str(-a/b)] += 1
    else:
        dic[str(-a/b)] = 1

point = 0
le = 0
li = []

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))#組み合わせ

for i,j in dic.items():
    if i == "s":
        if "0" in dic:
            point += j
            point %= mod
    elif i == "0":
        if "s" in dic:
            point += j
            point %= mod
    else:
        li.append(str(-1/float(i)))
        if str(-1/float(i)) in dic:
            point += j
            le += 1

print(2**len(dic)%mod-2**(n-point)%mod-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import collections
import fractions

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()


MOD = 1000000007
N = ni()
cnt_ab0 = cnt_a0 = cnt_b0 = 0
cnt_r = collections.Counter()

for i in range(N):
    a, b = nm()
    if a == 0 and b == 0:
        cnt_ab0 += 1
    elif a == 0:
        cnt_a0 += 1
    elif b == 0:
        cnt_b0 += 1
    else:
        r = fractions.Fraction(a, b)
        cnt_r[r] += 1


def solve():
    rpairs = set()
    for r in cnt_r.keys():
        if r > 0:
            rpairs.add(r)
        else:
            rpairs.add(-1 / r)

    mcnt = max(cnt_r.values())
    pow2 = [1] * (mcnt + 1)
    for i in range(1, mcnt + 1):
        pow2[i] = (pow2[i - 1] << 1) % MOD

    ans = 1
    for r1 in rpairs:
        r2 = -1 / r1
        p = pow2[cnt_r[r1]] + pow2[cnt_r[r2]] - 1
        ans *= p % MOD
        ans %= MOD
    p = pow(2, cnt_a0, MOD) + pow(2, cnt_b0, MOD) - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0 - 1
    return ans % MOD


if __name__ == "__main__":
    print(solve())