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
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,gcd #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))



def main():
    N=I()
    A,B=[],[]
    for i in range(N):
        a,b = MI()
        A.append(a)
        B.append(b)
    both_zero_cnt = 0
    num_of_group = defaultdict(int) ##既約分数にしてあげて、(分子,分母)がkeyで、負なら分子が負になる他は正
    for i in range(N):
        a,b = A[i], B[i]
        if(a==b==0):
            both_zero_cnt+=1
            continue
        elif(a==0):
            num_of_group[-inf,inf] += 1
        elif(b==0):
            num_of_group[inf,inf] += 1
        else:
            if(a*b<0):
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(-b,a)] += 1
                num_of_group[(b,a)] += 0
            else:
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(a,b)] += 1
    # print(num_of_group.items())
    if(both_zero_cnt==N):
        print(N)
        return
    ##solve
    ans = 1
    two_pow = [1]
    for i in range(N):
        two_pow.append((2*two_pow[-1])%mod)
    # print(two_pow,"#######")
    for (a,b),cnt1 in num_of_group.items():
        if(a<0):
            continue
        tmp = two_pow[cnt1]
        # print((a,b),cnt1)
        # print(tmp)

        if (-a,b) in num_of_group:
            cnt2 = num_of_group[-a,b]
            tmp += two_pow[cnt2]
            tmp-=1
        if(tmp):
            ans *= tmp
    ans -= 1 ##全部選ばない
    ans += both_zero_cnt
    print(ans)
if __name__ == '__main__':
    main()

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
for a, b in counts.values():
    total = (total * (pow(2, a, MOD) + pow(2, b, MOD) - 1)) % MOD
print((total + MOD - 1) % MOD)

Submission status: 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      
    
#print (d_m,d_p)

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:
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
    elif a == 0 or b == 0:
        ans *= 2
        continue
    tmp1 = format(- b / a, '.14f').rstrip('0').rstrip('.')
    cnt = d[tmp1]
    if cnt <= 0:
        ans *= 2
    else:
        ans *= flt.inv(sqr[cnt])
        ans *= (sqr[cnt] + 1)
    ans %= MOD
    tmp2 = format(a / b, '.14f').rstrip('0').rstrip('.')
    d[tmp2] += 1
# print(d)
print(ans-1+cnt_0)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
import os
from collections import Counter

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

zeros_cnt = 0
A = []
B = []
for a, b in AB:
    if a == 0 or b == 0:
        zeros_cnt += 1
    else:
        A.append(a)
        B.append(b)

ab = [Fraction(a, b) for a, b in zip(A, B)]
ba = [Fraction(b, a) for a, b in zip(A, B)]

counts = Counter(ba)
ans = 1
nandemo = 0
for f, cnt in Counter(ab).items():
    if counts[-f] == 0:
        nandemo += cnt
    else:
        if f > 0:
            ans *= pow(2, cnt, MOD) + pow(2, counts[-f], MOD) - 1
            ans %= MOD
ans = ans * pow(2, nandemo, MOD) - 1
ans *= zeros_cnt + 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())
mod=10**9+7
pow2=[1]
for i in range(n+10):
    pow2.append(pow2[-1]*2%mod)

P=[] #[比較する数,正負の場合分け]
Q=[]
zero=0
for i in range(n):
    a,b=map(int,input().split())
    if a*b==0:
        zero+=1
    elif a*b>0:
        P.append([a/b,0])
    else:
        P.append([-b/a,1])
P.sort()
#print(P)
if not P:
    print(zero)
    sys.exit()

now=P[0][0]
cnt0=0
cnt1=0
d=n
ans=1
for p in P:
    if now!=p[0]:
        if cnt0*cnt1>0:
            d-=cnt0+cnt1
            ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod
            #print(cnt0,cnt1,d,ans)
        cnt0=0
        cnt1=0
    now=p[0]
    if p[1]==0:
        cnt0+=1
    else:
        cnt1+=1
if cnt0*cnt1>0:
    d-=cnt0+cnt1
    ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod

if zero>1:
    d-=zero
    ans=ans*(zero+1)%mod
ans=ans*pow2[d]%mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
from math import gcd
input = sys.stdin.readline
n = int(input())
fish = dict()
zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        if b == 0:
            zero += 1
            continue
        else:
            b = -1
    elif b == 0:
        a = 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0 and b < 0:
            a = -a
            b = -b
        elif b < 0:
            a = -a
            b = -b

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

ans = 1
pair = []
mod = 10**9+7
while fish:
    key, value = fish.popitem()
    a, b = key
    if a < 0:
        if (b, -a) in fish:
            pair.append((value, fish[(b, -a)]))
            fish.pop((b, -a))
        else:
            ans *= pow(2, value, mod)

    else:
        if (-b, a) in fish:
            pair.append((value, fish[(-b, a)]))
            fish.pop((-b, a))
        else:
            ans *= pow(2, value, mod)

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


