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 Counter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    MOD = 10**9 + 7

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

    def gcd(a, b):
        while b:
            a, b = b, a%b
        return a

    cntPos = Counter()
    cntNeg = Counter()
    num00 = 0
    for A, B in ABs:
        if A == B == 0:
            num00 += 1
            continue
        if A == 0:
            cntNeg[(0, 1)] += 1
        elif B == 0:
            cntPos[(0, 1)] += 1
        else:
            isPN = A*B < 0
            A, B = abs(A), abs(B)
            g = gcd(A, B)
            A, B = A//g, B//g
            if isPN:
                cntNeg[(B, A)] += 1
            else:
                cntPos[(A, B)] += 1

    numPoss = []
    numNegs = []

    numIso = 0
    for key in set(cntPos.keys()) | set(cntNeg.keys()):
        if cntPos[key] > 0 and cntNeg[key] > 0:
            numPoss.append(cntPos[key])
            numNegs.append(cntNeg[key])
        else:
            numIso += cntPos[key] + cntNeg[key]

    M = len(numPoss)
    numAlls = [0] * M
    numOKs = [0] * M
    numNGs = [0] * M
    for i in range(M):
        numPos = numPoss[i]
        numNeg = numNegs[i]
        numAll = pow(2, numPos+numNeg, MOD)
        numOK = pow(2, numPos, MOD) + pow(2, numNeg, MOD) - 1
        numNG = numAll - numOK
        numAlls[i] = numAll
        numOKs[i] = numOK
        numNGs[i] = numNG

    acc = pow(2, numIso, MOD)
    accNumAlls = [acc]
    for i in reversed(range(M)):
        acc *= numAlls[i]
        acc %= MOD
        accNumAlls.append(acc)
    accNumAlls.reverse()

    N -= num00
    ans = pow(2, N, MOD) - 1
    accOK = 1
    for i in range(M):
        num = accOK * numNGs[i] * accNumAlls[i+1] % MOD
        ans -= num
        ans %= MOD
        accOK *= numOKs[i]

    print(ans)


solve()

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
 
 
 
a = int(input())
resab = dict()
resba = dict()
res0 = 0
res0a = 0
res0b = 0
 
for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        s = Fraction(ai, bi)
        if Fraction(ai, bi) not in resab:
            resab[s] = 1
        else:
            resab[s] += 1
        b = Fraction(-s.denominator, s.numerator)
        if b not in resba:
            resba[b] = 1
        else:
            resba[b] += 1
    else:
        if ai == 0 and bi == 0:
            res0 += 1
        elif ai == 0:
            res0a += 1
        elif bi == 0:
            res0b += 1
 

ans = 1
for i in list(resab.keys()):
    if i in resba and i in resab:
        ans *= (2**resab[i] - 1 + 2**resba[i]) 
        #print(ans, i)
        del resab[i]
        del resab[Fraction(-i.denominator, i.numerator)]
        del resba[i]
        del resba[Fraction(-i.denominator, i.numerator)]
    elif i in resba:
        ans *= resba[i] + 1
        #print(ans, i)
        del resba[i]
        try:
            del resab[Fraction(-i.denominator, i.numerator)]
        except:
            pass
    elif i in resab:
        ans *= resab[i] + 1
        #print(ans, i)
        del resab[i]
        try:
            del resba[Fraction(-i.denominator, i.numerator)]
        except:
            pass
        
    ans %= 1000000007
 
ans *= (2 ** res0a)
ans *= (2 ** res0b)
ans *= (res0 + 1)
ans -= 1
ans %= 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l=[list(map(int, input().split())) for _ in range(n)]
cnt=0
for i in range(n-1):
    for j in range(i+1, n):
        if l[i][0]*l[j][0]+l[i][1]*l[j][1] == 0:
            cnt+=1

print((2**n-1-2**(n-2))%1000000007)

Submission status: Wrong Answer

Solution code:
import math

def make_key(a, b):
    if a == 0:
        return (0, 1)
    elif b == 0:
        return (1, 0)
    g = math.gcd(a, b)
    a //= g
    b //= g
    # make sure a is always positive
    if a < 0:
        a *= -1
        b *= -1
    return (a, b)


