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:
#!/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 = pow2[cnt_a0] + pow2[cnt_b0] - 1
    ans *= p % MOD
    ans %= MOD
    ans += cnt_ab0 - 1
    return ans % MOD


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

Submission status: Runtime Error

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a_b_value_count = {}
m_b_a_value_count = {}
zeroes = 0

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

	if a == 0 and b == 0:
		zeroes += 1
	else:
		if a == 0:
			a_b = 0
			m_b_a = INF
		elif b == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a / b
			m_b_a = -b / a

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

a_b = list(set(a_b_value_count.keys()))
m_b_a = [-1/item for item in a_b]

# a_b.sort()
# m_b_a.sort(reverse=True)


# print("a_b", a_b)
# print("a_b_value_count", a_b_value_count)
# print()

# print("m_b_a", m_b_a)
# print("m_b_a_value_count", m_b_a_value_count)

if len(a_b) != len(m_b_a):
	# print("Error!")
	exit()

n = len(a_b)
used = [False for _ in range(n)]

mba_to_ind = {}
for i in range(n):
	mba_to_ind[m_b_a[i]] = i

ans = 1
for i in range(n):
	# print("i", i)
	if not used[i]:
		a_b_key = a_b[i]
		# print("a_b_key", a_b_key)
		# if not connected
		if a_b_key not in m_b_a_value_count:
			# print("not connected")
			ans *= pow(2, a_b_value_count[a_b_key], MODULO)
			ans %= MODULO
			used[i] = True
			# for j in a_b_value_indices[a_b[i]]:
			# 	used[j] = True
		else:
			# print(" connected")
			s = a_b_value_count[a_b_key]
			t = m_b_a_value_count[a_b_key]
			# print("s, t", s, t)
			ans *= (1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1)
			ans %= MODULO

			# for j in a_b_value_indices[a_b[i]]:
			used[i] = True
			# for j in m_b_a_value_indices[a_b[i]]:
			used[mba_to_ind[a_b_key]] = True
	# print("ans", ans)
	# print("used", used)
	# print()


			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)


# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Runtime Error

Solution code:
from collections import Counter
n = int(input())
pp = []
a0 = 0
b0 = 0
z = 0
for i in range(n):
  a,b = map(int,input().split())
  if a==0 and b==0:
    z += 1
  elif a==0:
    a0 += 1
  elif b==0:
    b0 += 1
  else:
    pp.append(round(a/b,16))
    
mod = 10**9+7
a0 %= mod
b0 %= mod
z %= mod
p = Counter(pp)
r = 1
s = set()

for i in p.keys():
  if i in s:
    continue
  ans = p[i]
  f = round(-1/i,16)
  chk = p[f]
  r *= (pow(2,ans,mod)+pow(2,chk,mod)-1)%mod
  r %= mod
  s.add(f)
r *= (pow(2,a0,mod)+pow(2,b0,mod)-1)%mod
r %= mod
print((r+z-1)%mod)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
zero = 0
zero_l = 0
zero_r = 0
rest = N
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        # fishes.append((0, 0))
        zero += 1
        rest -= 1
    elif a == 0:
        # fishes.append((0, 1))
        zero_l += 1
    elif b == 0:
        # fishes.append((1, 0))
        zero_r += 1
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    # if a == 0 or b == 0:
    #     continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    if bad_count != 0:
        # good か bad からしか選ばないものは駄目
        ans *= pow(2, count + bad_count, mod) - (pow(2, count, mod) - 1) * (pow(2, bad_count, mod) - 1) 
        ans %= mod

        rest -= count + bad_count

# どちらかが0になっているもの
ans *= pow(2, zero_r + zero_l, mod) - (pow(2, zero_l, mod) - 1) * (pow(2, zero_r, mod) - 1)
ans %= mod
rest -= zero_r + zero_l

# 仲が悪いものが存在しないイワシの組み合わせ
ans *= pow(2, rest, mod)