print(ans+zero-1)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction



a = int(input())
resab = dict()
resba = dict()
res0 = 0

for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        s = Fraction(ai, bi)
        if s not in resab:
            resab[s] = 1
        else:
            resab[s] += 1
        b = Fraction(-s.denominator, s.numerator)
        if b not in resba:
            resba[b] = 1
        else:
            resba[b] += 1
    else:
        res0 += 1

ans = 1
for i in list(resab.keys()):
    if i in resba and i in resab:
        ans *= (2**resab[i] - 1 + 2**resba[i]) 
        #print(ans, i)
        del resab[i]
        del resab[Fraction(-i.denominator, i.numerator)]
        del resba[i]
        del resba[Fraction(-i.denominator, i.numerator)]
    elif i in resba:
        ans *= resba[i] + 1
        del resba[i]
        try:
            del resab[Fraction(-i.denominator, i.numerator)]
        except:
            pass
    elif i in resab:
        ans *= resab[i] + 1
        del resab[i]
        try:
            del resba[Fraction(-i.denominator, i.numerator)]
        except:
            pass
        
    ans %= 1000000007

if res0 == a:
    print(0)
else:
    ans *= (res0 + 1)
    ans -= 1
    ans %= 1000000007
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
arr = set()
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        ct[a/b] += 1
        arr.add((a, b))
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in arr:
    v = a/b
    if v in visited:
        continue
    inv = -b/a
    visited.add(v)
    visited.add(inv)
    tmp = pow(2, ct[v], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
A = []
d = {}
for i in range(N):
	a,b = map(int,input().split())
	g = math.gcd(a,b)
	if a < 0:
		a *= -1
		b *= -1
	if a == 0 and b < 0:
		b *= -1
	if g != 0:
		a = a // g
		b = b // g
	if (a,b) in d:
		d[(a,b)] += 1
	else:
		d[(a,b)] = 1

ans_sp = 0
if (0,0) in d:
	ans_sp += d[(0,0)]

def pow(n, k):
	ret = 1
	while k > 0:
		if k % 2 == 1:
			ret = ret * n % MOD
		n = n * n % MOD
		k = k // 2
	return ret

ans = 1
for k in d:
	a,b = k[0], k[1]
	if a == 0 and b == 0:
		continue
	v = d[k]
	x,y = b,-a
	if x < 0:
		x *= -1
		y *= -1
	if x == 0 and y < 0:
		y *= -1
	if y == 0 and x < 0:
		x *= -1
	if (x,y) in d:
		if  b > y:
			continue
		tmp = (pow(2,v) + pow(2,d[(x,y)]) - 1) % MOD
		ans = (ans * tmp) % MOD
	else:
		ans = (ans * pow(2,v)) % MOD
print(ans_sp + ans - 1)

Submission status: Wrong Answer

Solution code:
import sys

n=int(input())
mod=10**9+7
pow2=[1]
for i in range(n+10):
    pow2.append(pow2[-1]*2%mod)

P=[] #[比較する数,正負の場合分け]
Q=[]
zero=0
for i in range(n):
    a,b=map(int,input().split())
    if a*b==0:
        zero+=1
    elif a*b>0:
        P.append([a/b,0])
    else:
        P.append([-b/a,1])
P.sort()
print(P)
if not P:
    print(zero)
    sys.exit()

now=P[0][0]
cnt0=0
cnt1=0
d=n
ans=1
for p in P:
    if now!=p[0]:
        if cnt0*cnt1>0:
            d-=cnt0+cnt1
            ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod
            #print(cnt0,cnt1,d,ans)
        cnt0=0
        cnt1=0
    now=p[0]
    if p[1]==0:
        cnt0+=1
    else:
        cnt1+=1
if cnt0*cnt1>0:
    d-=cnt0+cnt1
    ans=ans*(pow2[cnt0]+pow2[cnt1]-1)%mod

if zero>1:
    d-=zero
    ans=ans*(zero+1)%mod
ans=ans*pow2[d]%mod
print(ans-1)

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 and b != 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 b > 0 or a == 0:
        col.append((a, b))
    elif 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

ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

abl = [map(int, input().split()) for _ in range(n)]

from collections import defaultdict
dic = defaultdict(int)

# a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

ab0 = 0
a0 = 0
b0 = 0
for a,b in abl:
    if a == 0 and b == 0:
        ab0 += 1
        continue
    elif a == 0:
        a0 += 1
        continue
    elif b == 0:
        b0 += 1
        continue
    gc = abs(gcd(a,b))
    if a < 0:
        a, b = -a // gc, -b // gc
    else:
        a, b = a // gc, b // gc
    dic[(a,b)] += 1
MOD = 1000000007
ans = 1
used = defaultdict(int)
for (a,b) in dic:
    if b > 0:
        target = (b, -a)
    else:
        target = (-b, a)
    if target in dic:
        if used[target] == 0:
            ans *= pow(2, dic[(a,b)], MOD) + pow(2, dic[target], MOD) - 1
            used[(a,b)] = 1
    else:
        ans *= (dic[(a,b)] + 1)
    ans %= 1000000007

ans *= pow(2, a0, MOD) + pow(2, b0, MOD) - 1
ans %= 1000000007
print((ans - 1 + ab0) % MOD)

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=0
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)
if az*bz:
  t.append((az,bz))
  n-=az+bz
  tt+=(az+bz+1)
