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):
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 = 1
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)


from collections import defaultdict

def gcd(a, b):
    return gcd(b, a%b) if b else a

mod = 10 ** 9 + 7
N = int(input())
X = defaultdict(lambda: [0, 0])
print(X[(1, 1)])

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
# suppose we have a super head point which can put togother with every point.
ans = 1
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
print((ans+z-1)%mod)


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)


mod = 10 ** 9 + 7
from math import gcd
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
ans = 1
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 - 1
ans %= mod
print(ans)


Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted