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:
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    MOD = 1000000007
    N = int(input())
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    for i in range(N):
        a, b = map(int, input().split())
        # bが0のときは約分できないのでそのまま
        if b == 0:
            C[(a, b)] += 1
            continue
        _gcd = gcd(a, b)
        a = a // _gcd
        b = b // _gcd
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    groups = []
    for c, nc in C.items():
        a, b = c
        # 仲の悪いイワシの個数
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_b = -bad_b
            bad_a = -bad_a
        nBad = C.get((bad_a, bad_b), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        if nBad == 0:
            groups.append(2 ** nc)
            continue
        # 中の悪いグループがすでに調査済みなら何もしない
        elif flag[(bad_a, bad_b)]:
            continue

        # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
        # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
        # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
        # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
        groups.append((2 ** nc) + (2 ** nBad) - 1)
        flag[(a, b)] = True

    # 各グループの選択肢を掛け合わせ、-1する
    # (全て選択しないパターンを除外する)
    ans = 1
    for g in groups:
        ans = (ans * g) % MOD
    ans -= 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 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
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    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.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)
print(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif 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] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

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) % mod
    ans = ans * tmp % mod
ans = (ans - 1 + m) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
mod = 10**9+7
n=int(input())
r = defaultdict(int)
for _ in range(n):
  a,b=map(int,input().split())
  if a == 0 and b == 0:
    r[(a,b)]+=1
  elif b == 0:
    r[(1,b)]+=1
  elif a == 0:
    r[(a,1)]+=1
  else:
    g = gcd(a,b)
    if a<0: a,b = -a,-b
    if b < 0:
      r[(abs(a)//g,-abs(b)//g)]+=1
    else:
      r[(abs(a)//g,abs(b)//g)]+=1

def cnt(a,b):
  ra,rb=0,0
  if a in r:ra=r[a]
  if b in r:rb=r[b]
  t = pow(2,ra+rb,mod)
  na = pow(2,ra,mod)-1
  nb = pow(2,rb,mod)-1
  #print(a,b,t,na,nb)
  return t-na*nb
  #return 1
ans = 1
checked = set()
#print(r)
for v in r:
  #print(v)
  if v == (0,0): continue
  if v in checked: continue
  if v == (1,0):
    ans *= cnt(v,(0,1))
    ans %= mod
    checked.add((1,0))
    checked.add((0,1))
  else:
    aibo = (-v[1],v[0])
    if aibo[0]<0:
      aibo = (v[1],-v[0])
    ans *= cnt(v,aibo)
    ans %= mod
    checked.add(v)
    checked.add(aibo)
    
print((ans-1)%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()


def add_positive(_):
    if _ not in vectors:
        vectors[_] = (1, 0)
    else:
        vectors[_] = (vectors[_][0] + 1, vectors[_][1])


def add_negative(_):
    if _ not in vectors:
        vectors[_] = (0, 1)
    else:
        vectors[_] = (vectors[_][0], vectors[_][1] + 1)


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 a == 0:
        key = (1, 0)
        add_negative(key)
    elif b == 0:
        key = (1, 0)
        add_positive(key)

    elif Is_Positive(a) and Is_Positive(b):
        key = (abs(a) // gcd, abs(b) // gcd)
        add_positive(key)
    else:
        key = (abs(b) // gcd, abs(a) // gcd)
        add_negative(key)



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

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

print(((total- 1) % mod + allZeros % mod) % mod)

Submission status: Wrong Answer

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

from fractions import Fraction

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

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

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
mod = 10**9+7
n=int(input())
r = defaultdict(int)
for _ in range(n):
  a,b=map(int,input().split())
  if a == 0 and b == 0:
    r[(a,b)]+=1
  elif b == 0:
    r[(1,b)]+=1
  elif a == 0:
    r[(a,1)]+=1
  else:
    g = gcd(a,b)
    if a<0: a,b = -a,-b
    if b < 0:
      r[(abs(a)//g,-abs(b)//g)]+=1
    else:
      r[(abs(a)//g,abs(b)//g)]+=1

def cnt(a,b):
  ra,rb=0,0
  if a in r:ra=r[a]
  if b in r:rb=r[b]
  t = pow(2,ra+rb,mod)
  na = pow(2,ra,mod)-1
  nb = pow(2,rb,mod)-1
  #print(a,b,t,na,nb)
  return t-na*nb
  #return 1
ans = 1
checked = set()
#print(r)
for v in r:
  #print(v)
  if v in checked: continue
  if v == (1,0):
    ans *= cnt(v,(0,1))
    ans %= mod
    checked.add((1,0))
    checked.add((0,1))
  else:
    aibo = (-v[1],v[0])
    if aibo[0]<0:
      aibo = (v[1],-v[0])
    ans *= cnt(v,aibo)
    ans %= mod
    checked.add(v)
    checked.add(aibo)
    
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
mod = 10**9+7
n=int(input())
r = defaultdict(int)
for _ in range(n):
  a,b=map(int,input().split())
  if a == 0 and b == 0:
    r[(a,b)]+=1
  elif b == 0:
    r[(1,b)]+=1
  elif a == 0:
    r[(a,1)]+=1
  else:
    g = gcd(a,b)
    if a<0: a,b = -a,-b
    if b < 0:
      r[(abs(a)//g,-abs(b)//g)]+=1
    else:
      r[(abs(a)//g,abs(b)//g)]+=1

def cnt(a,b):
  ra,rb=0,0
  if a in r:ra=r[a]
  if b in r:rb=r[b]
  t = pow(2,ra+rb,mod)
  na = pow(2,ra,mod)-1
  nb = pow(2,rb,mod)-1
  #print(a,b,t,na,nb)
  return t-na*nb
  #return 1
ans = 1
checked = set()
#print(r)
for v in r:
  #print(v)
  if v in checked: continue
  if v == (1,0):
    ans *= cnt(v,(0,1))
    ans %= mod
    checked.add((1,0))
    checked.add((0,1))
  else:
    aibo = (-v[1],v[0])
    if aibo[0]<0:
      aibo = (v[1],-v[0])
    ans *= cnt(v,aibo)
    ans %= mod
    checked.add(v)
    checked.add(aibo)
    
print(ans-1)

Submission status: Wrong Answer

Solution code:
import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 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
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    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.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)
print(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif 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] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

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 - 1 + m) % mod

print(ans)

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()


def add_positive(_):
    if _ not in vectors:
        vectors[_] = (1, 0)
    else:
        vectors[_] = (vectors[_][0] + 1, vectors[_][1])


def add_negative(_):
    if _ not in vectors:
        vectors[_] = (0, 1)
    else:
        vectors[_] = (vectors[_][0], vectors[_][1] + 1)


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 a == 0:
        key = (1, 0)
        add_negative(key)
    elif b == 0:
        key = (1, 0)
        add_positive(key)

    elif Is_Positive(a) and Is_Positive(b):
        key = (abs(a) // gcd, abs(b) // gcd)
        add_positive(key)
    else:
        key = (abs(b) // gcd, abs(a) // gcd)
        add_negative(key)



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

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

print((total- 1 + allZeros) % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][0]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][0]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        
print(ans + zero - 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())
zero1 = 0
zero2 = 0
zero3 = 0
cnt = defaultdict(int)
MOD = 10**9+7

for _ in range(N):
    A, B = map(int, input().split())
    
    if A==0 and B==0:
        zero1 += 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
    elif A<0 and B<0:
        A *= -1
        B *= -1
        G = gcd(A, B)
        A //= G
        B //= G
        cnt[(A, B)] += 1
    elif A==0:
        zero2 += 1
    else:
        zero3 += 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])
        
    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 += zero1
ans *= pow(2, zero2, MOD)+pow(2, zero3, MOD)-1
ans %= MOD
ans -= 1
ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        
print(ans + zero - 1)

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
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    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.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif 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 == '1/0': continue
    if key[0] == '-': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

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 - 1 + m) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        continue

    if a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        
print(ans + zero - 1)

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import functools
import heapq
import math
from collections import deque
from collections import defaultdict
MOD = 10**9+7

N = int(input())
A = [0]*N
B = [0]*N
C = [[0]*2 for _ in range(N)]
zero = 0
for i in range(N):
    A[i],B[i] = map(int,(input().split()))
    if A[i] == 0 and B[i] == 0:
        C[i] = (0,0)
        zero += 1
    elif B[i] == 0:
        C[i] = (A[i],B[i])
    elif B[i] > 0:
        g = math.gcd(A[i],B[i])
        C[i] = (A[i]//g,B[i]//g)
    else:
        g = math.gcd(A[i],B[i])
        C[i] = (-A[i]//g,-B[i]//g)

d = defaultdict(int)

for i in range(N):
    if C[i] != (0,0):
        d[C[i]] += 1

ans = 1
for k in d.keys():
    if k[0] >= 0:
        if (-k[1],k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(-k[1],k[0])],MOD) - 1
            d[k],d[(-k[1],k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)
    else:
        if (k[1],-k[0]) in d:
            ans *= pow(2,d[k],MOD) + pow(2,d[(k[1],-k[0])],MOD) -1
            d[k],d[(k[1],-k[0])] = 0,0
        else:
            ans *= pow(2,d[k],MOD)

print((ans-1)%MOD)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import Counter as cc
    from math import gcd
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = cc(),cc()
    count= 0
    count_zero_a = 0
    count_zero_b = 0
    ans = 1
    for i in range(n):
        a,b = map(int, input().split())
        if a == 0 and b== 0:
            count += 1
        else:
            gcd_ab = gcd(a,b)
            a //= gcd_ab
            b //= gcd_ab
            if b == 0:
                count_zero_b += 1
            elif a == 0: 
                count_zero_a += 1
            else:
                if a/b>0:
                    C_p[a,b] += 1
                else:
                    if b<0:
                        a = -a
                        b = -b
                    C_n[a,b] += 1
    
    ans *= (2**count_zero_a + 2**count_zero_b -1)%mod
    count += count_zero_a + count_zero_b    
    for a,b in C_p:
        if (-b,a) in C_n:
            count += C_n[-b,a] + C_p[a,b]
            ans *= (2**C_n[-b,a] + 2**C_p[a,b] -1)%mod
    ans *= pow(2,n-count,mod)%mod
    ans -=1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
import math

n = int(input())


ab = []
ba = []

a0 = 0
b0 = 0
ab0 = 0

for i in range(n):
    a, b = map(int, input().split())
    if a != 0 and b != 0:
        ab.append(Fraction(a, b))
        ba.append(Fraction(-b, a))
    elif a == 0 and b == 0:
        ab0 += 1
    elif a == 0 and b != 0:
        a0 += 1
    elif a != 0 and b == 0:
        b0 += 1


d_ab = dict()
d_ba = dict()

d_done = dict()

for i in range(len(ab)):
    cur = ab[i]
    if cur in d_ab:
        d_ab[cur] += 1
    else:
        d_ab[cur] = 1

    cur = ba[i]
    if cur in d_ba:
        d_ba[cur] += 1
    else:
        d_ba[cur] = 1

mod = 1000000007
ans = 1

for k, v in d_ab.items():
    x = v
    if k in d_ba:
        if k in d_done:
            continue
        else:
            y = d_ba[k]
            kake = 0
            kake += ((2**x) % mod + (2**y) % mod - 1)
            ans *= kake
            ans %= mod
            d_done[Fraction(-k.denominator, k.numerator)] = 1
    else:
        kake = (2**x) % mod
        ans *= kake
        ans %= mod

ans *= ((2**a0) % mod+(2**b0) % mod-1)
ans %= mod

ans += ab0
ans %= mod

print(ans-1)

Submission status: Wrong Answer

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


data=defaultdict(lambda:-1)
dp=[0 for i in range(N+1)]
dpsum=0
a,b=AB[0]
if a or b:
    dp[0]=1
    dpsum+=1
    data[a*idle_max+b]=0
else:
    dp[0]=0
c=0
for i in range(1,N):
    a,b=AB[i]
    M=dpsum
    if a==0 and b==0:
        continue
    elif a and b:
        M-=dp[data[-b*idle_max+a]]
        M-=dp[data[b*idle_max-a]]
    elif b==0:
        M-=dp[data[-a]]
    elif a==0:
        M-=dp[data[-b*idle_max]]

    dpsum=M*2%mod
    dp[i]=dpsum
    c+=dpsum
    c%=mod
    data[a*idle_max+b]=i
"""#print(dp)
for l in data:
    if data[l]!=-1:
        print(l,data[l])
        #print(l//idle_max,l%idle_max)
"""
print(sum(dp)%mod)

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 = (0, 1)
            if calc.get(k):
                calc[k][1] += 1
            else:
                calc[k] = [0, 1]
        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 + non_count)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
def gcd(a, b):
    return gcd(b, a%b) if b else a
N = int(input())
from collections import defaultdict
X = defaultdict(lambda: [0, 0])
x = 0
y = 0
z = 0
for i in range(N):
    a, b = map(int, input().split())
    g = abs(gcd(a, b))
    if a * b > 0:
        X[(abs(a) // g, abs(b) // g)][0] += 1
    elif a * b < 0:
        X[(abs(b) // g, abs(a) // g)][1] += 1
    else:
        if a:
            x += 1
        elif b:
            y += 1
        else:
            z += 1
print(X)
print(X.values())
ans = 0
pow2 = [1]
for i in range(N):
    pow2 += [pow2[-1] * 2 % mod]
for i in X.values():
    
    ans *= pow2[i[0]] + pow2[i[1]]- 1
    ans %= mod
ans *= pow2[x] + pow2[y] - 1
ans += z
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
# import time
import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1             # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    theta = []
    zero_zero_cnt = 0
    for i in range(n):
        a, b = mi()
        if a == 0 and b == 0:
            zero_zero_cnt += 1
        else:
            theta.append(math.degrees(math.atan2(b, a)))
    theta.sort()
    # print(theta)

    eps = 10 ** (-10)
    compressed_theta = []
    cnt_theta = []
    prev = -inf
    for i in range(len(theta)):
        if theta[i] <= prev + eps:
            cnt_theta[-1] += 1
        else:
            compressed_theta.append(theta[i])
            cnt_theta.append(1)
            prev = theta[i]

    # print(compressed_theta)
    pairs = []
    no_pair_ind = set(range(len(compressed_theta)))
    for i, dg in enumerate(compressed_theta):
        l_ind = bisect_left(compressed_theta, dg - 90 - eps)
        r_ind = bisect_right(compressed_theta, dg - 90 + eps)
        if l_ind != r_ind:
            # assert(l_ind + 1 == r_ind)
            # if l_ind + 1 != r_ind:
                # print(f"{dg}")
                # print(f"{l_ind} {r_ind} {compressed_theta[l_ind]} {compressed_theta[r_ind-1]}")
            pairs.append((cnt_theta[l_ind], cnt_theta[i]))
            if l_ind in no_pair_ind:
                no_pair_ind.remove(l_ind)
            if i in no_pair_ind:
                no_pair_ind.remove(i)
    
    num_of_no_pairs = sum([cnt_theta[ind] for ind in no_pair_ind])

    ans = pow(2, num_of_no_pairs, mod)
    for k, l in pairs:
        ans = (ans * (1 + pow(2, k, mod) - 1 + pow(2, l, mod) - 1)) % mod
    ans -= 1

    ans += zero_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 = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    if a < 0 :
        a, b = -a, -b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)