for p,m in t:
  ttt=tt-(p+m)
  ans-=pow(2,n,mod)*ttt*(pow(2,p,mod)-1)*(pow(2,m,mod)-1)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())

mod = 1000000007

team_minus = {}
team_plus = {}

team_zero_a = 0
team_zero_b = 0
team_zero_ab = 0

for i in range(n):
    a, b = map(int, input().split())
    if a * b < 0:
        if team_minus.get(abs(a/b), None) is None:
            team_minus[abs(a/b)] = 1
        else:
            team_minus[abs(a/b)] += 1
    elif a * b > 0:
        if team_plus.get(b/a, None) is None:
            team_plus[b/a] = 1
        else:
            team_plus[b/a] += 1
    else:
        if a == 0:
            if b == 0:
                team_zero_ab += 1
            else:
                team_zero_a += 1
        else:
            team_zero_b += 1

bad_relations = []

bad_number = 0

for key in team_minus:
    if team_plus.get(key, None) is not None:
        minus_number = team_minus[key]
        plus_number = team_plus[key]
        bad_relations.append([minus_number, plus_number])
        bad_number += (minus_number + plus_number)

bad_relations.append([team_zero_a, team_zero_b])
bad_number += (team_zero_a + team_zero_b)

true_good_number = n - bad_number - team_zero_ab

ans = 0

ans += pow(2, true_good_number, mod)

for bad_relation in bad_relations:
    selection_number = (pow(2, bad_relation[0], mod) - 1) + (pow(2, bad_relation[1], mod) - 1)
    ans_plus = selection_number * ans % mod
    ans += ans_plus
    ans %= mod

ans += team_zero_ab
ans -= 1
ans %= mod

print(ans)

Submission status: Wrong Answer

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


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


MOD = 10 ** 9 + 7
n, *ab = map(int, sys.stdin.buffer.read().split())
ab_zero = 0
a_zero = 0
b_zero = 0
nonzero = defaultdict(int)

for a, b in zip(ab[0::2], ab[1::2]):
    if a == 0 and b == 0:
        ab_zero += 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        if a == 0 and b < 0:
            b = -b
        nonzero[a, b] += 1

n -= ab_zero

dame_pairs_pattern = 1
dame_pairs_cnt = 0

if a_zero > 0 and b_zero > 0:
    dame_pairs_pattern *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
    dame_pairs_cnt += a_zero + b_zero

checked = set()

for (a, b), cnt in nonzero.items():
    if (a, b) in checked:
        continue
    if b < 0:
        c, d = -b, a
    else:
        c, d = b, -a
    if (c, d) in nonzero:
        cnt2 = nonzero[c, d]
        dame_pairs_pattern *= pow(2, cnt, MOD) + pow(2, cnt2, MOD) - 1
        dame_pairs_pattern %= MOD
        dame_pairs_cnt += cnt + cnt2
        checked.add((c, d))

ans = dame_pairs_pattern * pow(2, n - dame_pairs_cnt, MOD) - 1

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
n = int(input())

abl = [map(int, input().split()) for _ in range(n)]

from collections import defaultdict
dic = defaultdict(int)

# a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

ab0 = 0
a0 = 0
b0 = 0
for a,b in abl:
    if a == 0 and b == 0:
        ab0 += 1
        continue
    elif a == 0:
        a0 += 1
        continue
    elif b == 0:
        b0 += 1
        continue
    gc = abs(gcd(a,b))
    if a < 0:
        a, b = -a // gc, -b // gc
    else:
        a, b = a // gc, b // gc
    dic[(a,b)] += 1
MOD = 1000000007
ans = 1
used = defaultdict(int)
for (a,b) in dic:
    if b > 0:
        target = (b, -a)
    else:
        target = (-b, a)
    if target in dic:
        if used[target] == 0:
            ans *= pow(2, dic[(a,b)], MOD) + pow(2, dic[target], MOD) - 1
            used[(a,b)] = 1
    else:
        ans *= (dic[(a,b)] + 1)
    ans %= 1000000007