# 全部選ばないものは駄目
ans += zero - 1
ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

a_b_value_count = {} # a_b values
m_b_a_value_count = {} # a_b values

used_a_b_keys = set()
# a_b_used = {}
# [False for _ in range(n)]
# m_b_a_used = [False for _ in range(n)]
used = [False for _ in range(n)]

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

	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

ans = 1
for a_b_key in a_b_value_count.keys():
	if a_b_key not in used_a_b_keys:
		# not connected
		if a_b_key not in m_b_a_value_count:
			ans *= pow(2, a_b_value_count[a_b_key], MODULO)
			ans %= MODULO
			used_a_b_keys.add(a_b_key)
			# m_b_a_used[-1/a_b_key] = True
		else:
			a = a_b_value_count[a_b_key]
			b = m_b_a_value_count[a_b_key]
			ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
			ans %= MODULO

			used_a_b_keys.add(a_b_key)
			used_a_b_keys.add(-1/a_b_key)


	# if not used[i]:
	# 	if len(graph[i]) == 0:
	# 		used[i] = True
	# 		ans *= 2
	# 		ans %= MODULO
	# 	else:
	# 		chet, nechet = 0, 0
	# 		# for item in 
	# 		a, b = dfs_chet_nechet(i)
	# 		ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
	# 		# ans *= comb(i)
	# 		ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Runtime Error

Solution code:
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        if a != 0 and b != 0:
            g = gcd(a, b) * a // abs(a)
        elif a != 0:
            g = b
        else:
            g = a
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Submission status: Runtime Error

Solution code:
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        g = gcd(a, b) * a // abs(a)
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import Counter

mod = 1000000007
 
