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:
# 解説AC
from math import gcd
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

mod = 10 ** 9 + 7
n = int(input())
cnt = 0
cnt += n
zerocnt = 0
kumi = defaultdict(int)
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zerocnt += 1
        continue
    elif b == 0:
        kumi[(1, 0)] += 1
        kumi[(0, -1)] += 0
        continue
    elif a == 0:
        kumi[(0, -1)] += 1
        kumi[(1, 0)] += 0
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        a *= -1
        b *= -1
    kumi[(a, b)] += 1
    kumi[(b, -a)] += 0
ans = 1
cnt -= zerocnt
for a, b in kumi.keys():
    if b <= 0:
        continue
    s = kumi[(a, b)]
    t = kumi[(b, -a)]
    ans *= pow(2, (s + t), mod) - (pow(2, s, mod) - 1) * (pow(2, t, mod) - 1)
    ans %= mod
    cnt -= s + t
if cnt > 0:
    ans *= pow(2, cnt, mod)
    ans %= mod
print((ans - 1) % mod)

Submission status: Wrong Answer

Solution code:
# 解説AC
from math import gcd
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

mod = 10 ** 9 + 7
n = int(input())
cnt = 0
cnt += n
zerocnt = 0
kumi = defaultdict(int)
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zerocnt += 1
        continue
    elif b == 0:
        kumi[(1, 0)] += 1
        continue
    elif a == 0:
        kumi[(0, -1)] += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        a *= -1
        b *= -1
    kumi[(a, b)] += 1
ans = 1
cnt -= zerocnt
for a, b in kumi.keys():
    if b <= 0:
        continue
    s = 0
    t = 0
    if (a, b) in kumi:
        s += kumi[(a, b)]
    else:
        continue
    if (b, -a) in kumi:
        t = kumi[(b, -a)]
    else:
        continue
    ans *= pow(2, (s + t), mod) - (pow(2, s, mod) - 1) * (pow(2, t, mod) - 1)
    ans %= mod
    cnt -= s + t
if cnt > 0:
    ans *= pow(2, cnt, mod)
    ans %= mod
print((ans - 1) % mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in range (N)]
MOD = 10**9+7

from collections import defaultdict
dnums = defaultdict(int)
dnums2 = defaultdict(int)
num_zero = 0
num_az = 0
num_bz = 0
keys = set()
for a,b in AB:
    if a!=0 and b!=0:
        dnums[b/a] += 1
        keys.add(b/a)
        dnums2[-a/b] += 1
    elif a==0 and b==0:
        num_zero += 1
    elif a == 0 and b!=0:
        num_az += 1
    elif a != 0 and b==0:
        num_bz += 1

mydict = dict()
for key in list(keys):
    mydict[key] = False

ans = 1
for key in list(keys):
    if mydict[key]:
        continue
    if -1/key in keys:
        mydict[-1/key] = True
        mydict[key] = True

    ans *= pow(2, dnums[key], MOD) + pow(2, dnums2[key], MOD) - 1

ans *= pow(2, num_az, MOD) + pow(2, num_bz, MOD) - 1
ans += num_zero
ans += MOD - 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
# 解説AC
from math import gcd
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline

mod = 10 ** 9 + 7
n = int(input())
cnt = 0
cnt += n
zerocnt = 0
kumi = defaultdict(int)
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zerocnt += 1
        continue
    elif b == 0:
        kumi[(1, 0)] += 1
        continue
    elif a == 0:
        kumi[(0, -1)] += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        a *= -1
        b *= -1
    kumi[(a, b)] += 1
ans = 1
cnt -= zerocnt
for a, b in kumi.keys():
    if b <= 0:
        continue
    s = 0
    t = 0
    if (a, b) in kumi:
        s += kumi[(a, b)]
    if (b, -a) in kumi:
        t = kumi[(b, -a)]
    ans *= pow(2, (s + t), mod) - (pow(2, s, mod) - 1) * (pow(2, t, mod) - 1)
    ans %= mod
    cnt -= s + t
if cnt > 0:
    ans *= pow(2, cnt, mod)
    ans %= mod
print((ans - 1) % mod)

Submission status: Wrong Answer

Solution code:
import sys,math,bisect
input = sys.stdin.readline

mod = 1000000007
eps = 0.0000000000001

n = int(input())

