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):
N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
M=0
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if x==0:
    if a>b:
      k=(1,0)
    elif b>a:
      k=(0,1)
    else:
      k=(0,0)
  else:
    if a<0:
      a,b=-a,-b
    if b<0:
      a,b=a//x,-((-b)//x)
    else:
      a,b=a//x,b//x
    k=(a,b)
  d[k]+=1
  M=max(M,d[k])
ans=0
def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

#N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル
for i in range( 2, M + 1 ):
  g1.append( ( g1[-1] * i ) % MOD )
  inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
  g2.append( (g2[-1] * inverse[-1]) % MOD )

def C(x):
  _=0
  for i in range(1,x+1):
    _+=cmb(x,i,MOD)
  return _

if d[(0,0)]>0:
  ans+=d[(0,0)]
ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if b<0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans.append(C(d[(a,b)])+1)
    index+=1
  else:
    if ind[_k]==0:
      _ans.append(C(d[(a,b)]))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=C(d[(a,b)])+1
_=1
for a in _ans:
  _*=a
print((ans+_-1)%MOD)



N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
M=0
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(a,b)
  if x==0:
    if a>b:
      k=(1,0)
    elif b>a:
      k=(0,1)
    else:
      k=(0,0)
  else:
    a,b=a//x,b//x
    if a<0:
      a,b=-a,-b
    k=(a,b)
  d[k]+=1
  M=max(M,d[k])
ans=0

def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

#N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル
for i in range( 2, M + 1 ):
  g1.append( ( g1[-1] * i ) % MOD )
  inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
  g2.append( (g2[-1] * inverse[-1]) % MOD )

def C(x):
  _=0
  for i in range(1,x+1):
    _+=cmb(x,i,MOD)
  return _%MOD

if d[(0,0)]>0:
  ans+=d[(0,0)]
ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if b<0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans.append(C(d[(a,b)])+1)
    index+=1
  else:
    if ind[_k]==0:
      _ans.append(C(d[(a,b)]))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=C(d[(a,b)])+1
_=1
for a in _ans:
  _*=a
print((ans+_-1)%MOD)

N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
M=0
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(a,b)
  if x==0:
    if a>b:
      k=(1,0)
    elif b>a:
      k=(0,1)
    else:
      k=(0,0)
  else:
    a,b=a//x,b//x
    if a<0:
      a,b=-a,-b
    k=(a,b)
  d[k]+=1
  M=max(M,d[k])
ans=0

def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

#N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル
for i in range( 2, M + 1 ):
  g1.append( ( g1[-1] * i ) % MOD )
  inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
  g2.append( (g2[-1] * inverse[-1]) % MOD )

def C(x):
  _=0
  for i in range(1,x+1):
    _+=cmb(x,i,MOD)
  return _%MOD

if d[(0,0)]>0:
  x=d[(0,0)]
  for i in range(1,x+1):
    ans+=cmb(x,i,MOD)
ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if b<0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans.append(C(d[(a,b)])+1)
    index+=1
  else:
    if ind[_k]==0:
      _ans.append(C(d[(a,b)]))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=C(d[(a,b)])+1
_=1
for a in _ans:
  _*=a
print((ans+_-1)%MOD)

N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
M=0
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if x==0:
    if a>b:
      k=(1,0)
    elif b>a:
      k=(0,1)
    else:
      k=(0,0)
  else:
    a,b=a//x,b//x
    if a<0:
      a,b=-a,-b
    k=(a,b)
  d[k]+=1
  M=max(M,d[k])
ans=0

def cmb(n, r, mod):
  if ( r<0 or r>n ):
    return 0
  r = min(r, n-r)
  return g1[n] * g2[r] * g2[n-r] % mod

#N = 10**4
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル
for i in range( 2, M + 1 ):
  g1.append( ( g1[-1] * i ) % MOD )
  inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
  g2.append( (g2[-1] * inverse[-1]) % MOD )

def C(x):
  _=0
  for i in range(1,x+1):
    _+=cmb(x,i,MOD)
  return _%MOD

if d[(0,0)]>0:
  ans+=d[(0,0)]
ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if b<0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans.append(C(d[(a,b)])+1)
    index+=1
  else:
    if ind[_k]==0:
      _ans.append(C(d[(a,b)]))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=C(d[(a,b)])+1
_=1
for a in _ans:
  _*=a
print((ans+_-1)%MOD)

N=int(input())
from collections import defaultdict
import math
d = defaultdict(int)
MOD=10**9+7
for i in range(N):
  a,b=map(int,input().split())
  x=math.gcd(abs(a),abs(b))
  if a==0:
    if b==0:
      k=(0,0)
    else:
      k=(0,1)
  elif b==0:
    k=(1,0)
  else:
    if a<0:
      a,b=-a,-b
    if b<0:
      a,b=a//x,-((-b)//x)
    else:
      a,b=a//x,b//x
    k=(a,b)
  d[k]+=1

ind=defaultdict(int)
index=1
_ans=[1]
for a,b in list(d.keys()):
  if a==b==0:
    continue
  if b<=0:
    _k=(-b,a)
  else:
    _k=(b,-a)
  if d[_k]==0:
    _ans[0]*=pow(2,d[(a,b)])
  else:
    if ind[_k]==0:
      _ans.append(pow(2,d[(a,b)],MOD))
      ind[(a,b)]=index
      index+=1
    else:
      _ans[ind[_k]]+=pow(2,d[(a,b)],MOD)-1
ans=1
for a in _ans:
  ans=ans*a%MOD
print((d[(0,0)]+ans-1+MOD)%MOD)

Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Wrong Answer

Accepted