ans *= pow(2, a0, MOD) + pow(2, b0, MOD) - 1
ans %= 1000000007
print(ans - 1 + ab0)

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
N = int(input())

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

T1 = []
T2 = []
T0 = 0

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

for i in range(N): #第一象限、第二象限だけを考える
    if E[i][0] <= 0 and E[i][1] <= 0:
        E[i][0] = -E[i][0]
        E[i][1] = -E[i][1]
    elif E[i][0] >= 0 and E[i][1] < 0:
        E[i][0] = -E[i][0]
        E[i][1] = -E[i][1]

for i in range(N):
    if E[i][0] == E[i][1] == 0:
        T0 += 1
    elif E[i][0] > 0:
        g = gcd(E[i][0], E[i][1])
        T1.append([E[i][0]//g, E[i][1]//g])
    else:
        g = gcd(E[i][0], E[i][1])
        T2.append([E[i][1]//g, -(E[i][0]//g)])

from collections import defaultdict

D = defaultdict(lambda :[0, 0])

for i in range(len(T1)):
    D[(T1[i][0], T1[i][1])][0] += 1

for i in range(len(T2)):
    D[(T2[i][0], T2[i][1])][1] += 1

res = 1

for x, y in D.values():

    if x > 0 and y > 0:
        res *= (1 + pow(2, x, MOD) - 1 + pow(2, y, MOD) - 1)
        res %= MOD
    elif x > 0:
        res *= pow(2, x, MOD)
        res %= MOD
    elif y > 0:
        res *= pow(2, y, MOD)
        res %= MOD

print(res - 1 + T0)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
mod = 10**9+7
n = int(input())
dic = defaultdict(lambda:[[0,0],[0,0]])
zero = [0,0]
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            continue
        else:
            if a == 0:
                zero[0] += 1
            else:
                zero[1] += 1
        continue
    minus = False
    rev = False
    if a * b < 0:
        minus = True
    a,b = abs(a),abs(b)
    g = gcd(a,b)
    a,b = a//g,b//g
    if a > b:
        a,b = b,a
        rev = True
    if minus:
        if rev:
            dic[(a,b)][0][1] += 1
        else:
            dic[(a,b)][0][0] += 1
    else:
        if rev:
            dic[(a,b)][1][1] += 1
        else:
            dic[(a,b)][1][0] += 1
ans = 1
for y in dic.keys():
    x = dic[y]
    if y == (1,1):
        ans *= 2**sum(x[0])+2**sum(x[1])-1
    else:
        ans *= 2**x[0][1]+2**x[1][0]-1
        ans *= 2**x[0][0]+2**x[1][1]-1
        ans %= mod
ans *= 2**zero[0]+2**zero[1]-1
ans %= mod
ans += 10**9+6
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = inpm()
        m = gcd(a,b)
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                a //= m
                b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        rev = ' '.join([str(-b),str(a)])
        flag = 0
        cnt = 0
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        cnt += dic1[rev]
        rev = ' '.join([str(b),str(-a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        cnt += dic1[rev]
        if flag:
            continue
        if a == 0 or b == 0:
            continue
        n1 = pow(2,dic[e],mod)-1
        n2 = pow(2,cnt,mod)-1
        if n1 == 0:
            ans *= (n2+1)
        elif n2 == 0:
            ans *= (n1+1)
        else:
            ans *= (n1+n2+1)
        ans %= mod
    num = dic['1 0'] + dic['0 1'] + dic['0 0']
    if num != 0:
        ans *= (num+1)
        ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

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))
for ai,bi in C:
    if C[(ai,bi)]<0:##集計済
        continue
    if ai==0:##ai==0
        if (bi,ai) in C:
            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
    elif bi==0:##bi==0
        if ai<0:##?
            ai*=-1
        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
    elif 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:
# -*- 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
    ans+=zz
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
mod = 10**9+7
N = int(input())
AB = [list(map(int, input().split())) for i in range(N)]
cnt = defaultdict(int)
for i, (A, B) in enumerate(AB):
    if A == 0 or B == 0:
        A, B = 0, 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
    if cnt[(-A, -B)] > 0:
        a, b = -A, -B
    elif cnt[(-B, A)] > 0:
        a, b = -B, A
    elif cnt[(B, -A)] > 0:
        a, b = B, -A
    else:
        a, b = A, B
    cnt[(a, b)] += 1
ans = 0
f = 1
p = [None]*len(cnt)
vs = cnt.values()
for i, v in enumerate(vs):
    p[i] = pow(2, v, mod)    
    f = f * p[i] % mod
for i, v in enumerate(vs):
    f = f * pow(p[i], mod-2, mod) % mod
    ans += v * f
    ans %= mod
print(ans)