N = int(sys.stdin.readline().strip())
fishes = []
zero = 0
zero_l = 0
zero_r = 0
rest = N
for _ in range(N):
    a, b = map(int, sys.stdin.readline().strip().split())
    # 角度だけが重要なので座標圧縮して良い
    if a == 0 and b == 0:
        # fishes.append((0, 0))
        zero += 1
        rest -= 1
    elif a == 0:
        # fishes.append((0, 1))
        zero_l += 1
    elif b == 0:
        # fishes.append((1, 0))
        zero_r += 1
    else:
        gcd = math.gcd(a, b)
        fishes.append((a // gcd, b // gcd))

# print(fishes)

# (a, b)ごとにカウント
counter = Counter(fishes)
# print(counter)

calculated = set()
ans = 1
# 組み合わせを計算
for ((a, b), count) in counter.items():
    # if a == 0 or b == 0:
    #     continue
    # 計算済みの場合
    if (a, b) in calculated:
        continue

    # 仲が悪いイワシの数
    bad_count = 0
    # 90度異なるものがダメ
    for (a_k, b_k) in ((-1, 1), (1, -1)):
        bad_pair = (b * a_k, a * b_k)
        if bad_pair in counter:
            bad_count += counter[bad_pair]
            calculated.add(bad_pair)

    # 仲が悪いイワシがいない場合
    if bad_count == 0:
        ans *= 2**count
        ans %= mod
    else:
        # 仲が良いものだけの組み合わせ
        good = 2**count
        
        # 仲が悪いものだけの組み合わせ
        bad = 2**bad_count

        # 全て選ばない場合は許容しないので1を引いておく
        ans *= good + bad - 1
        ans %= mod

    rest -= count + bad_count

if (1,0) not in counter:
    counter[(1,0)] = 0
if (0,1) not in counter:
    counter[(0,1)] = 0
if (0,0) not in counter:
    counter[(0,0)] = 0
ans *= 2**counter[(1, 0)] + 2**counter[(0, 1)] - 1
ans %= mod
rest -= zero_r + zero_l

# 仲が悪いものが存在しないイワシの組み合わせ
ans *= pow(2, rest, mod)

# 全部選ばないものは駄目
ans += zero - 1
ans %= mod


print(ans)

Submission status: Runtime Error

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

a_b_value_count = {} # a_b values
m_b_a_value_count = {} # a_b values

a_b_used = [False for _ in range(n)]
# m_b_a_used = [False for _ in range(n)]
used = [False for _ in range(n)]

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

	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		a_b_value_count[a_b] = a_b_value_count.get(a_b, 0) + 1
		m_b_a_value_count[m_b_a] = m_b_a_value_count.get(m_b_a, 0) + 1

ans = 1
for a_b_key in a_b_used.keys():
	if not a_b_used[a_b_key]:
		# not connected
		if m_b_a_value_count[a_b_key] == 1:
			ans *= pow(2, a_b_value_count[a_b_keys], MODULO)
			ans %= MODULO
			a_b_used[a_b_key] = True
			# m_b_a_used[-1/a_b_key] = True
		else:
			a = a_b_value_count[a_b_keys]
			b = m_b_a_value_count[a_b_keys]
			ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
			ans %= MODULO

			a_b_used[a_b_keys] = True
			a_b_used[-1/a_b_keys] = True


	# if not used[i]:
	# 	if len(graph[i]) == 0:
	# 		used[i] = True
	# 		ans *= 2
	# 		ans %= MODULO
	# 	else:
	# 		chet, nechet = 0, 0
	# 		# for item in 
	# 		a, b = dfs_chet_nechet(i)
	# 		ans *= ((1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1) % MODULO)
	# 		# ans *= comb(i)
	# 		ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Runtime Error

Solution code:
from collections import Counter
import fractions

P =1000000007
zz = 0
ABs = []
conb = []
uni = 0
pair = 0

N = int(input())
for _ in range(N):
  a,b = map(int, input().split())
  if b == 0:
    ABs.appned('1 0')
  elif b > 0:
    c = fractions.gcd(a,b)
    ABs.append(str(a//c)+' '+str(b//c))
  else:
    c = fractions.gcd(abs(a),abs(b))
    ABs.append(str(-a//c)+' '+str(-b//c))

d = Counter(ABs)

for i in d:
  if i == '0 0':
    zz = d[i]
  elif i[0] == '-':
    a, b = i.split()
    j = b+' '+a[1:]
    if d[j] > 0:
      conb.append([d[i],d[j]])
      pair += d[i]+d[j]
  elif i[0] == '0':
    j = '1 0'
    if d[j] > 0:
      conb.append([d[i],d[j]])
      pair += d[i]+d[j]
    
uni = N - zz - pair

rlt = (2**uni) % P
for p in conb:
  rlt *= (2**p[0] + 2**p[1] - 1) % P

rlt += zz - 1

print(rlt)

Submission status: Runtime Error

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
INF = 1e18+10

n = int(input())
a = [0 for i in range(n)]
b = [0 for i in range(n)]

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

graph = [[] for _ in range(n)]
value_indices = {} # a_b values
zeroes = 0
used = [False for _ in range(n)]
for i in range(n):
	if a[i] == 0 and b[i] == 0:
		zeroes += 1
		used[i] = True
		# for j in range(n):
		# 	graph[i].append(j)
		# 	graph[j].append(i)
	else:
		if a[i] == 0:
			a_b = 0
			m_b_a = INF
		elif b[i] == 0:
			a_b = INF
			m_b_a = 0
		else:
			a_b = a[i] / b[i]
			m_b_a = -b[i] / a[i]

		if m_b_a in value_indices:
			for j in value_indices[m_b_a]:
				graph[i].append(j)
				graph[j].append(i)
		value_indices[a_b] = value_indices.get(a_b, []) + [i]

# print("value_indices", value_indices)
# print("graph", graph)

def dfs_chet_nechet(i, chet=0, nechet=0):
	# print("dfs_chet_nechet", i)
	used[i] = True
	a, b = chet, nechet
	for child in graph[i]:
		if not used[child]:
			a1, b1 = dfs_chet_nechet(child, nechet, chet)
			a += b1
			b += a1
	# print("return  a+1, b")
	return a+1, b


# def comb(i):
# 	# print("comb", i)
# 	layers = [[i], []]
# 	used[i] = True

# 	chet = 0
# 	nechet = 0
# 	is_chet = True
# 	cur_layer_ind = 0
# 	next_layer_ind = 1

# 	while len(layers[cur_layer_ind]) > 0:
# 		if is_chet:
# 			cur_layer_ind = 0
# 			next_layer_ind = 1
# 			chet += len(layers[cur_layer_ind])
# 		else:
# 			cur_layer_ind = 1
# 			next_layer_ind = 0
# 			nechet += len(layers[cur_layer_ind])
# 		is_chet = not is_chet
# 		# layers.append(cur_layer)
# 		layers[next_layer_ind] = []
# 		for item in layers[cur_layer_ind]:
# 			for child in graph[item]:
# 				if not used[child]:
# 					layers[next_layer_ind].append(child)
# 					used[child] = True
# 		# cur_layer = next_layer.copy()
# 	# including empty
# 	return 1*pow(2, chet, MODULO) + 1*pow(2, nechet, MODULO) -1


ans = 1
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i] = True
			ans *= 2
			ans %= MODULO
		else:
			a, b = dfs_chet_nechet(i)
			ans *= (1*pow(2, a, MODULO) + 1*pow(2, b, MODULO) -1)
			# ans *= comb(i)
			ans %= MODULO

# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def fraction(a, b):
    """a/b を既約分数 numer/denom として求める
    denom は必ず非負整数
    numer = denom = 0 のときは numer/denom = 0/0
    numer = 0 のときは numer/denom = 0/1
    denom = 0 のときは numer/denom = 1/0
    """
    numer, denom = a, b
    if numer == denom == 0:
        return 0, 0
    elif numer == 0:
        return 0, 1
    elif denom == 0:
        return 1, 0

    # GCD(a, b) を計算して約分する
    while b:
        a, b = b, a % b
    gcd_ab = a
    numer = numer // gcd_ab
    denom = denom // gcd_ab

    if denom < 0:  # denom は必ず非負整数
       numer, denom = -numer, -denom
    return numer, denom
  

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7

memo = defaultdict(int)
for i in range(n):
    a, b = info[i]
    memo[fraction(a, b)] += 1

cnt_00 = 0
cnt_n0 = 0 
cnt_d0 = 0
ans = 1
used = set()
for frac in memo:
    numer, denom = frac
    if numer == 0 and denom == 0:
        cnt_00 += memo[frac]
        continue
    if frac in used:
        continue
    if numer == 0 or denom == 0:
        cnt1 = memo[(0, 1)]
        cnt2 = memo[(1, 0)]
        tmp = pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
        ans *= tmp
        used.add((0, 1))
        used.add((1, 0))
        continue

    rev_num, rev_den = -denom, numer
    if rev_den < 0:
        rev_num, rev_den = -rev_num, -rev_den

    cnt1 = memo[frac]
    cnt2 = 0
    if (rev_num, rev_den) in memo:
        cnt2 = memo[(rev_num, rev_den)]
    tmp = pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    ans *= tmp
    ans %= MOD
    used.add((rev_num, rev_den))

ans = ans + cnt_00
print((ans - 1) % MOD)

Submission status: Runtime Error

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
gp = []
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a,b = map(int, input().split())
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b != 0:
        left_zero += 1
    elif a != 0 and b == 0:
        right_zero += 1
    elif a == 0 and b == 0:
        zero += 1
    else:
        dic[a/b] += 1
        gp.append((a, b))
done = defaultdict(bool)
ans = 1
for a,b in gp:
    k = a/b
    if done[k]: continue
    rk = -b/a
    done[k] = True
    done[rk] = True
    cnt1 = pow(2, dic[k], MOD)-1
    cnt2 = pow(2, dic[rk], MOD)-1
    c = cnt1+cnt2+1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans %= MOD
print(ans-1)

Submission status: Runtime Error

Solution code:
import collections
import fractions

P =1000000007

N = int(input())
ABs = []
for _ in range(N):
  a,b = map(int, input().split)
  if b == 0:
    ABs.append([1,0])
  elif b > 0:
    c = fractions.gcd(a,b)
    ABs.append([a//c, b//c])
  else:
    c = fractions.gcd(abs(a),abs(b))
    ABs.append([-a//c, -b//c])

print(ABs)

Submission status: Runtime Error

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

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

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

cnt = defaultdict(int)
zero = 0

tmp = []
for a, b in AB:
    gcd_ab = gcd(abs(a), abs(b))
    if a < 0: a,  b = - a, - b 
    tmp.append([a // gcd_ab, b // gcd_ab])
AB = tmp
#print(AB)

cnt = defaultdict(int)
zero = 0
        
for a, b in AB:
    if a * b == 0:
        zero += 1
    else:
        cnt[(a, b)] += 1
#print(cnt)

answer = 1
rest = N

answer *= zero + 1
answer %= MOD
rest -= zero

check = defaultdict(int)
for a, b in AB:
    if a > 0 and b > 0 and check[(a, b)] == 0:
        check[(a, b)] = 1
        #print((a, b), cnt[(a, b)], cnt[(b, -a)])
        answer *= pow(2, cnt[(a, b)] + cnt[(b, -a)], MOD) - (pow(2, cnt[(a, b)], MOD) - 1) * (pow(2, cnt[(b, -a)], MOD) - 1) 
        answer %= MOD
        rest -= cnt[(a, b)] + cnt[(b, -a)]

answer *= pow(2, rest, MOD)
answer -= 1
answer %= MOD

print(answer)

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
from math import gcd

mod = int(1e9+7)
n = ii()
cnd = {}
azero = 0
bzero = 0
allzero = 0
for _ in range(n):
    a,b = iim()
    if a == 0:
        if b != 0:
            azero += 1
        else:
            allzero += 1
    elif b == 0:
        bzero += 1            
    else:
        '''
        ratio = Fraction(a,b)
        before = cnd.get(ratio,False)
        if before:
            cnd[ratio] = [before[0]+1,before[1]]
        else:
            invratio = Fraction(-b,a)
            check = cnd.get(invratio,False)
            if check:
                cnd[invratio] = [check[0],check[1]+1]
            else:
                cnd[ratio] = [1,0]
        '''
        g = gcd(a,b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        cnd[(a,b)] += cnd.get((a,b),0)


noreg = 0
if azero == 0 or bzero == 0:
    noreg += max(azero,bzero)
else:
    ans = (2**azero%mod + 2**bzero%mod - 1)%mod

for k,item in cnd:
    a,b = k
    if b>0:
        m = cnd.get((-b,a),False)
        if m:
            ans *= (2**item%mod+2**m%mod-1)%mod
        else:
            noreg += item
    else:
        m = cnd.get((-b,a),False)
        if not m:
            noreg += item
#print('hoge')
print(int((ans*((2**noreg)%mod)-1+allzero)%mod))

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


def f(a, b):
    if a == 0 and b == 0:
        return 0, 0
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = -1
    elif b == 0 and a < 0:
        s = -1
    else:
        s = 1 if a * b >= 0 else -1
    if b == 0:
        a = 1
        s = 1
    a = abs(a)
    b = abs(b)
    return s, 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:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


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 -*-
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


def f(a, b):
    g = math.gcd(a, b)
    a //= g
    b //= g
    if a == 0 and b < 0:
        s = -1
    elif b == 0 and a < 0:
        s = -1
    else:
        s = 1 if a * b >= 0 else -1
    if b == 0:
        a = 1
        s = 1
    a = abs(a)
    b = abs(b)
    return s, 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:
        s, a, b = f(a, b)
        adb[(s*a, b)] += 1
    M = Mod(1000000007)
    ans = 1
    done = set()
    for k, v in adb.items():
        if k in done:
            continue
        if k == (0, 0):
            continue
        a, b = k
        if a < 0:
            s = 1
            a = abs(a)
        else:
            s = -1
        n = adb[(s*b, a)]
        done.add(k)
        done.add((s*b, a))
        t = M.sub(M.pow(2, v) + M.pow(2, n), 1)
        ans = M.mul(ans, t)

    return M.add(M.sub(ans, 1), adb[(0, 0)])


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:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
AB=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    if a and b:
        n=gcd(a,b)
        if a<0 and n>0:
            n*=-1
        AB[i][0]//=n
        AB[i][1]//=n
#print(AB)
data=defaultdict(int)
c=0
M=0
for i in range(N):
    a,b=AB[i]
    P=M
    if a==0 and b==0:
        continue
    elif a and b==0:
        P-=data[-a]
    elif a==0 and b:
        P-=data[-b*idle_max]
    else:
        P-=data[b*idle_max-a]
    #print(P)
    c+=pow(2,P,mod)
    c%=mod
    if data[a*idle_max+b]==0:
        M+=1
    data[a*idle_max+b]+=1
print(c)

Submission status: Runtime Error

Solution code:
N = int(input())
data = [list(map(int,input().split())) for i in range(N)]
mod = 10**9+7
ans = 0

from math import gcd

A = []

for i in range(N):
    if data[i][0] == 0 and data[i] == 0:  #(0,0)の場合は以降取り除いて考える
        ans += 1
    else:                                 #各々の成分をgcdで割り、第1成分が非負になるように調整
        if data[i][0] < 0:
            data[i][0] *= -1
            data[i][1] *= -1
        g = gcd(data[i][0],data[i][1])
        data[i][0] //= g
        data[i][1] //= g
        if data[i][0] == 0:
            A.append((0,1))
        elif data[i][1] > 0:
            A.append((data[i][0],data[i][1]))
        elif data[i][1] == 0:
            A.append((1,0))
        else:
            A.append((data[i][0],data[i][1]))


from collections import Counter

C = Counter(A)
D = []             #仲が悪いイワシの数の組

for i,j in list(C.keys()):
    if j <= 0:
        continue
    else:
        if j == 0:
            if C[(0,1)] > 0:
                D.append((C[(1,0)],C[(0,1)]))
        else:
            if C[(j,-i)] > 0:
                D.append((C[(i,j)],C[(j,-i)]))

r = 0  #仲が悪くなり得るイワシの数
for i,j in D:
    r += i+j

a = 1  #仲が悪くなり得るイワシたちの選び方
for i,j in D:
    a = (a*(pow(2,i,mod)+pow(2,j,mod)-1)) % mod

a = (a*pow(2,len(A)-r,mod)) % mod  #仲が悪くなり得ないイワシたちの選び方

ans += a-1  #全部選ばないものを除く

print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  if k>0:
   dic[Fraction(A,B)][0]+=1
  else:
   dic[Fraction(-B,A)][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Runtime Error

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
AB=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7
idle_max=10**19


for i in range(N):
    a,b=AB[i]
    n=gcd(a,b)
    if a<0 and n>0:
        n*=-1
    AB[i][0]//=n
    AB[i][1]//=n
#print(AB)
data=defaultdict(lambda:0)
c=0
M=0
for i in range(N):
    a,b=AB[i]
    P=M
    if a==0 and b==0:
        continue
    elif a and b==0:
        P-=data[-a]
    elif a==0 and b:
        P-=data[-b*idle_max]
    else:
        P-=data[b*idle_max-a]
    #print(P)
    c+=pow(2,P,mod)
    c%=mod
    if data[a*idle_max+b]==0:
        M+=1
    data[a*idle_max+b]+=1
print(c)