def main():
    MOD = 1000000007

    N = int(input())
    keys = [make_key(*[int(x) for x in input().split()]) for _ in range(N)]

    import collections
    count = collections.Counter(keys)
    seen = set()

    # find pairs
    pairs = []
    num = N
    for key in count.keys():
        if key in seen:
            continue
        okey = make_key(key[1], -key[0])
        if okey in count:
            seen.add(key)
            seen.add(okey)
            n1 = count[key]
            n2 = count[okey]

            num -= (n1+n2)
            pairs.append((n1, n2))

    ans = pow(2, num, MOD)
    for n1, n2 in pairs:
        num = ans
        ans += (pow(2, n1, MOD)-1) * num
        ans %= MOD
        ans += (pow(2, n2, MOD)-1) * num
        ans %= MOD
        # ans += num
        # ans %= MOD
    ans -= 1
    ans %= MOD

    print(ans)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        ratios.append((0, 0))
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))

twos = [1]
for i in range(2 * 10 ** 5):
    tmp = twos[-1] * 2
    tmp %= mod
    twos.append(tmp)


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    yy = seen[(-y, x)] + seen[(y, -x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = twos[n_frees]

for x, y in targets:
    ans *= (twos[x] + twos[y] - 1) % mod

print(ans % mod - 1)

Submission status: Wrong Answer

Solution code:

from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
            break
        if a == 0:
            a_0 += 1
        if b == 0:
            b_0 += 1
        break
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a0 + b0
    lst.append([a0, b0])
n -= a_b_0
ans = pow(2, n - total, mod)
tmp = 1
for a, b in lst:
    tmp *= pow(2, a, mod) + pow(2, b, mod) - 1
ans = (ans * tmp - 1 + a_b_0) % mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
 
 
 
a = int(input())
resab = dict()
resba = dict()
res0 = 0
res0a = 0
res0b = 0
 
for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        s = Fraction(ai, bi)
        if Fraction(ai, bi) not in resab:
            resab[s] = 1
        else:
            resab[s] += 1
        b = Fraction(-bi, ai)
        if b not in resba:
            resba[b] = 1
        else:
            resba[b] += 1
    else:
        if ai == 0 and bi == 0:
            res0 += 1
        elif ai == 0:
            res0a += 1
        elif bi == 0:
            res0b += 1
 

ans = 1
for i in list(resab.keys()):
    if i in resba and i in resab:
        ans *= (2**resab[i] - 1 + 2**resba[i]) 
        #print(ans, i)
        del resab[i]
        del resab[Fraction(-i.denominator, i.numerator)]
        del resba[i]
        del resba[Fraction(-i.denominator, i.numerator)]
    elif i in resba:
        ans *= resba[i] + 1
        #print(ans, i)
        del resba[i]
        try:
            del resab[Fraction(-i.denominator, i.numerator)]
        except:
            pass
    elif i in resab:
        ans *= resab[i] + 1
        #print(ans, i)
        del resab[i]
        try:
            del resba[Fraction(-i.denominator, i.numerator)]
        except:
            pass
        
    ans %= 1000000007
 
ans *= (2 ** res0a)
ans *= (2 ** res0b)
ans *= (res0 + 1)
ans -= 1
ans %= 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

def gcd(a, b) :
  if b > a : 
    a, b = b, a
  
  while b != 0 :
    a, b = b, a % b
  return a

p = []
both = 0
zeroa = 0
zerob = 0
for a, b in AB :
  if a == 0 and b == 0 :
    both += 1
    continue
  elif a == 0 :
    zeroa += 1
    continue
  elif b == 0 :
    zerob *= 1
    continue
    
  g = gcd(abs(a), abs(b))
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) + pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

ret *= both + pow(2, zeroa, mod) + pow(2, zerob, mod) - 1
ret %= mod

print((ret - 1) % mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import collections
MOD = 1000000007
INF = 10 ** 100

n = int(input())
ratio = []
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        ratio.append(INF)
    else:
        ratio.append(b/a)

ratio = collections.Counter(ratio)

ans = 1
done = set()
flag = True
for key, value in ratio.items():
    if key == 0:
        key2 = INF
    elif key == INF:
        key2 = 0
    else:
        key2 = -1 / key
    if key2 in done:
        continue

    value2 = ratio[key2]
    if value2 == 0:
        ans *= pow(2, value, MOD)
        flag = False
    else:
        ans *= pow(2, value, MOD) + pow(2, value2, MOD) - 1
        done.add(key)
    ans %= MOD

if flag:
    print(ans)
else:
    print(ans - 1)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
for n in range(N):
    a,b = map(float,input().split())

    if a==0 and b==0:
        continue
    if a==0:
        n_sign = 0
    elif b==0:
        n_sign = 1
    
    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        # gcd = math.gcd(a,b)
        # a//=gcd
        # b//=gcd
        

        #print(n_sign,a,b)
    # print(n_sign,a,b)


    if n_sign==1:
        s =str(b/a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a/b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect
N=int(input())
L = [list(map(int,input().split())) for _ in range(N)]

MOD=10**9+7


L =sorted(L)

L_non_zero=[[a,b,i] for i,[a,b] in enumerate(L) if a*b!=0]
L_zero=[[a,b,i] for i,[a,b] in enumerate(L) if a*b==0]

D_AB=defaultdict(int)
D_BA=defaultdict(int)


A_B=[]
B_A=[]
for a,b,i in L_non_zero:
    D_AB[a/b]+=1
    D_BA[b/a]+=1
    A_B.append([a/b,i])
    B_A.append([b/a,i])


ans=pow(2,N,MOD)-1

ans=1
used_key=set()
NG=[]
NG_each=len(L_zero)
for key,val in D_AB.items():
    if key in used_key:
        continue
    else:
        used_key.add(key)
        used_key.add(-1/key)
    val_other=D_BA[-key]

    if val_other==0:
        ans*=pow(2,val,MOD)
    else:
        ans*=((pow(2,val,MOD)-1)+(pow(2,val_other,MOD)-1)+1)
if NG_each>0:
    ans*=NG_each
print((ans-1+MOD)%MOD)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

read = sys.stdin.read
MOD = 10**9 + 7

n = int(input())
ab = np.array(read().split(), dtype=np.float64).reshape([-1,2])
a = ab[:,0]
b = ab[:,1]
c =  a/b
ans = 0
for i in range(n-1):
    ans += pow(2,np.count_nonzero((c*c[i] != -1)[i+1:]), MOD)
    ans %= MOD
ans += 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    return gcd(b,a%b) if b else a
n = int(input())
freq = {}
ans = 1
add = -1
for i in range(n):
    a,b=map(int, input().strip().split())
    if not (a or b):
        add += 1
        continue
    if not a:
        b = 1
    elif not b:
        a = 1
    else:
        if b < 0: a,b=-a,-b
        c = gcd(abs(a),b)
        a //= c; b //= c
        t = (a,b)
        if t not in freq:
            freq[t] = 1
        else:
            freq[t] += 1
mod = 1000000007
vis = set()
for i in freq:
    if i in vis: continue
    vis.add(i)
    a,b=i
    t = (b,-a) if a<=0 else (-b,a)
    if t in freq:
        vis.add(t)
        ans = ans*(pow(2,freq[t],mod)+pow(2,freq[i],mod)-1)%mod
    else:
        ans = ans*pow(2,freq[i],mod)%mod
print((ans+add)%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

def gcd(a, b) :
  if b > a : 
    a, b = b, a
  
  while b != 0 :
    a, b = b, a % b
  return a

p = []
both = 0
zeroa = 0
zerob = 0
for a, b in AB :
  if a == 0 and b == 0 :
    both += 1
    continue
  elif a == 0 :
    zeroa += 1
  elif b == 0 :
    zerob *= 1
    
  g = gcd(abs(a), abs(b))
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) + pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

ret *= both + pow(2, zeroa, mod) + pow(2, zerob, mod) - 1
ret %= mod

print((ret - 1) % mod)

Submission status: Wrong Answer

Solution code:

from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
            break
        if a == 0:
            a_0 += 1
        if b == 0:
            b_0 += 1
        break
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 * b_0 != 0:
    total += a0 + b0
    lst.append([a0, b0])
n -= a_b_0
ans = pow(2, n - total, mod)
tmp = 1
for a, b in lst:
    tmp *= pow(2, a, mod) + pow(2, b, mod) - 1
ans = (ans * tmp - 1 + a_b_0) % mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
ab = [tuple(map(int,input().split())) for i in range(n)]
mod = 10 ** 9 + 7
cnt = defaultdict(lambda :0)

for i in range(n):
    temp = ab[i]
    cnt[temp] = 1

check = defaultdict(lambda :0)
for key in ab:
    a, b = key
    if cnt[(b, -a)]:check[key] += 1
    if cnt[(-b, a)]:check[key] += 1

num = n
ans = 0
for key in ab:
    k = num - check[key] if check[key] > 0 else num
    #print(key, ans, num, k)
    if k > 0:
        ans = (ans + pow(2, k, mod) - pow(2, k - 1, mod)) % mod
    check[(key[1], -key[0])] -= 1
    check[(-key[1], key[0])] -= 1
    num -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        continue
    if a==0:
        n_sign = 0
    elif b==0:
        n_sign = 1
    
    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        # gcd = math.gcd(a,b)
        # a//=gcd
        # b//=gcd
        

        #print(n_sign,a,b)
    # print(n_sign,a,b)


    if n_sign==1:
        s =str(b/a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a/b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
ans -= 1
ans %= MOD
print (ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    if Btmp!=0:
        AB.append(Atmp/Btmp)
    else:
        AB.append(float('inf')*Atmp*Btmp)

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

from collections import Counter
C = Counter(AB)

kaburi = []
forsum = []
for key in C:
    if key<0:
        if C[-1/key]!=0:
            kaburi.append([C[key],C[-1/key]])
            forsum.append(C[key]+C[-1/key])
    if key==0:
        if (C[float('inf')]!=0)or(C[-1*float('inf')]!=0) :
            kaburi.append([C[key],C[float('inf')]+C[-1*float('inf')]])
            forsum.append(C[key]+C[float('inf')]+C[-1*float('inf')])

p = 10**9+7

free = N-sum(forsum)
free2 = power_func(2,free,p)
L = len(kaburi)

out = 1
for i in range(len(kaburi)):
    X = kaburi[i][0]
    Y = kaburi[i][1]
    B = power_func(2,X,p)
    C = power_func(2,Y,p)
    out = out*((B+C-1)%p)
    out = out%p
print((out*free2-1)%p)

Submission status: Wrong Answer

Solution code:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


def compress(string):
    string.append(-2)
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans

  
from collections import defaultdict


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)
res1 = []
res2 = []
ind = []
cnt_00 = 0
cnt_a0 = 0
cnt_b0 = 0
for i in range(n):
    a, b = info[i]
    if a == 0 and b == 0:
        cnt_00 += 1
        continue
    if a == 0:
        cnt_a0 += 1
        continue
    if b == 0:
        cnt_b0 += 1
        continue
    res1.append(a / b)
    res2.append(- b / a)
    ind.append(i)

memo_r = defaultdict(int)
memo_l = defaultdict(int)

for i in range(len(res1)):
    l, r = res1[i], res2[i]
    memo_r[r] += 1
    memo_l[l] += 1

ans = 1
used = set()
for r in memo_r:
    if r in used:
        continue
    cnt_r = memo_r[r]
    cnt_l = 0
    if r in memo_l:
        cnt_l += memo_l[r]
    if r == -1.0 or r == 1.0:
        tmp = cnt_l + cnt_r + 1
    else:
        tmp = (pow(2, cnt_l, MOD) - 1) + (pow(2, cnt_r, MOD) - 1) + 1
    ans *= tmp
    used.add(-1 / r)

ans = ans + ans * cnt_a0 + ans * cnt_b0  + cnt_b0 * cnt_a0 * ans + cnt_00
print((ans - 1) % MOD)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
n=int(input())
p=[]
m=[]
for i in range(n):
    a,b=map(int,input().split())
    if a*b<0:
        m.append(a*b)
    else:
        p.append(a*b)
m.sort()
p=sorted(p,reverse=True)
r=0
l=0
cnt=0
while l<len(m) and r<len(p):
    if p[r]+m[l]>0:
        l+=1
    elif p[r]+m[l]<0:
        r+=1
    else:
        cnt+=1
        if len(m)-l<len(p)-r:
            r+=1
        else:
            l+=1

ans=(pow(2,n,MOD)-1-pow(2,n-2,MOD)*cnt)%MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections

n = int(input())
iwashi = [None for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    iwashi[i] = (math.degrees(math.atan2(a, b)) + 180) % 180
# print(iwashi)
iwashi = collections.Counter(iwashi)
k_list = list(iwashi.keys())
v = list(iwashi.values())
# k_list.sort(key=lambda x: -x)

mod = 1000000007
ans = 1
for k in k_list:
    a = iwashi[k]
    b = iwashi[k+90] + iwashi[k-90]
    if a*b != 0:
        ans *= (pow(2, a, mod) + pow(2, b, mod) -1)
    else:
        ans *= (a+1)
    iwashi[k] = 0
    iwashi[k+90] = 0
    iwashi[k-90] = 0
    # print(a, b, ans)
    ans %= mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            f = b / a
            if b / a < 0:
                m.append(-round(a / b, 6))
            elif f > 0:
                p.append(round(b / a, 6))
        else:
            m.append(0.0)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if k == 0.0:
            ans *= (g_m[k] + 1)
        elif not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=[0]*N
B=[0]*N
x=0
y=0
plus={}
ans=1
for i in range(N):
  a,b=map(int,input().split())
  A[i]=a
  B[i]=b
  if(a==0 and b!=0):
    x+=1
  elif(a!=0 and b==0):
    y+=1
  elif(a!=0 and b!=0):
    c=math.gcd(a**2-b**2,a*b)
    d=(a**2-b**2)//c
    e=(a*b)//c
    if(e<0):
      d*=-1
      e*=-1
    #print(d)
    #print(e)
    if((d,e) in plus):
      plus[(d,e)]+=1
    else:
      plus[(d,e)]=1
#print(plus)
#print(x)
#print(y)
for z in plus.values():
  ans*=(z+1)%(10**9+7)
ans*=(2**x+2**y-1)%(10**9+7)
print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
mod=10**9+7

S=[tuple(map(int,input().split())) for i in range(N)]

from collections import Counter
from fractions import Fraction
C=Counter()
MINUS=0
for a,b in S:
    if a==0 and b==0:
        MINUS+=1
    if b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=1
#print(C)
for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

        C[x]=0
        C[Fraction(-d,n)]=0
        
    else:
        ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

        C[float("inf")]=0
        C[Fraction(0,1)]=0

print((ANS-1-MINUS)%mod)

Submission status: Wrong Answer

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from fractions import Fraction as Fra, gcd
from collections import Counter

def solve(N, A):
    MOD = 10 **9 + 7
    # Cant if dot product is 0
    count = Counter()
    for x, y in A:
        g = gcd(x, y)
        if g:
            x //= g
            y //= g
        else:
            if x > 0: x=1
            if y > 0: y=1
            if x < 0: x=1
            if y < 0: y=1
        count[x, y] += 1
    m = max(count.itervalues())
    powers = [1]
    for i in xrange(m):
        powers.append(powers[-1] * 2 % MOD)
        
    # x,y = -y,x
    ans = 1
    for (x, y), c1 in count.iteritems():
        px, py = -y, x
        pg = gcd(px, py)
        if pg:
            px//=pg; py//=pg;
        else:
            if px > 0: px = 1
            if px < 0: px = 1
            if py > 0: py = 1
            if py < 0: py = 1
        c2 = count[px, py]
        if not c2:
            ans *= powers[c1]
            ans %= MOD
        elif (x,y) < (px,py):
            f = (powers[c1] + powers[c2] - 1)%MOD
            ans *= f
            ans %= MOD
    return (ans - 1) % MOD
    
    
N = rri()
A = [rrm() for _ in xrange(N)]
print solve(N, A)

Submission status: Wrong Answer

Solution code:
n=int(input())
mod = 1000000007
gp = []
gm = []
ga0  =0
gb0 = 0
ans = 1
cnt = 0
for _ in range(n):
    a,b= map(int,input().split())
    #a,b = 1,1
    if a == 0 and b == 0:
        cnt += 1
    elif  a == 0:
        ga0 += 1
    elif b == 0:
        gb0 += 1
    elif b/a > 0:
        gp.append(b/a)
    else:
        gm.append(-a/b)
gp.sort()
gm.sort()

lp,lm=0,0
cntall = 0
while lp < len(gp) and lm < len(gm):
    cal = gp[lp] - gm[lm]
    if cal == 0:
        cntp,cntm = 1,1
        while lp +1 < len(gp) and  gp[lp] == gp[lp+1]:
            cntp += 1
            lp+=1
        while lm +1 < len(gm) and  gm[lm] == gm[lm+1]:
            cntm += 1
            lm+=1
        ans *= ((pow(2,cntp,mod)+pow(2,cntm,mod))%mod-1)%mod
        ans %= mod
        lp+=1
        lm+=1
        cntall += cntp+cntm
    elif cal < 0:
        lp += 1
    else:
        lm += 1

ans *= ((pow(2,ga0,mod)+pow(2,gb0,mod))%mod-1)%mod
ans %= mod
n -= ga0+gb0+cntall+cnt
ans *= pow(2,n,mod)
ans %= mod
ans += cnt - 1
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math 

MOD = 10**9 + 7
N = int(input())
ABC = []
for i in range(N):
    a, b = map(int, input().split())
    if a * b >=0 and a != 0:
        ABC.append([ math.atan2(abs(b),abs(a)), abs(a), abs(b),1])
    else:
        ABC.append([math.atan2(abs(a),abs(b)), abs(b), abs(a), -1])
ABC.sort()
current_arg = ABC[-1][0]
group = []
daiich = 0
daini = 0
while ABC:
    current = ABC.pop()
    if current[0] == current_arg:
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
    else:
        group += [[daiich, daini]]
        daiich = 0
        daini = 0
        if current[3]==1:
            daiich += 1
        else:
            daini += 1
        if ABC:
            current_arg = current[0]
else:
    group += [[daiich, daini]]
    daiich = 0
    daini = 0

ans = 1
for u, v in group:
    ans *= (2**u + 2**v -1)
    ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import sys
MOD = 1000000007  # type: int


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, A: "List[int]", B: "List[int]"):
    # fishes = {}
    # zeroFishesB = 0
    # zeroFishesA = 0
    # valueFishes = N
    #
    # def getFishC(a):
    #     return fishes[a] if a in fishes else 0
    # for i in range(N):
    #     if A[i] == 0 and B[i] == 0: # 両方0,0ならばどの魚とも仲良くなれないので消す
    #         valueFishes -= 1
    #         continue
    #     if A[i] == 0:
    #         zeroFishesA += 1
    #     if B[i] == 0:
    #         zeroFishesB += 1
    #     fishes[(A[i],B[i])] = getFishC((A[i],B[i]))+1
    # def countWithZero(a): # aと中の悪い魚の数を返す
    #     if a[0] != 0 or a[1] != 0:
    #         return getFishC((-a[1],a[0]))+getFishC((a[1],-a[0]))
    #     else:
    #         if a[0] == 0:
    #             return zeroFishesB
    #         else:
    #             return zeroFishesA
    #
    # allCandidate = powm(2,valueFishes,MOD)-1
    # print(allCandidate)
    # for k in fishes:
    #     print(f"{k}->{countWithZero(k)}")
    fishes = []
    validFishes = N
    fishRads = dict()
    for i in range(N):
        if A[i] == 0 or B[i] == 0:
            validFishes-=1
            continue
        fishes.append((A[i],B[i]))
        normalRad = abs(A[i])/abs(B[i])
        cur = (0,0)
        if (A[i] > 0 and B[i] >= 0) or (A[i] < 0 and B[i] <= 0):
            if normalRad in fishRads:
                cur = fishRads[normalRad]
            fishRads[normalRad] = (cur[0]+1,cur[1])
        else:
            rotRad = abs(B[i]) / abs(A[i])
            if rotRad in fishRads:
                cur = fishRads[rotRad]
            fishRads[rotRad] = (cur[0], cur[1]+1)
    current = 1
    for k in fishRads:
        groups = fishRads[k]
        stage= (powm(2,groups[0],MOD) + powm(2,groups[1],MOD)-1)%MOD
        current = current*stage%MOD
    print(current-1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()