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: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

#通分
def f(a,b):
    f = math.gcd(a,b)
    return a//f, b//f

N = I()
A,B = LIR(N,2)

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


dplus = defaultdict(int)
dminus = defaultdict(int)
dminus2 = defaultdict(int)
zero = 0
for i in range(N):
    if A[i] == 0 or B[i] == 0:
        zero += 1
    else:
        if A[i]*B[i] > 0:
            a,b = f(abs(A[i]),abs(B[i]))
            dplus[(a,b)] += 1
        else:
            a,b = f(abs(A[i]),abs(B[i]))
            dminus[(b,a)] += 1
            dminus2[(b,a)] += 1

ans = 1
count = 0

for k in dplus.keys():
    if dminus[k]:
        temp = beki[dplus[k]] + beki[dminus[k]] - 1
        ans *= temp
        ans %= mod
    else:
        count += dplus[k]

for k in dminus2.keys():
    if dplus[k]:
        continue
    else:
        count += dminus[k]

ans *= beki[count]
temp = ans-1
temp2 = ans*zero
ans = temp+temp2
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        continue
    # if a==0:
    #     n_sign = 1
    #     a=0
    #     b=0
    # elif b==0:
    #     n_sign = 0
    #     a=0
    #     b=0  


    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        gcd = math.gcd(a,b)
        a//=gcd
        b//=gcd
        #print(n_sign,a,b)

    

    if n_sign==1:
        s =str(b)+'/'+str(a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a)+'/'+str(b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans %= MOD
print (ans)

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int


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

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

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

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


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

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

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

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

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

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

        if end2 == None:
            end2 = end

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

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

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

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

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

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

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

    # print(d)
    print(ans-1)

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

mod = 10 ** 9 + 7


def regularize(a, b):
    if a < 0 or (a == 0 and b < 0):
        a, b = -a, -b
    if b > 0:
        return 0, a, b
    else:
        return 1, -b, a


n = int(input())
edict = dict()
zero_num = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_num += 1
        continue
    abgcd = np.gcd(a, b)
    a, b = a // abgcd, b // abgcd
    index, a, b = regularize(a, b)
    key = (a, b)
    if key not in edict.keys():
        edict[key] = [0, 0]
    edict[key][index] += 1
if len(edict.keys()) == 0:
    not_zeros = 0
else:
    not_zeros = 1
    for key in edict.keys():
        a, b = key
        pp, pm = edict[key]
        not_zeros *= (pow(2, pp, mod) + pow(2, pm, mod) - 1) % mod
        not_zeros %= mod
print((zero_num + not_zeros - 1) % mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 10**9+7
n = int(input())
dicn = {}
dicp = {}
dicz = {'a': 0, 'b': 0}
for i in range(n):
  a, b = map(int, input().split())
  if a == 0 and b == 0:
    continue
  else:
    g = gcd(a,b)
    a //= g
    b //= g
    if a < 0:
      a *= -1
      b *= -1
    elif a == 0 and b < 0:
      b *= -1
    if a * b > 0:
      if a in dicp:
        if b in dicp[a]:
          dicp[a][b] += 1
        else:
          dicp[a][b] = 1
      else:
        dicp[a] = {b: 1}
    elif a * b < 0:
      if b in dicn:
        if a in dicn[b]:
          dicn[b][a] += 1
        else:
          dicn[b][a] = 1
      else:
        dicn[b] = {a: 1}
    else:
      if a == 0:
        dicz['a'] += 1
      else:
        dicz['b'] += 1

ans = 1

for a in dicp:
  for b in dicp[a]:
    if -a in dicn:
      if b in dicn[-a]:
        ans *= (pow(2, dicp[a][b], mod) + pow(2, dicn[-a][b], mod) - 1)
        dicn[-a][b] = 0
      else:
        ans *= pow(2, dicp[a][b], mod)
    else:
      ans *= pow(2, dicp[a][b], mod)
    ans %= mod

for b in dicn:
  for a in dicn[b]:
    ans *= pow(2, dicn[b][a], mod)
    ans %= mod
    
if dicz['a'] > 0 and dicz['b'] > 0:
  ans *= pow(2,dicz['a'],mod) + pow(2,dicz['b'],mod) - 1
elif dicz['a'] > 0:
  ans *= pow(2,dicz['a'],mod)
elif dicz['b'] > 0:
  ans *= pow(2,dicz['b'],mod)
    
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys

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

from math import gcd
from collections import defaultdict


n = readint()

mod = 1000000007

d = defaultdict(int)

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

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

print((ans+mod-1)%mod)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

MOD = 10 ** 9 + 7


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


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
MOD = 10**9 + 7


def pow_k(x, n):
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 or b==0:
        zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = []
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.append(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.append(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

ans *= (zero_cnt+1)
ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import math


def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


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

my_dict = dict()

ab_mod = []
for item in ab:
    a, b = item
    if a == 0 and b == 0:
        ab_mod.append((0, 0))
    elif a == 0:
        ab_mod.append((0, 1))
    elif b == 0:
        ab_mod.append((1, 0))
    else:
        gcd = math.gcd(abs(a), abs(b))
        if a < 0:
            a = -a
            b = -b
        ab_mod.append((a // gcd, b // gcd))

for item in ab_mod:
    if item not in my_dict:
        my_dict[item] = 1
    else:
        my_dict[item] += 1


if (0, 0) in my_dict:
    num_dame = my_dict.pop((0, 0))
else:
    num_dame = 0

num_total = n - num_dame
dame_tuple = []

for item in my_dict:
    a, b = item
    val1 = my_dict[item]
    if (b, -a) in my_dict:
        val2 = my_dict[(b, -a)]
        dame_tuple.append((val1, val2))
        num_total -= (val1 + val2)

ret = 1

ret *= modpow(2, num_total, 10 ** 9 + 7)


for item in dame_tuple:
    val1, val2 = item
    zenbu = modpow(2, val1 + val2, 10 ** 9 + 7)
    dame1 = modpow(2, val1, 10 ** 9 + 7) - 1
    dame2 = modpow(2, val2, 10 ** 9 + 7) - 1
    ret *= (zenbu - (dame1 * dame2))

ret -= 1

print(ret % (10 ** 9 + 7))

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0
	dx0 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			pass
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[a * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1

	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + b2]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans %= con

	print(ans - 1)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
n=int(input())
a=[]
for i in range(n):
  line=input().split(" ")
  a.append(line)
g=0
for i in range(n):
  for j in range(n):
      ai=int(a[i][0])
      bi=int(a[i][1])
      aj=int(a[j][0])
      bj=int(a[j][1])
      ki=(ai*aj)+(bi*bj)
      if ki==0:
        g=g+1

ans=2**(n-g)*3**(g/2)-1
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from math import gcd

def main():
    N = int(input())
    minus_iwashi = {}
    iwashi = {}
    a0 = 0
    b0 = 0
    a0b0 = 0
    
    for _ in range(N):
        a,b = map(int,input().split())
        if a < 0 and b > 0:
            a = -a
            b = -b
        elif a < 0 and b < 0:
            a = -a
            b = -b
        if a == 0 and b == 0:
            a0b0 += 1
            continue
        if a == 0 and b != 0:
            a0 += 1
            continue
        if b == 0 and a != 0:
            b0 += 1
            continue
        #print(a,b)
        if b < 0:
            a,b = -b,a
            #print('mini{}{}'.format(a,b))
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in minus_iwashi:
                minus_iwashi[(a,b)] += 1
            else:
                minus_iwashi[(a,b)] = 1
        elif b > 0:
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in iwashi:
                iwashi[(a,b)] += 1
            else:
                iwashi[(a,b)] = 1
    
    power = [1]
    for _ in range(N):
        power.append(power[-1]*2%MOD)
    '''
    print(power)
    print(iwashi)
    print(minus_iwashi)
    print(a0,b0)
    '''
    
    if a0 > 0 and b0 > 0:
        ans = power[a0] + power[b0] - 1
    elif a0 > 0:
        ans = power[a0]
    elif b0 > 0:
        ans = power[b0]
    else:
        ans = 1

    for k,v in iwashi.items():
        if k in minus_iwashi:
            ans *= (power[v] + power[minus_iwashi[k]] - 1)
            ans %= MOD
        else:
            ans *= power[v]
            ans %= MOD
    
    for k,v in minus_iwashi.items():
        if k in iwashi:
            continue
        else:
            ans *= power[v]
            ans %= MOD
    print(ans - 1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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


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

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

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

# print(slopeCount)

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

# print(reversedPairs, independentCount)

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

mod = 10**9 + 7


def modpow(a, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = ret * a % mod
        a = a * a % mod
        n >>= 1
    return ret


col = []
row = []
for a, b in A:
    if a == b == 0:
        continue
    if a == 0:
        b = 1
    elif b == 0:
        a = 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g

    if a < 0:
        a *= -1
        b *= -1

    if a >= 0 and b > 0:
        col.append((a, b))
    elif a > 0 and b < 0 or b == 0:
        row.append((-b, a))


C = Counter(col)
D = Counter(row)
S = set(col) | set(row)


ans = 1
for s in S:
    if s in C:
        if s in D:
            mul = modpow(2, C[s], mod) + modpow(2, D[s], mod) - 1
        else:
            mul = modpow(2, C[s], mod)
    elif s in D:
        mul = modpow(2, D[s], mod)

    ans *= mul
    ans %= mod

if len(S) > 1:
    ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

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

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

mod = 10 ** 9 + 7

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

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

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

ret *= zero + 1
ret %= mod

print((ret - 1) % mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
n=int(input())

iw=[]
for i in range(n):
    ab=list(map(int, input().split( )))
    iw.append(ab)

for i in range(n):
    ai,bi=iw[i]
    if ai and bi:##互いに素にする
        g=gcd(ai,bi)
        iw[i][0]//=g;iw[i][1]//=g
    else:#どちらか0なら残りを1か0にする
        if ai:#biがゼロでaiが非ゼロ
            iw[i][0]=1
        elif bi:#aiがゼロでbiが非ゼロ
            iw[i][1]=1
    if bi<0:#biは正に設定
        iw[i][0]*=-1;iw[i][1]*=-1
    if bi==0 and ai<0:#biがゼロならaiは正かゼロ
        iw[i][0]*=-1
iw = [tuple(iwi) for iwi in iw]
C=Counter(iw)
ans=1
mod=10**9+7
#print(C)
#ai bi=0,0は別に処理が要る
tmp=0
if (0,0) in C:
    tmp= C.pop((0,0))

if (0,1) in C and (1,0) in C:
    tmpx=C.pop((0,1))
    tmpy=C.pop((1,0))
    ans*=(pow(2,tmpx,mod)+pow(2,tmpy,mod)-1)
    #print("A")
    #print(ans)
elif (0,1) in C :
    tmpx=C.pop((0,1))
    ans*=pow(2,tmpx,mod)
    #print("B")
elif (1,0) in C :
    tmpx=C.pop((1,0))
    ans*=pow(2,tmpx,mod)
    #print("C")

for ai,bi in C:
    if C[(ai,bi)]<0:##集計済
        continue

    if ai>0:#ai>0
        if (-bi,ai) in C and C[(-bi,ai)]>0:
            ans*=(pow(2,C[(-bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(-bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    else:#ai<0
        if (bi,-ai) in C and C[(bi,-ai)]>0:
            ans*=(pow(2,C[(bi,-ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,-ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    #print((ai,bi),C[(ai,bi)],ans)
print((ans+tmp-1)%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
import random
n = int(input())
mod = 10**9 + 7
d1 = dict()
a_zero,b_zero = 0,0

# サンプル入力
#n = 2*10**5
#data = [[random.randint(-10**18,10**18),random.randint(-10**18,10**18)] for _ in range(n)]
for i in range(n):
    a,b = map(int, input().split())
    #a,b = data[i]
    if a == 0 and b == 0:
        continue
    if a == 0:
        a_zero += 1
        continue
    if b == 0:
        b_zero += 1
        continue
    a,b = a//gcd(a,b),b//gcd(a,b)
    if a < 0:
        a *= -1
        b *= -1

    if (a,b) in d1:
        d1[(a,b)] += 1
    else:
        d1[(a,b)] = 1

ans =  1
ans *= pow(2,a_zero,mod)+pow(2,b_zero,mod)-1
ans %= mod
for a,b in d1:
    if b > 0 and (b,-a) in d1:
        ans *= pow(2,d1[(a,b)],mod)+pow(2,d1[(b,-a)],mod)-1
        d1[(a,b)] = 0
        d1[(b,-a)] = 0
    elif b < 0 and (-b,a) in d1:
        ans *= pow(2,d1[(a,b)],mod)+pow(2,d1[(-b,a)],mod)-1
        d1[(a,b)] = 0
        d1[(-b,a)] = 0
    else:
        ans *= pow(2,d1[(a,b)],mod)
        d1[(a,b)] = 0
    ans %= mod
    #print(a,b,d1)
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
MOD = 10**9+7
MAX = 2*(10**5)+1
sqr = [1 for _ in range(MAX)]
for i in range(1, MAX):
    sqr[i] = sqr[i-1] * 2
    sqr[i] %= MOD

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)

n = int(input())
d = defaultdict(lambda: 0)
ans = 1
flt = FLT()
cnt_0 = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        cnt_0 += 1
        continue

    key1 = format(- b / a, '.14f').rstrip('0').rstrip('.') if a != 0 else "b_0"
    cnt = d[key1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    if a == 0:
        d["0"] += 1
    elif b == 0:
        d["b_0"] += 1
    else:
        key2 = format(a / b, '.14f').rstrip('0').rstrip('.')
        d[key2] += 1
# print(d)
print(ans-1+cnt_0)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=10**9+7

n=int(input())

dp=defaultdict(int)
dm=defaultdict(int)
z=0
ans=0
cp=[]
cm=[]
az=0
bz=0
cz=0
for i in range(n):
    a,b=map(int,input().split())
    if a*b>0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        pp=(abs(b)*pow(abs(a),mod-2,mod))%mod
        if dp[p]==0:
            cp.append([p,pp])
        dp[p]+=1
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        dm[p]+=1
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1

kk=pow(2,az,mod)+pow(2,bz,mod)+cz-2
if kk>0:
    ans=kk
else:
    ans=1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    ans%=mod
    z-=(dp[a]+dm[b])
# print(z)
ans*=pow(2,z,mod)

if kk>0:
    ans+=1

print((ans-1)%mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def xy(x,y):
  x,y=abs(x),abs(y)
  g=gcd(x,y)
  x//=g
  y//=g
  return (10**20)*x+y
from collections import defaultdict
mod=10**9+7
n=int(input())
aabb=[list(map(int,input().split()))for _ in range(n)]
ab=[]
ans=0
for i in aabb:
  if i!=[0,0]:ab.append(i)
  else:
    n-=1
    ans+=1
az=bz=0
d=defaultdict(int)
dd=defaultdict(int)
for i in ab:
  if 0 in i:
    if i[0]==0:az+=1
    else:bz+=1
  else:
    a,b=i
    if a*b>0:d[xy(a,b)]+=1
    else:dd[xy(a,b)]+=1
ans+=pow(2,n,mod)-1
t=[]
tt=1
for i in dd:
  b,a=divmod(i,10**20)
  p,m=d[xy(a,b)],dd[i]
  if p*m:
    t.append((p,m))
    n-=p+m
    tt*=(p+m+1)
    tt%=mod
if az*bz:
  t.append((az,bz))
  n-=az+bz
  tt*=(az+bz+1)
  tt%=mod
for p,m in t:
  ttt=tt*pow(p+m+1,mod-2,mod)%mod
  ans-=pow(2,n,mod)*ttt*(pow(2,p,mod)-1)*(pow(2,m,mod)-1)%mod
  if len(t)!=1:ans-=pow(2,n,mod)*(pow(2,p,mod)-1)*(pow(2,m,mod)-1)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
from collections import defaultdict

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

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

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

    arg = defaultdict(int)
    zero = 0

if __name__ == '__main__':
    main()