Problem:


Score: 500 points

Problem Statement

We have caught N sardines. The deliciousness and fragrantness of the i-th sardine is A_i and B_i, respectively.

We will choose one or more of these sardines and put them into a cooler. However, two sardines on bad terms cannot be chosen at the same time.

The i-th and j-th sardines (i \neq j) are on bad terms if and only if A_i \cdot A_j + B_i \cdot B_j = 0.

In how many ways can we choose the set of sardines to put into the cooler? Since the count can be enormous, print it modulo 1000000007.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

-10^{18} \leq A_i, B_i \leq 10^{18}

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_N B_N

Output

Print the count modulo 1000000007.

Sample Input 1

3
1 2
-1 1
2 -1

Sample Output 1

5

There are five ways to choose the set of sardines, as follows:

The 1-st

The 1-st and 2-nd

The 2-nd

The 2-nd and 3-rd

The 3-rd

Sample Input 2

10
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4

Sample Output 2

479



Sample input:
3
1 2
-1 1
2 -1


Sample output:
5

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin, gcd
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 1000000007

n = I()
D = defaultdict(int)
D2 = defaultdict(int)
A = []
B = []
F = []
ans = 1
for i in range(n):
    a, b = LI()
    flg = 0
    if a * b < 0:
        flg = 1
    a = abs(a)
    b = abs(b)
    g = gcd(a, b)
    a //= g
    b //= g
    A += [a]
    B += [b]
    F += [flg]
    D[(flg, a, b)] += 1

visited = defaultdict(int)
for j in range(n):
    fi, ai, bi = F[j], A[j], B[j]
    if visited[(fi, ai, bi)]:
        continue
    visited[(fi, ai, bi)] = 1
    visited[(fi ^ 1, bi, ai)] = 1
    ans = ans * (pow(2, D[(fi, ai, bi)], mod) + pow(2, D[(fi ^ 1, bi, ai)], mod) - 1) % mod