ab = []
ang = []
half = math.pi/2.0
zero = 0

for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        ang.append(half)
    else:
        ang.append(math.atan(b/a))
ang.sort()

n -= zero

res = 1
rest = n

i = 0
while True:
    if i >= n:
        break
    val = ang[i]
    if val > 2*eps:
        break
    cnt = bisect.bisect_right(ang,val+eps) - i
    cnt2 = bisect.bisect_right(ang,val+half+eps) - bisect.bisect_left(ang,val+half-eps)
    if cnt2 > 0:
        rest = rest - cnt - cnt2
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
    i += cnt
rest = max(rest,0)
res = res*pow(2,rest,mod)%mod - 1 + zero
print(res%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

ab = set()
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    if a < 0:
        a, b = -a, -b
    ab.add((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
if (0, 0) in ab:
    ab.remove((0, 0))

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

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in range (N)]
MOD = 10**9+7

from collections import defaultdict
from math import gcd
def cmp(x,y):
    g = gcd(abs(x),abs(y))
    if x*y<0:
        return (-abs(x)//g, abs(y)//g)
    else:
        return (abs(x)//g, abs(y)//g)
def rev(x):
    # x = (a,b)
    # ret = (-b,a)
    a = x[0]
    b = x[1]
    if a<0:
        return (abs(b), abs(a))
    else:
        return (-abs(b), abs(a))

dnums = defaultdict(int)
dnums2 = defaultdict(int)
num_zero = 0
num_az = 0
num_bz = 0
keys = set()
for a,b in AB:
    if a!=0 and b!=0:
        k1 = cmp(a,b)
        dnums[k1] += 1
        keys.add(k1)
    elif a==0 and b==0:
        num_zero += 1
    elif a == 0 and b!=0:
        num_az += 1
    elif a != 0 and b==0:
        num_bz += 1

mydict = dict()
for key in list(keys):
    mydict[key] = False

ans = 1
for key in list(keys):
    if mydict[key]:
        continue
    rkey = rev(key)
    if rkey in keys:
        mydict[rev(key)] = True
        mydict[key] = True

    if dnums[rkey] != 0:
        ans *= pow(2, dnums[key], MOD) + pow(2, dnums[rkey], MOD) - 1
    else:
        ans *= 2
    ans %= MOD
    
ans *= pow(2, num_az, MOD) + pow(2, num_bz, MOD) - 1
ans += num_zero
ans += MOD - 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = [list(map(int,input().split())) for _ in range (N)]
MOD = 10**9+7

from collections import defaultdict
from math import gcd
def cmp(x,y):
    g = gcd(abs(x),abs(y))
    if x*y<0:
        return (-abs(x)//g, abs(y)//g)
    else:
        return (abs(x)//g, abs(y)//g)
def rev(x):
    # x = (a,b)
    # ret = (-b,a)
    a = x[0]
    b = x[1]
    if a<0:
        return (abs(b), abs(a))
    else:
        return (-abs(b), abs(a))

dnums = defaultdict(int)
dnums2 = defaultdict(int)
num_zero = 0
num_az = 0
num_bz = 0
keys = set()
for a,b in AB:
    if a!=0 and b!=0:
        k1 = cmp(a,b)
        dnums[k1] += 1
        keys.add(k1)
        k2 = cmp(-b,a)
        dnums2[k2] += 1
    elif a==0 and b==0:
        num_zero += 1
    elif a == 0 and b!=0:
        num_az += 1
    elif a != 0 and b==0:
        num_bz += 1

mydict = dict()
for key in list(keys):
    mydict[key] = False

ans = 1
for key in list(keys):
    if mydict[key]:
        continue
    if rev(key) in keys:
        mydict[rev(key)] = True
        mydict[key] = True

    if dnums2[key] != 0:
        ans *= pow(2, dnums[key], MOD) + pow(2, dnums2[key], MOD) - 1
    else:
        ans *= 2

ans *= pow(2, num_az, MOD) + pow(2, num_bz, MOD) - 1
ans += num_zero
ans += MOD - 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

ab = set()
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    if b < 0:
        a, b = -a, -b
    ab.add((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
if (0, 0) in ab:
    ab.remove((0, 0))

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

ab = set()
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    if b < 0:
        a, b = -a, -b
    ab.add((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
if (0, 0) in ab:
    ab.remove((0, 0))

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

Submission status: Wrong Answer

Solution code:
from math import gcd

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

ab = set()
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    if b < 0:
        a, b = -a, -b
    ab.add((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1
if (0, 0) in ab:
    ab.remove((0, 0))

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

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
#import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
def main():
  ans=1
  mod=1000000007
  n0=0
  na=nb=0
  n=int(input())
  d={}

  for i in range(n):
      a,b=map(int,input().split())
      if b==0 and a==0:
          n0+=1
      elif b==0:
          nb+=1
      elif a==0:
          na+=1
      else:
          if Fraction(a, b) not in d:
              d[Fraction(a, b)]=1
          else:
              d[Fraction(a, b)]+=1

  for i in d.keys():
      if Fraction(-1,i) in d:
          if i>0:
              ans*=pow(2,d[Fraction(-1, i)])-1+pow(2,d[i])-1+1
              ans=ans%mod
      else:
          ans*=pow(2,d[i])
          ans=ans%mod
  ans*=pow(2,na)-1+pow(2,nb)-1+1
  print((ans-1)%mod)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
#import numpy as np
#import math
from fractions import Fraction
import itertools

input=sys.stdin.readline

ans=1
mod=10**9+7
n0=0
na=nb=0
n=int(input())
d={}
for i in range(n):
    a,b=map(int,input().split())
    if b==0 and a==0:
        n0+=1
    elif b==0:
        nb+=1
    elif a==0:
        na+=1
    else:
        if Fraction(a, b) not in d:
            d[Fraction(a, b)]=1
        else:
            d[Fraction(a, b)]+=1
            
for i in d.keys():
    if Fraction(-1,i) in d:
        if i>0:
        	ans*=pow(2,d[Fraction(-1, i)])-1+pow(2,d[i])-1+1
        	ans=ans%mod
    else:
        ans*=pow(2,d[i])
        ans=ans%mod
ans*=pow(2,na)-1+pow(2,nb)-1+1
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import math

def m(L):
    (a,b)=L
    g=math.gcd(a,b)
    
    if b==0:
        return (1,0)
    elif b>0:
        return (a//g,b//g)
    else:
        return (-a//g,-b//g)

def w(x,y):
    if x==0:
        return 2**y
    elif y==0:
        return 2**x
    else:
        return 2**x+2**y-1
    
N=int(input())
D=[]
for i in range(N):
    (A,B)=map(int,input().split())
    D.append((A,B))

M=list(map(m,D))

O=0
if (0,0) in M:
    M.remove((0,0))
    O+=1
    
J={}

for m in M:
    if m in J:
        J[m]+=1
    else:
        J[m]=1

K={}
for u in J:
    (a,b)=u
    p=J[u]
    
    if a>=0:
        (c,d)=(-b,a)
    else:
        (c,d)=(b,-a)

    f=True
    if (a,b) in K:
        (x,y)=K[(a,b)]
        if a>=0:
            x+=p
        else:
            y+=p
        K[(a,b)]=(x,y)
        f=False

    elif f and ((c,d) in K):
        (x,y)=K[(c,d)]
        if c<=0:
            x+=p
        else:
            y+=p
        K[(c,d)]=(x,y)
        f=False
        
    elif f:
        if a>=0:
            K[(a,b)]=(p,0)
        else:
            K[(a,b)]=(0,p)

G=[w(x,y) for (x,y) in K.values()]

r=1
V=1000000007
for g in G:
    r=(r*g)%V

print(r-1+O)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

n = int(input())

zeros = 0
d = defaultdict(lambda: [0, 0])
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
        continue
    g = gcd(a, b)
    a, b = a // g, b // g
    if a == 0:
        b = 1
    if b == 0:
        a = 1
    if b < 0:
        a, b = -a, -b
    if a <= 0:
        d[(b, -a)][1] += 1
    else:
        d[(a, b)][0] += 1


mod = 1000000007
ans = 1
for v in d.values():
    ans = ans * (pow(2, v[0], mod) + pow(2, v[1], mod) - 1) % mod

ans = ans - 1 + zeros
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

n = int(input())

zeros = 0
d = defaultdict(lambda: [0, 0])
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
        continue
    g = gcd(a, b)
    a, b = a // g, b // g
    if a == 0:
        b = 1
    if b == 0:
        a = 1
    if b < 0:
        a, b = -a, -b
    if a < 0:
        d[(b, -a)][1] += 1
    else:
        d[(a, b)][0] += 1


mod = 1000000007
ans = 1
for v in d.values():
    ans = ans * (pow(2, v[0], mod) + pow(2, v[1], mod) - 1) % mod

ans = ans - 1 + zeros
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
n=int(input())
m=[]
groups=[]
INF=10**27
a0only=0
b0only=0
both0=0
negativecounter=0
for i in range(n):
  a,b=map(int,sys.stdin.readline().split())
  if b==0:
    if a==0:
      both0+=1
    else:
      b0only+=1
  elif a==0:
    a0only+=1
  else:
    m.append([a,b,a/b,-b/a])
  if a*b<0:
    negativecounter+=1
m1=sorted(m, key=lambda student: student[2])
m2=sorted(m, key=lambda student: student[3])
backcounter=0
done=set()
for i in range(len(m)):
  a=m1[i][0]
  b=m1[i][1]
  if len(groups)>0:
    if groups[-1][0]*b==a*groups[-1][1]:
      groups[-1][2]+=1
    else:
      if i in done:
        groups.append([a,b,1,0,0])
      else:
       	groups.append([a,b,1,0,-1])
  else:
    if i in done:
      groups.append([a,b,1,0,0])
    else:
      groups.append([a,b,1,0,-1])
  backcounter=max(0,backcounter-100)
  while backcounter<len(m) and ((a*m2[backcounter][0]>=-b*m2[backcounter][1] and b*m2[backcounter][0]>0) or (a*m2[backcounter][0]<=-b*m2[backcounter][1] and b*m2[backcounter][0]<0)):
    if m2[backcounter][0]*a+m2[backcounter][1]*b==0:
      groups[-1][3]+=1
      groups[-1][4]=0
    backcounter+=1
ans=1
donenumbers=[0]*len(groups)
for i in range(len(groups)):
  a=groups[i][0]
  b=groups[i][1]
  c=groups[i][2]
  d=groups[i][3]
  if groups[i][4]==0 and a*b<0:
    continue
  ans=(ans*((2**c+2**d)-1))%(10**9+7)
ans=(ans*(((2**a0only+2**b0only)-1+both0))%(10**9+7))
print((ans-1)%(10**9+7))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd

def main():
    N = int(input())
    MOD = 10 ** 9 + 7
    zero = 0
    d = defaultdict(lambda: defaultdict(int))
    for i in range(N):
        A, B = map(int, input().split())
        if A == 0 and B == 0:
            zero += 1
            continue
        if B <= 0:
            A = -A
            B = -B
        flag = False
        if A <= 0:
            A, B = B, -A
            flag = True
        g = gcd(A,B)
        A //= g
        B //= g
        if flag:
            d[(A,B)]['first'] += 1
        else:
            d[(A,B)]['second'] += 1
    ans = 1
    for i, j in d.items():
        now = 1
        now += pow(2,j['first'],MOD) - 1
        now += pow(2,j['second'],MOD) - 1
        ans *= now
        ans %= MOD
    ans -= 1
    ans += zero
    ans %= MOD
    print(ans)




    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1 if a*b < 0 else 0
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans = pow(2, n - (used_cnt), mod) % mod # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math

double_zero_cnt = 0 # [0, 0]の個数
a_b = [] # a/bを、約分した形で保持(a/gcd(a, b), b/gcd(a, b), 符号)
for a, b in ab:
    if a == 0 and b == 0: 
        double_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    sign = 1 if a*b > 0 else -1
    a_b.append((abs(a), abs(b), sign))

c = Counter(a_b) # ベクトルごとにグループ分け
key_list = list(c.keys())

d = defaultdict(list) # [a, b] あるngなペアのそれぞれの要素の個数
for key in key_list:
    a, b, sign = key
    if d[(b, a, -sign)]: # ダブルカウントしないように
        continue 
    if c[(b, a, -sign)] != 0:
        d[(a, b, sign)] = [c[(a, b, sign)], c[(b, a, -sign)]]

ans = 1 # 積算の単位元
used_cnt = double_zero_cnt # 組めないものがあるイワシの個数
for key in d.keys():
    if d[key] == []: # 前のループで調べると[]が生まれてしまう
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod # このグループからは、片方ずつからしか出せない。何も選ばないがダブルカウントになる。
    ans *= mul
    ans %= mod

ans *= pow(2, n - (used_cnt), mod) # まだ使われていないイワシは好きな組み合わせ可能
ans += double_zero_cnt # 両方0のものは1つにつき自分のみの1通り
ans -= 1 # 0匹は選べない
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from math import gcd

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = int(read())
    mod = 1000000007
    a = defaultdict(int)
    for _ in range(n):
        _a, _b = map(int, read().split())
        if _a == 0 and _b == 0:
            continue
        _g = gcd(_a, _b)
        if _a == 0:
            _b = 1
            _g = 1
        elif _b == 0:
            _a = 1
            _g = 1
        elif _a < 0:
            _a = -_a
            _b = -_b
        a[(_a // _g, _b // _g)] += 1
    keys = a.keys()
    p = 0
    t = []
    s = set()
    for _a, _b in keys:
        if (_a, _b) in s:
            continue
        if _a == 0 and ((1, 0) in keys):
            t.append((a[(0, 1)], a[1, 0]))
            s.add((0, 1))
            s.add((1, 0))
        elif _b > 0 and ((_b, -_a) in keys):
            t.append((a[(_a, _b)], a[(_b, -_a)]))
            s.add((_a, _b))
            s.add((_b, -_a))
        elif _b < 0 and ((-_b, _a) in keys):
            t.append((a[(_a, _b)], a[(-_b, _a)]))
            s.add((_a, _b))
            s.add((-_b, _a))
        else:
            p += a[(_a, _b)]
    c = pow(2, p, mod)
    for ta, tb in t:
        c = c * (pow(2, ta, mod) + pow(2, tb, mod) - 1) % mod
    print(c - 1)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import defaultdict
MOD = 10**9+7
n = int(input())
cnt = defaultdict(lambda: [0, 0])
zeros = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    if a < 0:
        a *= -1
        b *= -1
    g = gcd(a, b)
    a //= g
    b //= g
    if b > 0:
        cnt[(a, b)][0] += 1
    else:
        cnt[(-b, a)][1] += 1

ans = 1
for v, v2 in cnt.values():
    ans *= 1+pow(2, v, MOD)-1+pow(2, v2, MOD)-1
    ans %= MOD
ans = (ans+zeros-1) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import copy
from collections import defaultdict

def preproc(a,b): # a != 0 or b != 0
    if a < 0:
        a,b = -a,-b
    if a == 0 or b == 0:
        return (a, b)
    GCD = math.gcd(a,b)
    return (a // GCD, b // GCD)

n = int(input())
ab = [list(map(int, input().split())) for i in range(n)]
mod = 1000000007
ans = 0
dic = defaultdict(int)
dic2 = dict()
A = 0
B = 0
for k,(a,b) in enumerate(ab):
    if a == 0 and b == 0:
        n -= 1
        continue
    a,b = preproc(a,b)
    if a == 0:
        A += 1
        n -= 1
    elif b == 0:
        B += 1
        n -= 1
    else:
        dic[(a,b)] += 1
ok = (pow(2,A,mod) + pow(2,B,mod) - 1) % mod
c = copy.copy(dic)
for k,v in c.items():
    if not dic[k]:
        continue
    a,b = k
    pair = (b,-a) if b > 0 else (-b,a)
    if dic[pair]:
        ok *= pow(2,v,mod) + pow(2,dic[pair],mod) - 1
        ok %= mod
        n -= v + dic[pair]
        dic[pair] = 0
ans = ok * pow(2,n,mod) - 1
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
mod = 10**9 + 7
n = int(input())
ab = [[int(x) for x in input().split()] for _ in range(n)]
from collections import defaultdict, Counter
import math
double_zero_cnt = 0
a_zero_cnt = 0
b_zero_cnt = 0
d = defaultdict(list) # [a, b] ngのそれぞれの個数
a_b = []
for a, b in ab:
    if a == 0 and b == 0:
        double_zero_cnt += 1
        continue
    elif a == 0:
        a_zero_cnt += 1
        continue
    elif b == 0:
        b_zero_cnt += 1
        continue
    g = math.gcd(a, b)
    a //= g
    b //= g
    if b < 0:
        b *= (-1)
        a *= (-1) # 必ずbは正
    a_b.append((a, b))
c = Counter(a_b)
key_list = list(c.keys())
for key in key_list:
    a, b = key
    if a < 0:
        a *= (-1)
        b *= (-1)
    if d[(-b, a)] != []:
        continue
    if c[(-b, a)] != 0:
        d[(a, b)] = [c[(a, b)], c[(-b, a)]]
ans = 1
used_cnt = double_zero_cnt
for key in d.keys():
    if d[key] == []:
        continue
    x, y = d[key]
    used_cnt += (x + y)
    mul = (pow(2, x, mod) + pow(2, y, mod) - 1) % mod
    ans *= mul
    ans %= mod
if a_zero_cnt > 0 and b_zero_cnt > 0:
    ans *= (pow(2, a_zero_cnt, mod) + pow(2, b_zero_cnt, mod) - 1)
    ans %= mod
    used_cnt += a_zero_cnt + b_zero_cnt
elif a_zero_cnt > 0:
    ans *= pow(2, a_zero_cnt, mod)
    ans %= mod
    used_cnt += a_zero_cnt
elif b_zero_cnt > 0:
    ans *= pow(2, b_zero_cnt, mod)
    ans %= mod
    used_cnt += b_zero_cnt
if n - (used_cnt) >= 0:
    ans *= pow(2, n - (used_cnt), mod)
    ans %= mod
ans -= 1
ans += double_zero_cnt
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd
from fractions import Fraction

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    inf = 10**18+1
    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue
        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai*bi < 0
        if ai < 0:
            ai, bi = -ai, -bi
        elif ai == 0 and bi > 0:
            bi = -bi
            t = True

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai) if bi >= 0 else (-bi, ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v+v2, mod) - (pow(2, v, mod)-1)*(pow(2, v2, mod)-1)
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        ans *= pow(2, v, mod)
        ans %= mod

    print(ans-1+z0)



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd
from fractions import Fraction

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = input()
    it = map(int, sys.stdin.read().split())
    mod = 10**9 + 7

    inf = 10**18+1
    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for i, (ai, bi) in enumerate(zip(it, it)):
        if ai == 0 and bi == 0:
            z0 += 1
            continue
        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai*bi < 0
        if ai < 0:
            ai, bi = -ai, -bi
        elif ai == 0 and bi > 0:
            bi = -bi
            t = True

        d1[t][(ai, bi)] += 1


    a1, a2 = d1
    ans = 1
    for (ai, bi), v in a1.items():
        k2 = (bi, -ai)
        if k2 in a2:
            v2 = a2[k2]
            ans *= pow(2, v+v2, mod) - (pow(2, v, mod)-1)*(pow(2, v2, mod)-1)
        else:
            ans *= pow(2, v, mod)
        ans %= mod

    for (ai, bi), v in a2.items():
        k2 = (-bi, ai)

        if k2 in a1: continue

        ans *= pow(2, v, mod)
        ans %= mod

    print(ans-1+z0)



if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

mod=10**9+7
n=int(input())
fact=[1]
revfact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[-1],mod-2,mod))
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if (a>0 and b>0) or (a<0 and b<0):
      if (abs(a)//g,abs(b)//g) not in dic:
        dic[(abs(a)//g,abs(b)//g)]=1
      else:
        dic[(abs(a)//g,abs(b)//g)]+=1
    elif (a>0 and b<0) or (a<0 and b>0):
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]+=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a*b!=0:
    if a>0:
      if (-b,a) in dic:
        s.add((-b,a))
        cnt1=dic[(a,b)]
        cnt2=dic[(-b,a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
    elif a<0:
      if (b,-a) in dic:
        s.add((b,-a))
        cnt1=dic[(a,b)]
        cnt2=dic[(b,-a)]
        tmp=1
        for i in range(1,cnt1+1):
          tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
        for i in range(1,cnt2+1):
          tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
        ans*=tmp
        ans%=mod
      else:
        ans*=pow(2,dic[(a,b)])
        ans%=mod
  else:
    if (b,a) in dic:
      s.add((b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,a)]
      tmp=1
      for i in range(1,cnt1+1):
        tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
      for i in range(1,cnt2+1):
        tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
      ans*=tmp
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
print(ans+cnt-1)