Problem: 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.

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

ans = 1

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

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


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

ans = 1

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

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


Verdicts: Wrong Answer

Accepted