print(ans - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 1000000007

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

n = I()
D = defaultdict(int)
D2 = defaultdict(int)
A = []
B = []
F = []
ans = 1
for i in range(n):
    a, b = LI()
    flg = 0
    if a * b < 0:
        flg = 1
    a = abs(a)
    b = abs(b)
    g = gcd(a, b)
    a //= g
    b //= g
    A += [a]
    B += [b]
    F += [flg]
    D[(flg, a, b)] += 1

visited = defaultdict(int)
for j in range(n):
    fi, ai, bi = F[j], A[j], B[j]
    if visited[(fi, ai, bi)]:
        continue
    visited[(fi, ai, bi)] = 1
    visited[(fi ^ 1, bi, ai)] = 1
    ans = ans * (pow(2, D[(fi, ai, bi)], mod) + pow(2, D[(fi ^ 1, bi, ai)], mod) - 1) % mod

print(ans - 1)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter

mod = 10**9+7
n = int(input())
c = Counter()
cc = Counter()

for _ in range(n):
    a, b = map(int, input().split())
    a, b = a//math.gcd(a, b), b//math.gcd(a, b)
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        c[-1] += 1
        continue

    key = a*(10**19)+b
    c[key] += 1
    cc[key] += 1

l = []

for r in cc.keys():
    if r == -1:
        continue
    ra = c[r]
    
    a, b = r//(10**19), r % (10**19)
    if a >= 0:
        r_inv = (-b)*10**19 + a
    else:
        r_inv = b*(10**19) - a
    rb = c[r_inv]

    if ra >= 0 and rb >= 0:
        l.append([ra, rb])
        c[r] -= 10**9
        c[r_inv] -= 10**9

ans = 1
for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1
    ans %= mod

ans = (ans-1) + c[-1]
ans %= mod

print(ans)

Submission status: Runtime Error

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

mod = 10**9+7

N = int(input())
As = {}
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    x, y = x//g, y//g
    if x != 0 or y != 0:
        if y < 0 or (y==0 and x < 0):
            y = -y
            x = -x
        if (x, y) in As:
            As[(x, y)] += 1
        else:
            As[(x, y)] = 1

ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        if x > 0:
            ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
n = int(readline())
#dic1
#[正負,比率1(小),比率2(大)]
for i in range(n):
    a,b= map(int,readline().split())
    plamai = 1 if a*b > 0 else 0
    if a < 0:a = -a
    if b < 0:b = -b
    res = gcd(a,b)
    if res == 0:
        zero += 1
        continue
    dic1[str(plamai)+" "+str(a//res)+" "+str(b//res)] += 1

ans = 1
dic2 = dict()
for i in dic1.keys():
    res = 0
    if not i in dic2:
        a = dic1[i]
        g,d,e = i.split()
        if g == "1":
            res2 = "0"+" "+e+" "+d
        else:
            res2 = "1"+" "+e+" "+d
        if res2 in dic1:
            b = dic1[res2]
        else:b = 0
        if a > 0:
            res += pow(2,a)
        if b > 0:
            res += pow(2,b)
        if a != 0 and b != 0:
            res -= 1
        ans *= res
        ans %= mod
        dic2[res2] = 1
if not zero:
    print(ans-1)
else:
    print(ans+pow(2,zero)-2)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod = 1000000007

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

n = I()
D = defaultdict(int)
D2 = defaultdict(int)
A = []
B = []
ans = 1
for i in range(n):
    a, b = LI()
    if a < 0 and b < 0:
        a = -a
        b = -b
    g = gcd(abs(a), abs(b))
    a //= g
    b //= g
    if a < 0 or b < 0:
        a = -abs(a)
        b = abs(b)
    A += [a]
    B += [b]
    D[(a, b)] += 1

visited = defaultdict(int)
for j in range(n):
    ai, bi = A[j], B[j]
    if visited[(ai, bi)]:
        continue
    visited[(ai, bi)] = 1
    if ai < 0 and D[(bi, -ai)]:
        ans = ans * (pow(2, D[(ai, bi)], mod) + pow(2, D[(bi, -ai)], mod) - 1) % mod
        visited[(bi, -ai)] = 1
    elif ai > 0 and D[(-bi, ai)]:
        ans = ans * (pow(2, D[(ai, bi)], mod) + pow(2, D[(-bi, ai)], mod) - 1) % mod
        visited[(-bi, ai)] = 1
    else:
        ans = ans * 2 % mod

print(ans - 1)

Submission status: Runtime Error

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

mod = 10**9+7

N = int(input())
As = {}
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    g = math.gcd(x, y)
    x, y = x//g, y//g
    if x == 0 and y == 0:
        Empty += 1
    else:
        if y < 0 or (y==0 and x < 0):
            y = -y
        if (x, y) in As:
            As[(x, y)] += 1
        else:
            As[(x, y)] = 1

M = N - Empty
ans = 1
for (x, y), num in As.items():
    if (-y, x) in As:
        if x > 0:
            ans = (ans * (pow(2, num, mod) + pow(2, As[(-y, x)], mod) - 1)) % mod
    elif not (y, -x) in As:
        ans = (ans * pow(2, num, mod)) % mod

print((ans-1)%mod)

Submission status: Runtime Error

Solution code:
from fractions import Fraction
N, = map(int, input().split())
d = dict()
X = []
cc = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b==0:
        cc += 1
        continue
    f = Fraction(a, b)
    if f not in d:
        d[f] = 0
    d[f] += 1
    X.append((a, b))

vs = dict()
cs = []
for a, b in X:
    f1 = Fraction(a, b)
    f2 = Fraction(b, -a)
    if f2 not in d:
        d[f2] = 0
#        cs.append(d[f1])
#        continue
    if f1 in vs or f2 in vs:
        continue
    vs[f1] = (d[f1], d[f2])
mod = 10**9+7

tmp = []
r = 1
#print(pow(2, sum(cs),mod))
r2 = 1
for k in vs:
    a, b = vs[k]
#    print((pow(2, a, mod), pow(2, b, mod)))
    r = r * (pow(2, a, mod) + pow(2, b, mod)-1) % mod
#    r2 = r2 * (pow(2, a-1, mod) + pow(2, b-1, mod)+2) % mod

print(r-1+cc)
#print(len(vs))
#print(r2)
#print(r2*pow(2, sum(cs),mod)+1)

Submission status: Runtime Error

Solution code:
from collections import deque

import numpy as np

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

ans = []

for i in range(N):
    if P[i][0]==P[i][1] and P[1][0]==0:
        del P[i]


Pmat = np.matrix(P).astype("int64")


badmat = Pmat@Pmat.T
badmat = np.where(badmat == 0)

graph = [deque([]) for _ in range(N)]
for i in range(N):
    graph[i].extend(badmat[1][badmat[0] == i])

visit = [-1] * (N)

# 深さ優先探索


def dfs(v):
    s = 1
    stack = [v]
    visit[v] = 1
    while stack:
        v = stack[-1]
        if graph[v]:
            w = graph[v].popleft()
            if visit[w] == -1:
                visit[w] = 1
                s += 1
                stack.append(w)
        else:
            stack.pop()
    return s



# 孤立している頂点対策
for i in range(N):
    if visit[i] == -1:
        ans.append(dfs(i))


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

kotae = 0
for a in ans:
    kotae += power_func(2, a, 1000000007)
    kotae = kotae % 1000000007
print(kotae - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import reduce
n=int(input())
inf=float('inf')
def lean():
  a,b=map(int,input().split())
  if b==0:
    return inf
  return a/b
leans=sorted([lean() for _ in range(n)])
lean_c=defaultdict(int)
def inv(k):
  if k==0:
    return inf
  if k==inf:
    return 0
  return -1/k
for l in leans:
  lean_c[l]+=1
  lean_c[inv(l)]+=0
neuts=sum(lean_c[l] for l in lean_c if lean_c[inv(l)]==0)
posnegs=[[lean_c[l],lean_c[inv(l)]] for l in lean_c
         if l>0 and lean_c[l]>0 and lean_c[inv(l)]>0]
const=1000000007
def count_posneg(posneg):
  pos,neg=posneg
  return 2**pos%const+2**neg%const-1
print(2**neuts%const*
      reduce(lambda x,y:x*y,(count_posneg(posneg) for posneg in posnegs))
      %const-1)

Submission status: Runtime Error

Solution code:
def main():
    import math
    import collections
    N = int(input())

    mod = 10**9+7
    AB = [tuple(map(int, input().split())) for i in range(N)]

    d = collections.defaultdict(set)
    i = 0
    for a, b in AB:
        g = math.gcd(a, b)
        a = a // g
        b = b // g
        # d[(a, b)] += 1

        d[(a, b)].add(i)
        i += 1

    ans = 0
    r = set()

    dd = [1]
    for i in range(1, N+1):
        dd.append(dd[i-1]*2 % mod)

    r = set()
    ans = 1
    for a, b in d:
        if (a, b) in r:
            continue
        l1 = len(d[(a, b)])
        s = set()
        if (-b, a) in d:
            s |= d[(-b, a)]
        if (b, -a) in d:
            s |= d[(b, -a)]
        l2 = len(s)
        if l2:
            ans *= dd[l1] + dd[l2] - 1
            N -= l1 + l2
            ans %= mod
            r.add((-b, a))
            r.add((b, -a))
        else:
            continue
    if N:
        ans *= dd[N]
    ans -= 1

    print(ans % mod)


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = [],[]
    for i in range(n):
        a,b = map(int, input().split())
        if b == 0:
            C_n.append(0)
        elif a/b < 0:
            C_n.append(a/b)
        else:
            C_p.append(a/b)
    import numpy as np
    from collections import Counter as cc
    C_p,C_n = cc(C_p),cc(C_n)
    count= 0
    re = 1
    for c in C_p:
        if c == 0:
            re *= (2**C_n[-1/c] + 2**C_p[c] -1)%mod
            count += C_p[c]+C_n[c]
            continue

        if -1/c in C_n:
            count += C_n[-1/c] + C_p[c]
            re *= (2**C_n[-1/c] + 2**C_p[c] -1)%mod
    ans = pow(2,n-count,mod)*re%mod -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 1000000007
s, AB0, A0, B0 = {}, 0, 0, 0

for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        AB0 += 1
    elif A == 0:
        A0 += 1
    elif B == 0:
        B0 += 1
    else:
        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 key in s.keys():
        v2 = s.pop(key)
        Cv1, Cv2 = pow(2, v1, MOD), pow(2, v2, MOD)     # pow(2, n, MOD) は二項定理による組み合わせの総和
        C = ((Cv1 + Cv2) % MOD + (MOD - 1)) % MOD
        ans = (ans * C) % MOD
    else:
        f += v1

if A0 == 0 or B0 == 0:
    f += A0 + B0
else:
    Cv1, Cv2 = pow(2, A0, MOD), pow(2, B0, MOD)     # pow(2, n, MOD) は二項定理による組み合わせの総和
    C = ((Cv1 + Cv2) % MOD + (MOD - 1)) % MOD
    ans = (ans * C) % MOD

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

Submission status: Runtime Error

Solution code:
N = int(input())
data = []
for _ in range(N):
  data.append([int(v) for v in input().split(" ")])

count = 0

def check_ab(bit, j):
  if len(bit) == 0:
    return True
  
  for i in range(len(bit)):
    if bit[i] == 0:
      continue
    if data[i][0] * data[j][0] + data[i][1] * data[j][1] == 0:
      return False
    
  return True

def dfs(bit):
  global count
  if (len(bit) == N):
    if sum(bit) > 0:
      count = (count + 1) % 1000000007
    return
  
  else:
    c = 0
    bit.append(c)
    dfs(bit)
    bit.pop()
    
    c = 1
    if check_ab(bit, len(bit)):
      bit.append(c)
      dfs(bit)
      bit.pop()
        
dfs([])
print(count)

Submission status: Runtime Error

Solution code:
from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else b == 0:
            b_0 += 1
        continue
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)

Submission status: Runtime Error

Solution code:

from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
        elif a == 0:
            a_0 += 1
        else b == 0:
            b_0 += 1
        continue
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a_0 + b_0
    lst.append([a_0, b_0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from collections import defaultdict

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def mk(a,b):
	c = -1 if a < 0 else 1
	r = math.gcd(abs(a),abs(b))
	ra = (a //r)*c
	rb = (b //r)*c
	
	return ra, rb
	
def mh(a,b):
	return str(a)+'_'+str(b)
	
def mv(s):
	a,b = map(int, s.split('_'))
	return a,b
	
def ty(s):
	a, b = mv(s)
	sign = 1 if b > 0 else -1
	return mh(b*sign, -a*sign)
	


def main():
	n = int(input())
	dd = defaultdict(lambda : 0)
	for _ in range(n):
		a,b=tin()
		a,b = mk(a,b)
		dd[mh(a,b)] += 1
		
	cc = set()
	ret = 1
	for k in dd:
		if k in cc:
			continue
		v = dd[k]
		if ty(k) in dd:
			tv = dd[ty(k)]
			r = pow(2,v,mod)+pow(2,tv,mod)-1
			#pa((r,k, ty(k)))
			ret *= r
			ret %= mod
			cc.add(ty(k))
		else:
			#pa(('v',v,k, ty(k)))
			ret *= pow(2,v,mod)
			ret %= mod
	ret -= 1
	ret %= mod
	print(ret) 
		
			
		
		
	#b , c = tin()
	#s = input()
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Runtime Error

Solution code:
N=int(input())
dic={}
dic={}
for i in range(0,N):
    A,B=input().split(" ")
    A=int(A)
    B=int(B)
    if A/B in dic:
        dic[A/B]+=1
    else:
        dic[A/B]=1
sum=1
for items in dic:
    if dic[items]>0:
        if -1/items in dic:
            sum=sum*(pow(2, dic[items]) + pow(2, dic[-1 / items])-1 )
            dic[items]=0
            dic[-1 / items]=0
        else:
            sum=sum*(pow(2, dic[items]))
print((sum-1)%1000000007)

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

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

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

# print("a_b", a_b)
# print("m_b_a", m_b_a)

graph = [[] for _ in range(n)]
# rep_size = {}
value_indices = {} # a_b values
# value_size = {} # a_b values
for i in range(n):
	if m_b_a[i] in value_indices:
		for j in value_indices[m_b_a[i]]:
			graph[i].append(j)
			graph[j].append(i)
		# rep_size[rep] += value_size[m_b_a[i]]
		# rep_size[i] = 1
	value_indices[a_b[i]] = value_indices.get(a_b[i], []) + [i]
	 # = value_rep.get(a_b[i], i)
	# value_size[a_b[i]] = value_size.get(a_b[i], 0) + 1

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

def comb(i):
	layers = []
	cur_layer = [i]
	next_layer = []
	used[i] = True
	while len(cur_layer) > 0:
		layers.append(cur_layer)
		next_layer = []
		for item in cur_layer:
			for child in graph[item]:
				if not used[child]:
					next_layer.append(child)
					used[child] = True
		cur_layer = next_layer.copy()
	# print(layers)
	chet = 0
	nechet = 0
	for i in range(len(layers)):
		if i % 2 == 0:
			chet += len(layers[i])
		else:
			nechet += len(layers[i])
	return pow(2, chet, MODULO) + pow(2, nechet, MODULO) -1
	# return 1


ans = 1
used = [False for _ in range(n)]
for i in range(n):
	if not used[i]:
		if len(graph[i]) == 0:
			used[i]
			ans *= 2
			ans %= MODULO
		else:
			ans *= comb(i)
			ans %= MODULO
print(ans-1)

Submission status: Runtime Error

Solution code:
import math
mod = 1000000007
d = {}
X = []
zero = 0
N = int(input())
for i in range(N):
    a,b = map(int,input().split())
    if a,b = 0,0:
        zero += 1
        continue
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        b = 1
    else:
        g = math.gcd(a,b)
        a = a//g
        b = b//g
    c = b
    d = a
    if c < 0:
        c = -c
        d = -d    
        if (a,b) in X:
            d[(a,b)] += 1
        else:
            d[(a,b)] = 1
            d[(c,d)] = 0
            (a,b).append(X)
n = N
a = []
for (a,b) in X:
    c = b
    d = a
    if c < 0:
        c = -c
        d = -d
    x = d[(a,b)]
    y = d[(c,d)]
    if y > 0:
        a.append([x,y])
        n = n - x - y - zero
ans = 1
for x,y in a:
    z = (2**x + 2**y)%mod
    ans *= z
    ans % mod
ans += zero
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
MOD = 10**9+7
AB = []
x = 0
y = 0
d = defaultdict(int)
ch = defaultdict(int)
flag = 0
for _ in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        flag = 1
        continue
    elif a == 0:
        x += 1
        continue
    elif b == 0:
        y += 1
        continue
    else:
        d = math.gcd(abs(a),abs(b))
        a /= d
        b /= d
        c = a / b
        d[c] += 1
        AB.append(c)
n = len(AB)
ans = 1
for i in range(n):
    cc = AB[i]
    if ch[cc] != 0:
        continue
    m = d[cc]
    ccc = (-1)/cc
    l = d[ccc]
    ans *= (pow(2,m,MOD)+pow(2,l,MOD)-1)
    print(ans)
    ch[cc] = 1
    ch[ccc] = 1
ans *= (pow(2,x,MOD)+pow(2,y,MOD)-1)
if flag == 0:
    ans -= 1
ans = ans % MOD
print(ans)

Submission status: Runtime Error

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

from fractions import Fraction

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

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

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    C = []
    for i in range(n):
        a,b = map(int, input().split())
        if b == 0:
            C.append(0)
        C.append(a/b)
    import numpy as np
    C = np.array(C)
    C_p = C[C>=0]
    C_n = C[C<0]
    from collections import Counter as cc
    C_p,C_n = cc(C_p),cc(C_n)
    count= 0
    re = 1
    for c in C_p:
        if c == 0:
            re *= C_p[c]
            count += C_p[c]
            continue
        
        if -1/c in C_n:
            count += C_n[-1/c] + C_p[c]
            re *= (2**C_n[-1/c] + 2**C_p[c] -1)%mod
    ans = pow(2,n-count,mod)*re%mod -1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from math import gcd

N = int(input())
MOD = 1000000007
d = defaultdict(int)
pow2 = [1]
for i in  range(N):
  pow2.append(pow2[-1] * 2 % MOD)

def to_idx(a, b):
  return tuple(sorted(((a, b), (-a, -b))))

ans = 0
for i in range(N):
  a, b = map(int, input().split())
  g = gcd(a, b)
  a //= g; b //= g
  d[to_idx(a, b)] += 1

memo = []
key_set = set(d.keys())
while key_set:
  k = key_set.pop()
  v1, v2 = k
  a, b = v1
  idx = to_idx(-b, a)
  memo.append((pow2[d[k]] + pow2[d[idx]] - 1) % MOD)
  key_set.discard(idx)

ans = 1
for m in memo:
  ans *= m
  ans %= MOD

print((ans - 1) % MOD)

Submission status: Runtime Error

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

  return K * x # 指数を割り続け n が 1 に至ったら終了
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: 0)
dica=defaultdict(lambda: 0)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   x=Fraction(A,B)
   if x>0:
    if x in dic:
     dic[x]+=1
    else:
     dic[x]=1
   else:
    if x in dic:
     dica[x]+=1
    else:
     dica[x]=1
ans=1
for k in dic:
 ans*=(powmod(2,dic[k],mod)+powmod(2,dica.pop(-1/k),mod) -1)
 ans%=mod
for k in dica:
 ans*=powmod(2,dica[k],mod)
 ans%=mod
ans*=(powmod(2,c,mod)+powmod(2,d,mod)-1)
print((ans-1+e)%mod)

Submission status: Runtime Error

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

def gcd(x, y):
    if x < y:
        x = x ^ y
        y = x ^ y
        x = x ^ y
    div = x % y
    while div != 0:
        x = y
        y = div
        div = x % y
    return y


N=II()
MP1={}
A0 = 0
B0 = 0
AB0 = 0
RES=1
for i in range(N):
    A, B = LI()
    G = gcd(abs(A),abs(B))
    A //= G
    B //= G
    if A*B != 0:
        v = (abs(A), abs(B), A*B > 0)
        if not v in MP1:
            MP1[v] = 1
        else:
            MP1[v] += 1

    if A == 0 and B != 0: A0 += 1
    if A != 0 and B == 0: B0 += 1

# print(MP1)

VIS = set()
for (vv, n) in MP1.items():
    # print(vv, n)
    (A, B, isPos) = vv
    v = (B, A, not isPos)
    if not v in VIS and not vv in VIS:
        VIS.add(v)
        VIS.add(vv)
        if v in MP1:
            m = MP1[v]
            RES = (RES*POW(2, n))%DVSR + (RES*POW(2, m))%DVSR - RES
            RES %= DVSR
        else:
            RES *= POW(2, n)
            RES %= DVSR
    # print(RES)

if A0 and B0:
    RES = (RES*POW(2, A0))%DVSR + (RES*POW(2, B0))%DVSR
elif A0:
    RES = RES*POW(2, A0)%DVSR
elif B0:
    RES = RES*POW(2, B0)%DVSR

print(RES-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
mod = 10**9+7
def pow(n,p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
n = int(readline())
#dic1
#[正負,比率1(小),比率2(大)]
for i in range(n):
    a,b= map(int,readline().split())
    plamai = 1 if a*b > 0 else 0
    if a < 0:a = -a
    if b < 0:b = -b
    res = gcd(a,b)
    
    dic1[str(plamai)+" "+str(a//res)+" "+str(b//res)] += 1

ans = 1
dic2 = dict()
for i in dic1.keys():
    res = 0
    if not i in dic2:
        a = dic1[i]
        g,d,e = i.split()
        if g == "1":
            res2 = "0"+" "+e+" "+d
        else:
            res2 = "1"+" "+e+" "+d
        if res2 in dic1:
            b = dic1[res2]
        else:b = 0
        if a > 0:
            res += pow(2,a)
        if b > 0:
            res += pow(2,b)
        if a != 0 and b != 0:
            res -= 1
        ans *= res
        ans %= mod
        dic2[res2] = 1

print(ans-1)