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 collections
import math

n = int(input())
m = 0
mod = 10 ** 6 + 7
c = []
d = []
frac = {}

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        n -= 1
        m += 1
        continue
    try:
        if a == 0:
            frac['0'] += 1
        elif b == 0:
            frac['inf'] += 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = 1 if a * b > 0 else -1
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] += 1
    except KeyError:
        if a == 0:
            frac['0'] = 1
        elif b == 0:
            frac['inf'] = 1
        else:
            gcd = abs(math.gcd(a, b))
            sign = a * b // abs(a * b)
            a = sign * abs(a) // gcd
            b = abs(b) // gcd
            frac['{}/{}'.format(a, b)] = 1

def inverse(key):
    if key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key == '0': continue
    if key[0] == '-': continue
    try:
        if key == 'inf':
            d.append(frac['0'])
        else:
            d.append(frac[inverse(key)])
        c.append(value)
    except KeyError:
        continue

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1)
    ans = (ans * (pow(2, i, mod) + pow(2, j, mod) - 1)) % mod
ans = (ans * (m + 1) - 1) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math


def main():

    mod = 1000000007
    N = int(input())

    A = [0]
    B = [0]

    for n in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    calc = dict()
    non_count = 0

    for i in range(1, N + 1):

        if A[i] == 0 and B[i] == 0:
            non_count += 1
        elif A[i] == 0:
            k = (0, 1)
            if calc.get(k):
                calc[k][0] += 1
            else:
                calc[k] = [1, 0]
        elif B[i] == 0:
            k = (1, 0)
            if calc.get(k):
                calc[k][0] += 1
            else:
                calc[k] = [1, 0]
        else:
            r = math.gcd(A[i], B[i])
            m = 1
            if A[i] * B[i] < 0:
                m = -1
            k1 = (m * abs(A[i] // r), abs(B[i] // r))
            k2 = (-m * abs(B[i] // r), abs(A[i] // r))
            if calc.get(k1):
                calc[k1][0] += 1
            elif not calc.get(k2):
                calc[k1] = [1, 0]
            else:
                calc[k2][1] += 1

    N = N - non_count

    count = 0
    for k, v in calc.items():
        if not v[0] * v[1] == 0:
            count += v[0] + v[1]

    ans = pow(2, N - count, mod)
    for k, v in calc.items():
        if not v[0] * v[1] == 0:
            comb = (pow(2, v[0]) + pow(2, v[1]) - 1)
            ans = (ans * comb) % mod

    print(ans - 1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

zero = sum([1 for a, b in ab if a ==  b == 0])
adivb = [(float('inf') if b == 0 else a / b)
         for a, b in ab if not(a == b == 0)]
bdiva = [(float('inf') if a == 0 else -b / a)
         for a, b in ab if not(a == b == 0)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i > 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
    ans %= mod
if zero > 0:
    print(ans * pow(2, n - cnt - zero, mod) + zero -1 % mod)
else:
    print(ans * pow(2, n - cnt, mod) - 1 % mod)
# 19 246177278

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

zero = sum([1 for a, b in ab if a ==  b == 0])
adivb = [(float('inf') if b == 0 else a / b)
         for a, b in ab if not(a == b == 0)]
bdiva = [(float('inf') if a == 0 else -b / a)
         for a, b in ab if not(a == b == 0)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i > 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
    ans %= mod
if zero > 0:
    print(ans * pow(2, n - cnt - zero, mod) + zero % mod)
else:
    print(ans * pow(2, n - cnt, mod) - 1 % mod)

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

zero = sum([1 for a, b in ab if a ==  b == 0])
adivb = [(float('inf') if b == 0 else a / b)
         for a, b in ab if not(a == b == 0)]
bdiva = [(float('inf') if a == 0 else -b / a)
         for a, b in ab if not(a == b == 0)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i > 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
    ans %= mod
if zero > 0:
    print(ans * pow(2, n - cnt - zero, mod) + zero -1 % mod)
else:
    print(ans * pow(2, n - cnt, mod) - 1 % mod)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

t = []
d = {}
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        result *= d[0][0] + 1
        result %= 1000000007
    else:
        i = d[a][b]
        j, k, l = 0, 0, 0
        if -a in d and -b in d[-a]:
            j = d[-a][-b]
            used.add((-a, -b))
        if -b in d and a in d[-b]:
            k = d[-b][a]
            used.add((-b, a))
        if b in d and -a in d[b]:
            l = d[b][-a]
            used.add((b, -a))
        result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
        result %= 1000000007
print(result - 1)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = 0
B = 0
Z = 0
C = {}
m = 1000000007

def mypow(dummy, num):
    ans = 1
    for i in range(num):
        ans = (ans*2)%1000000007
    return ans

def rNum(a, b):
    g = math.gcd(a, b)
    if a >0 and b <0:
        return (-1*(a//g), -1*(b//g))
    else:
        return (a//g, b//g)


for i in range(N):
    a, b = map(int, input().split())
    
    if a == 0 and b==0:
        Z += 1
        continue
    elif a==0:
        A += 1
        continue
    elif b==0:
        B +=1
        continue
    
    r = rNum(a, b)
    if r in C.keys():
        C[r] +=1
    else: C[r] = 1


used = set()
ans = 1
ans *= (mypow(2, A) + mypow(2, B) -1)%m


for c in C.keys():
    if c in used: continue
    a, b = c
    r = rNum(b, -1*a)
    if r in C.keys():
        if c == r: continue
        used.add(r)
        score = (mypow(2, C[c]) + mypow(2, C[r])- 1)
        ans *= score

    else:
        ans *= mypow(2, C[c])

ans += Z

print((ans-1)%m)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
N=int(input())
mod = 10**9+7
d_1 = defaultdict(int)
d_2 = defaultdict(int)
zeros = 0

def to_irreducible(a,b):
    GCD = gcd(a,b)
    return list(map(lambda x:x//GCD,[a,b]))
for i in range(N):
    a,b=map(int,input().split(' '))
    if a==b==0:
        zeros += 1
        continue
    if a*b >= 0 and b!=0:
        a,b = to_irreducible(abs(a),abs(b))
        d_1[(a,b)] +=1
    else:
        a,b = to_irreducible(abs(b),abs(a))
        d_1[(a,b)] +=0
        d_2[(a,b)] +=1

ans =  1

for k,v_1 in d_1.items():
    v_2 = d_2[k]
    ans *= pow(2,v_1,mod) + pow(2,v_2,mod) -1
    ans %= mod

print(ans+zeros-1)

Submission status: Wrong Answer

Solution code:
def main():
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 1000000007
  from collections import defaultdict
  from fractions import Fraction

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int,{})
  dd_ab = defaultdict(int,{})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      dd_ba[Fraction(-b, a)] += 1
      dd_ab[Fraction(a, b)] += 1


  ans = (2**zero_one_count + 2**one_zero_count -1)
  flag_dd = defaultdict(bool,{})

  for key,value in dd_ba.items():
    if flag_dd[key]:
      continue
    ans *= (2**dd_ab[key] + 2**value - 1) % MOD
    ans %= MOD
    flag_dd[Fraction(key.denominator, -(key.numerator))] = True

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

Submission status: Wrong Answer

Solution code:
import math
import itertools

n = int(input())
mod = 1000000007

def Is_Positive(n):
    return n > 0

allZeros = 0
vectors = dict()
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        allZeros += 1
        continue
    gcd = math.gcd(a, b)

    key = (0, 0)
    if Is_Positive(a) and Is_Positive(b):
        key = (abs(a) // gcd, abs(b) // gcd)
        if key not in vectors:
            vectors[key] = (1, 0)
        else:
            vectors[key] = (vectors[key][0] + 1, vectors[key][1])
    else:
        key = (abs(b) // gcd, abs(a) // gcd)
        if key not in vectors:
            vectors[key] = (0, 1)
        else:
            vectors[key] = (vectors[key][0], vectors[key][1] + 1)



total = 1
for vec in vectors.values():

    total *= ((2**(vec[0]))
              + (2**(vec[1])) - 1) % mod

print(total- 1 + allZeros)

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

zero = sum([1 for a, b in ab if a ==  b == 0])
adivb = [(float('inf') if b == 0 else a / b)
         for a, b in ab if not(a == b == 0)]
bdiva = [(float('inf') if a == 0 else -b / a)
         for a, b in ab if not(a == b == 0)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i >= 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
    ans %= mod
if zero > 0:
    print(ans * pow(2, n - cnt - zero, mod) + zero + 1 % mod)
else:
    print(ans * pow(2, n - cnt, mod) - 1 % mod)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        if a*b!=0:
            g=gcd(abs(a),abs(b))
            a=a//g
            b=b//g
        elif (a,b)!=(0,0):
            #assert 0
            if a==0:
                b=1
            else:
                a=1
        
        #aを正にする
        if a<0:
            a*=-1
            b*=-1
            
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k))

    temp0=0
    for i in range(len(L)):
        k=L[i]
        v=d[k]
        if v==0:
            continue
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if a*b!=0:
            if (-b,a) in d:
                v2=d[(-b,a)]
                temp+=pow(2,v2)-1
                d[(-b,a)]=0
            if (b,-a) in d:
                v2=d[(b,-a)]
                temp+=pow(2,v2)-1
                d[(b,-a)]=0
                    
        elif (a,b)==(1,0) or (a,b)==(0,1):
            if (b,a) in d:
                v2=d[(b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,a)]=0
        else:
            temp0=v
            temp=1
            
        #print(k,v,temp)
        ans=(ans*temp)%mod
        
        


    ans=(ans-1+temp0)%mod
    print(ans)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()

Submission status: Wrong Answer

Solution code:
import math
import itertools

n = int(input())
mod = 1000000007

def Is_Positive(n):
    return n > 0

allZeros = 0
vectors = dict()
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        allZeros += 1
        continue
    gcd = math.gcd(a, b)



    key = (0, 0)
    if Is_Positive(a) and Is_Positive(b):
        key = (abs(a) // gcd, abs(b) // gcd)
        if key not in vectors:
            vectors[key] = (1, 0)
        else:
            vectors[key] = (vectors[key][0] + 1, vectors[key][1])
    else:
        key = (abs(b) // gcd, abs(a) // gcd)
        if key not in vectors:
            vectors[key] = (0, 1)
        else:
            vectors[key] = (vectors[key][0], vectors[key][1] + 1)



total = 1
for vec in vectors.values():

    total *= (1 + (2**(vec[0])-1)
              + (2**(vec[1])-1)) % mod

print(total- 1 + allZeros)

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

zero = sum([1 for a, b in ab if a ==  b == 0])
adivb = [(float('inf') if b == 0 else a / b)
         for a, b in ab if not(a == b == 0)]
bdiva = [(float('inf') if a == 0 else -b / a)
         for a, b in ab if not(a == b == 0)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i >= 0):
        cntadb[i] += 2 ** bda[i] + 2 ** adb[i] - 1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
    ans %= mod
print(ans * pow(2, n - cnt - zero, mod) + zero - 1 % mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
import math
sin_dic = {}
mod = 1000000007

zero_num = 0
for i in range(N):
    a, b = list(map(int, input().split()))
    if a == 0 and b == 0:
        zero_num += 1
        continue
    if a == 0:
        b = -1
    elif b == 0:
        a = 1
    else:
        c = math.gcd(a, b)
        a, b = a//c, b//c
        if a < 0 and b < 0:
            a, b = -a, -b
        elif a < 0 and b > 0:
            a, b = -a, -b
    if (a,b) in sin_dic:
        sin_dic[(a, b)].append(i)
    else:
        sin_dic[(a, b)] = [i]

ans = 1
skip_dic = {}
for (key, _key) , values in sin_dic.items():
    if (key, _key) in skip_dic:
        continue
    oth_len = 0
    norm_len = 0
    norm_len += len(values)
    if (-key, -_key) in sin_dic:
        norm_len += len(sin_dic[(-key, -_key)])
    if (_key, -key) in sin_dic:
        oth_len += len(sin_dic[(_key, -key)])
    if (-_key, key) in sin_dic:
        oth_len += len(sin_dic[(-_key, key)])

    p = pow(2, oth_len, mod) - 1 + pow(2, norm_len, mod)
    ans = (ans * p) % mod
    skip_dic[(_key, -key)] = True
    skip_dic[(-_key, key)] = True
    skip_dic[(-_key, -key)] = True
print((ans-1 + zero_num) % mod)

Submission status: Wrong Answer

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    AB = [ZZ() for _ in range(N)]
    AB = [[a, b] for a, b in AB if a != 0 or b != 0] # 零ベクトルは除外
    cnt_0 = N - len(AB) # 零ベクトルの個数
    vec = defaultdict(int) # ベクトル個数の管理

    #既約化
    for i in range(len(AB)):
        a, b = AB[i]
        if a < 0: a, b = -a, -b
        g = math.gcd(a, b)
        a //= g
        b //= g
        vec[(a, b)] += 1

    output = 1
    used = set()
    for v in vec.keys():
        if v in used: continue
        a, b = v
        inv = (-b, a) if b < 0 else (b, -a)
        if inv in vec.keys():
            output *= (pow(2, vec[v], MOD) + pow(2, vec[inv], MOD) - 1)
        else: output *= pow(2, vec[v], MOD)
        output %= MOD
        used.add(v)
        used.add(inv)

    output += cnt_0 - 1
    output %= MOD
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N = Z()
    AB = [ZZ() for _ in range(N)]
    AB = [[a, b] for a, b in AB if a != 0 or b != 0] # 零ベクトルは除外
    cnt_0 = N - len(AB) # 零ベクトルの個数
    vec = defaultdict(int) # ベクトル個数の管理

    #既約化
    for i in range(len(AB)):
        a, b = AB[i]
        if a < 0: a, b = -a, -b
        g = math.gcd(a, b)
        a //= g
        b //= g
        vec[(a, b)] += 1

    output = 1
    used = set()
    for v in vec.keys():
        if v in used: continue
        a, b = v
        inv = (-b, a) if b < 0 else (b, -a)
        if inv in vec.keys():
            output *= (pow(2, vec[v], MOD) + pow(2, vec[inv], MOD) - 1)
        else: output *= pow(2, vec[v], MOD)
        output %= MOD
        used.add(v)
        used.add(inv)

    output += cnt_0 - 1
    print(output)
    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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

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

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

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = 0
B = 0
Z = 0
C = {}
m = 1000000007

def mypow(dummy, num):
    ans = 1
    for i in range(num):
        ans = (ans*2)%1000000007
    return ans

def rNum(a, b):
    g = math.gcd(a, b)
    if a >0 and b <0:
        return (-1*(a//g), -1*(b//g))
    else:
        return (a//g, b//g)

def inv(rnum):
    a,b = rnum
    if a <0 and b >0:
        return (-1*b, -1*a)
    else:
        return (b, a)
        

for i in range(N):
    a, b = map(int, input().split())
    
    if a == 0 and b==0:
        Z += 1
        continue
    elif a==0:
        A += 1
        continue
    elif b==0:
        B +=1
        continue
    
    r = rNum(a, b)
    if r in C.keys():
        C[r] +=1
    else: C[r] = 1


used = set()
ans = 1
ans *= (mypow(2, A) + mypow(2, B) -1)%m


for c in C.keys():
    if c in used: continue
    a, b = c
    a *= -1
    r = rNum(b, a)
    if r in C.keys():
        if c == r: continue
        used.add(r)
        score = (mypow(2, C[c]) + mypow(2, C[r])- 1)%m
        ans = (ans * score)%m

    else:
        ans = (ans*mypow(2, C[c]))%m

ans += Z

print(ans-1)

Submission status: Wrong Answer

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

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

N = int(input())
zero = 0
cnt = defaultdict(int)
MOD = 10**9+7

for _ in range(N):
    A, B = map(int, input().split())
    
    if A==0 or B==0:
        zero += 1
    elif A>0 and B>0:
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(A, B)] += 1
    elif A>0 and B<0:
        B *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(-A, B)] += 1
    elif A<0 and B>0:
        A *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(-A, B)] += 1
    else:
        A *= -1
        B *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(A, B)] += 1

s = set()
ans = 1

for k in cnt.keys():
    if k in s:
        continue
    
    k2 = (-k[1], k[0])
    
    if k2[0]<0 and k2[1]<0:
        k2 = (-k2[0], -k2[1])
    elif k2[0]>0 and k2[1]<0:
        k2 = (-k2[0], -k2[1])
        
    a = cnt[k]
    
    if k2 not in cnt:
        ans *= pow(2, a, MOD)
        ans %= MOD
    else:
        b = cnt[k2]
        ans *= pow(2, a, MOD)+pow(2, b, MOD)-1
        ans %= MOD
        s.add(k2)

ans *= zero+1
ans %= MOD
ans -= 1
ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import collections
import math

N=int(input())
posi=[]
nega=[]
mod=1000000007
power=[1]*(N+1)
zero=0

for i in range(1,N+1):
    power[i]=power[i-1]*2%mod
    
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0:
        posi.append(0)
    elif b==0:
        nega.append(0)
    elif a/b>=0:
        posi.append(a/b)
    else:
        nega.append((-1)*b/a)

m=N-zero
cp=collections.Counter(posi)
cn=collections.Counter(nega)

x=1
y=1


for pp in cp.keys():
    if pp in cn.keys():
        p=cp[pp]
        n=cn[pp]
        powp=power[p]
        pown=power[n]
        e=(powp-1)*(pown-1)%mod
        f=(powp+pown-1)%mod
        x=x*(e+f)%mod
        y=y*f%mod
        m-=(p+n)
        
ans=power[N-zero]-1-power[m]*(x-y)%mod
print((ans+zero)%mod)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
zz = 0 # a=b=0
for n in range(N):
    a,b = map(int,input().split())
    if a==0 and b==0:
        zz += 1
        continue
    if a==0:
        n_sign = 0
    elif b==0:
        n_sign = 1
    
    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)
    # print(n_sign,a,b)


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

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 += zz
ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
A = 0
B = 0
Z = 0
C = {}
m = 1000000007

def mypow(dummy, num):
    ans = 1
    for i in range(num):
        ans = (ans*2)%1000000007
    return ans

def rNum(a, b):
    g = math.gcd(a, b)
    if a >0 and b <0:
        return (-1*(a//g), -1*(b//g))
    else:
        return (a//g, b//g)

def inv(rnum):
    a,b = rnum
    if a <0 and b >0:
        return (-1*b, -1*a)
    else:
        return (b, a)
        

for i in range(N):
    a, b = map(int, input().split())
    
    if a == 0 and b==0:
        Z += 1
        continue
    elif a==0:
        A += 1
        continue
    elif b==0:
        B +=1
        continue
    
    r = rNum(a, b)
    if r in C.keys():
        C[r] +=1
    else: C[r] = 1


used = set()
ans = 1
ans *= (mypow(2, A) + mypow(2, B) -1)%m


for c in C.keys():
    if c in used: continue
    a, b = c
    a *= -1
    r = rNum(b, a)
    if r in C.keys():
        # print(inv(c), c)
        if c == r: continue
        
        used.add(r)
        score = mypow(2, C[c]) + mypow(2, C[r])- 1
        ans = (ans * score)%m

    else:
        ans = (ans*mypow(2, C[c]))%m

ans += Z

print(ans-1)

Submission status: Wrong Answer

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)
A = []
B = []
F = []
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

ans = 1
cnt1 = 0
cnt2 = 0
cnt3 = 0
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)
    if g:
        a = a // g
        b = b // g
    A += [a]
    B += [b]
    F += [flg]
    if a == 0 and b == 0:
        cnt3 += 1
    elif a == 0:
        cnt1 += 1
    elif b == 0:
        cnt2 += 1
    else:
        D[(flg, a, b)] += 1

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

print(ans * (pow2[cnt1] + pow2[cnt2] - 1) % mod - 1 + cnt3)

Submission status: Wrong Answer

Solution code:
import collections
import math
 
N=int(input())
posi=[]
nega=[]
mod=1000000007
power=[1]*(N+1)
zero=0
 
for i in range(1,N+1):
    power[i]=power[i-1]*2%mod
    
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0:
        posi.append((0,1))
    elif b==0:
        nega.append((0,1))
    elif a/b>=0:
        posi.append((a/math.gcd(a,b),b/math.gcd(a,b)))
    else:
        nega.append((abs(b/math.gcd(a,b)),abs(a/math.gcd(a,b))))
 
m=N-zero
cp=collections.Counter(posi)
cn=collections.Counter(nega)
 
x=1
y=1
 
 
for pp in cp.keys():
    if pp in cn.keys():
        p=cp[pp]
        n=cn[pp]
        powp=power[p]
        pown=power[n]
        e=(powp-1)*(pown-1)%mod
        f=(powp+pown-1)%mod
        x=x*(e+f)%mod
        y=y*f%mod
        m-=(p+n)
        
ans=power[N-zero]-1-power[m]*(x-y)%mod
print((ans+zero)%mod)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        if a*b!=0:
            g=gcd(abs(a),abs(b))
            a=a//g
            b=b//g
        elif (a,b)!=(0,0):
            #assert 0
            if a==0:
                b=1
            else:
                a=1
        if a<0:
            a*=-1
            b*=-1
            
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k))

    temp0=0
    for i in range(len(L)):
        k=L[i]
        v=d[k]
        if v==0:
            continue
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if a*b!=0:
            if (-b,a) in d:
                v2=d[(-b,a)]
                temp+=pow(2,v2)-1
                d[(-b,a)]=0
            if (b,-a) in d:
                v2=d[(b,-a)]
                temp+=pow(2,v2)-1
                d[(b,-a)]=0
                    
        elif (a,b)==(1,0) or (a,b)==(0,1):
            if (b,a) in d:
                v2=d[(b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,a)]=0
        else:
            temp0=v
            temp=1
        ans=(ans*temp)%mod
        
        


    ans=(ans-1+temp0)%mod
    print(ans)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()