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:
def divide(a,b):
    minus=0
    if a*b<0:
        minus=1
    u=abs(max(a,b))
    t=abs(min(a,b))
    while(1):
        c=u//t
        d=u%t
        if d>0:
            u=t
            t=d
        else:
            ret=str(abs(a)//t)+'/'+str(abs(b)//t)
            if minus==1:
                ret="-"+ret
            return ret


n = int(input())
d={}
s=set([])
x=0
y=0
z=0
c=0
ans=1
N=1000000007
for i in range(n):
    a,b =map(int,input().split())
    if (a==0) and (b!=0):
        x+=1
    elif (a!=0) and (b==0):
        y+=1
    elif (a==0) and (b==0):
        z+=1
    else:
        p=divide(a,b)
        if d.get(p)==None:
            d[p]=1
        else:
            d[p]+=1
        s|={p}
if x==0:
    ans*=2**y
elif y==0:
    ans*=2**x
else:
    ans*=2**x+2**y-1

for i in s:
    if i.startswith("-"):
        index=i.index('/')
        q=i[index+1:]+'/'+i[1:index]
    else:
        index=i.index('/')
        q='-'+i[index+1:]+'/'+i[:index]
    if d.get(q)!=None:
        j=d[q]
        ans*=2**d[i]+2**j-1
        d[i]=0
        d[q]=0
    else:
        ans*=2**d[i]
        d[i]=0
    if ans>N:
        ans%=N
print(ans+z-1)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
ab = []
for i in range(n):
  ab.append(tuple(map(int,input().split())))
MOD = 1000000007

d = {}
zero = 0
for a,b in ab:
  if a == 0 and b == 0:
    zero += 1
    continue
  g = math.gcd(a,b)
  a //= g
  b //= g
  if b < 0:
    a,b = -a,-b
  elif a < 0 and b == 0:
    a = -a
  rot90 = False
  if a <= 0:
    a,b = b,-a
    rot90 = True
  if (a,b) in d:
    if rot90:
      d[(a,b)][1] += 1
    else:
      d[(a,b)][0] += 1
  else:
    if rot90:
      d[(a,b)] = [0,1]
    else:
      d[(a,b)] = [1,0]
print(d)

ans = 1
for k,v in d.items():
  tmpans = pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
  tmpans %= MOD
  ans *= tmpans
ans -= 1
ans += zero
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import sys

max_int = 1000000001  # 10^9+1
min_int = -max_int

n = int(sys.stdin.readline())
counter = {}
to_add = 0
a_zero_counter = b_zero_counter = 0
for _n in range(n):
    a, b = map(int, sys.stdin.readline().split())

    if a == 0 and b == 0:
        to_add += 1
        continue
    elif a == 0:
        a_zero_counter += 1
        continue
    elif b == 0:
        b_zero_counter += 1
        continue
    elif (a > 0) == (b > 0):
        definer = a / b
    else:
        definer = b / a

    if definer not in counter:
        counter[definer] = 1
    else:
        counter[definer] += 1

#print(counter)

prod = 2 ** a_zero_counter + 2 ** b_zero_counter - 1
for k in counter:
    if counter[k]:
        if -k in counter:
            prod *= 2 ** counter[k] + 2 ** counter[-k] - 1
            counter[-k] = 0
        else:
            prod *= 2 ** counter[k]
        prod %= 1000000007

prod += to_add - 1

print(prod % 1000000007)

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((d[x], 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return (r - 1 + zab) % mod
print(main())

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return (r - 1 + zab) % mod
print(main())

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return r % mod - 1 + zab
print(main())

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = zab + pow(2, za) + pow(2, zb) - 1
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return r % mod - 1
print(main())

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = zab + pow(2, za) + pow(2, zb) - 2
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return r % mod - 1
print(main())

Submission status: Wrong Answer

Solution code:
import math
def main():
    N = int(input())
    d = {}
    zb = 0
    za = 0
    zab = 0
    r = 0
    mod = 10**9 + 7
    for i in range(N):
        a, b = map(int, input().split())
        if a== 0 and b == 0:
            zab += 1
        elif b == 0:
            zb += 1
        elif a == 0:
            za += 1
        else:
            if a < 0:
                a = -a
                b = -b
            x = math.gcd(abs(a), abs(b))
            if (a//x, b//x) in d:
                d[(a//x, b//x)] += 1
            else:
                d[(a//x, b//x)] = 1
    used = set()
    l = []
    for x in d:
        if x in used:
            continue
        a, b = x[0], x[1]
        used.add(x)
        if a * b > 0:
            t = (abs(b), -abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
        else:
            t = (abs(b), abs(a))
            if t in d:
                used.add(t)
                l.append((d[x], d[t]))
            else:
                l.append((1, 0))
    r = pow(2, zab) + pow(2, za) + pow(2, zb) - 2
    for i in l:
        r *= (pow(2, i[0]) + pow(2, i[1]) - 1)
        r %= mod
    return r % mod - 1
print(main())

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
def GCD(a,b):
    gc = gcd(a,b)
    a//=gc
    b//=gc
    return a,b

zero = 0
First_quadrant = defaultdict(int)
Second_quadrant = defaultdict(int)
n = int(input())
for i in range(n):
    a,b = map(int, input().split())
    if a == 0 and b == 0:
        zero +=1
        continue
    elif a*b > 0 and b != 0:
        First_quadrant[(GCD(abs(a),abs(b)))] +=1
    else:
        Second_quadrant[(GCD(abs(b), abs(a)))] +=1
        First_quadrant[(GCD(abs(b), abs(a)))] +=0

ans = 1
for key1, val in  First_quadrant.items():

    v2 = Second_quadrant[key1]
    ans *= (2**val + 2**v2 -1)
    ans %= (10**9+7)
ans  = ans + zero -1
ans %= (10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
A_B_dict = {}
RF_zero = 0
R_zero = 0
F_zero = 0
for i in range(n):
    a, b = map(int,input().split())
    if a == 0:
        if b == 0:
            RF_zero += 1
        else:
            RF_zero += 0
    elif b == 0:
        F_zero += 1
    else:
        temp = a/b
        if temp in A_B_dict:
            A_B_dict[temp] += 1
        else:
            A_B_dict[temp] = 1
net_dict = {}
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = pow(2, A_B_dict[i], 1000000007) + pow(2, A_B_dict[temp], 1000000007) - 1
    else:
        net_dict[temp] = pow(2,A_B_dict[i], 1000000007)
ans = pow(2, R_zero, 1000000007) + pow(2, F_zero, 1000000007)
for k in net_dict.values():
    ans = (ans*k)
print((ans-1)%1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())
A_B_dict = {}
RF_zero = 0
R_zero = 0
F_zero = 0
for i in range(n):
    a, b = map(int,input().split())
    if a == 0:
        if b == 0:
            RF_zero += 1
        else:
            RF_zero += 0
    elif b == 0:
        F_zero += 1
    else:
        temp = a/b
        if temp in A_B_dict:
            A_B_dict[temp] += 1
        else:
            A_B_dict[temp] = 1
net_dict = {}
for i in A_B_dict:
    temp = -1/i
    if temp in A_B_dict:
        if i not in net_dict:
            net_dict[temp] = pow(2, A_B_dict[i], 1000000007) + pow(2, A_B_dict[temp], 1000000007) - 1
    else:
        net_dict[temp] = pow(2,A_B_dict[i], 1000000007)
ans = pow(2, R_zero, 1000000007) + pow(2, F_zero, 1000000007) - 1
for k in net_dict.values():
    ans = (ans*k)
print((ans-1)%1000000007)

Submission status: Wrong Answer

Solution code:
def inner_product(l, m): return l[0]*m[0] + l[1]*m[1]

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


N = int(input())

status = []
for i in range(N):
    A, B = input().split()
    status.append([int(A), int(B)])

f = [0 for i in range(N)]

for i in range(N-1):
    counter = 0
    for j in range(i+1, N):
        if inner_product(status[i], status[j]) == 0:
            counter += 1
    f[i] = counter

result = 0
for i in range(N):
    result += power_func(2, N - 1 - i - f[i], 1000000007)

print(result % 1000000007)

Submission status: Wrong Answer

Solution code:
n = int(input())
d={}
s=set([])
x=0
y=0
z=0
c=0
ans=1
N=1000000007
for i in range(n):
    a,b =map(int,input().split())
    if (a==0) and (b!=0):
        x+=1
    elif (a!=0) and (b==0):
        y+=1
    elif (a==0) and (b==0):
        z+=1
    else:
        p=round(b/a,17)
        if d.get(p)==None:
            d[p]=1
        else:
            d[p]+=1
        s|={b/a}
if x==0:
    ans*=2**y
elif y==0:
    ans*=2**x
else:
    ans*=2**x+2**y-1

for i in s:
    p=round(i,17)
    q=round(-1/i,17)
    if d.get(q)!=None:
        j=d[q]
        ans*=2**d[p]+2**j-1
        d[p]=0
        d[q]=0
    else:
        ans*=2**d[p]
        d[p]=0
    if ans>N:
        ans%=N
print(ans+z-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d={}
s=set([])
x=0
y=0
z=0
c=0
ans=1
N=1000000007
for i in range(n):
    a,b =map(int,input().split())
    if (a==0) and (b!=0):
        x+=1
    elif (a!=0) and (b==0):
        y+=1
    elif (a==0) and (b==0):
        z+=1
    else:
        if d.get(b/a)==None:
            d[b/a]=1
        else:
            d[b/a]+=1
        s|={b/a}
if x==0:
    ans*=2**y
elif y==0:
    ans*=2**x
else:
    ans*=2**x+2**y-1

for i in s:
    if d.get(-1/i)!=None:
        j=d[-1/i]
        ans*=2**d[i]+2**j-1
        d[i]=0
        d[-1/i]=0
    else:
        ans*=2**d[i]
        d[i]=0
    if ans>N:
        ans%=N
print(ans+z-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d={}
s=set([])
x=0
y=0
z=0
c=0
ans=1
N=1000000007
for i in range(n):
    a,b =map(int,input().split())
    if (a==0) and (b!=0):
        x+=1
    elif (a!=0) and (b==0):
        y+=1
    elif (a==0) and (b==0):
        z+=1
    else:
        if d.get(b/a)==None:
            d[b/a]=1
        else:
            d[b/a]+=1
        s|={b/a}
ans*=2**x+2**y-1
for i in s:
    if d.get(-1/i)!=None:
        j=d[-1/i]
        ans*=2**d[i]+2**j-1
        d[i]=0
        d[-1/i]=0
    else:
        ans*=2**d[i]
        d[i]=0
    if ans>N:
        ans%=N
print(ans+z-1)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

input = sys.stdin.buffer.readline
MOD = 1000000007
N = int(input())
dd = defaultdict(int)
count = 1
iwashi = [list(map(int, input().split())) for _ in range(N)]


checked = defaultdict(bool)
zeros = 0

for i in range(N):
    if iwashi[i][0] == iwashi[i][1] == 0:
        zeros += 1
        continue
    iw = iwashi[i]
    gcd_iw = math.gcd(iw[0], iw[1])
    if gcd_iw != 0:
        iw = list(map(lambda x: x // gcd_iw, iw))
    if iw[0] < 0:
        iw = list(map(lambda x: -x, iw))
    if iw[0] == 0 and iw[1] < 0:
        iw = list(map(lambda x: -x, iw))
    dd[tuple(iw)] += 1

for key, val in dd.items():
    if checked[key]:
        continue
    vert_key = (key[1], -key[0]) if key[1] >= 0 else (-key[1], key[0])
    vert_val = dd[vert_key] if vert_key in dd else 0
    count *= (pow(2, val, MOD) - 1) + (pow(2, vert_val, MOD) - 1) + 1
    count %= MOD
    checked[vert_key] = True

# 0匹入れる場合を除外
count -= 1

count += zeros
print(count % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

input = sys.stdin.buffer.readline
MOD = 1000000007
N = int(input())
dd = defaultdict(int)
count = 1
iwashi = [list(map(int, input().split())) for _ in range(N)]


checked = defaultdict(bool)
zeros = 0

for i in range(N):
    if iwashi[i][0] == iwashi[i][1] == 0:
        zeros += 1
        continue
    iw = iwashi[i]
    gcd_iw = math.gcd(iw[0], iw[1])
    if gcd_iw != 0:
        iw = list(map(lambda x: x // gcd_iw, iw))
    if iw[0] < 0:
        iw = list(map(lambda x: -x, iw))
    dd[tuple(iw)] += 1

for key, val in dd.items():
    if checked[key]:
        continue
    vert_key = (key[1], -key[0]) if key[1] >= 0 else (-key[1], key[0])
    vert_val = dd[vert_key] if vert_key in dd else 0
    count *= (pow(2, val, MOD) - 1) + (pow(2, vert_val, MOD) - 1) + 1
    count %= MOD
    checked[vert_key] = True

# 0匹入れる場合を除外
count -= 1

count += zeros
print(count % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

input = sys.stdin.buffer.readline
MOD = 1000000007
N = int(input())
dd = defaultdict(int)
count = 1
iwashi = [list(map(int, input().split())) for _ in range(N)]


checked = defaultdict(bool)
zeros = 0

for i in range(N):
    if iwashi[i][0] == iwashi[i][1] == 0:
        zeros += 1
        continue
    iw = iwashi[i]
    gcd_iw = math.gcd(iw[0], iw[1])
    if gcd_iw != 0:
        iw = list(map(lambda x: x // gcd_iw, iw))
    if iw[0] < -1:
        iw = list(map(lambda x: -x, iw))
    dd[tuple(iw)] += 1

for key, val in dd.items():
    if checked[key]:
        continue
    vert_key = (key[1], -key[0]) if key[1] >= 0 else (-key[1], key[0])
    vert_val = dd[vert_key] if vert_key in dd else 0
    count *= (pow(2, val, MOD) - 1) + (pow(2, vert_val, MOD) - 1) + 1
    count %= MOD
    checked[vert_key] = True

# 0匹入れる場合を除外
count -= 1

count += zeros
print(count % MOD)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from collections import defaultdict

input = sys.stdin.buffer.readline
MOD = 1000000007
N = int(input())
dd = defaultdict(int)
count = 1
iwashi = np.array([list(map(int, input().split())) for _ in range(N)])


gcd = np.gcd(iwashi[:, 0], iwashi[:, 1])
iwashi = iwashi // np.array([gcd, gcd]).T

checked = defaultdict(bool)
zeros = 0

for i in range(N):
    if iwashi[i][0] == iwashi[i][1] == 0:
        zeros += 1
        continue
    iw = iwashi[i]
    if iw[0] < -1:
        iw *= -1
    dd[tuple(iw.tolist())] += 1
for key, val in dd.items():
    if checked[key]:
        continue
    vert_key = (key[1], -key[0]) if key[1] >= 0 else (-key[1], key[0])
    vert_val = dd[vert_key] if vert_key in dd else 0
    count *= (pow(2, val, MOD) - 1) + (pow(2, vert_val, MOD) - 1) + 1
    count %= MOD
    checked[vert_key] = True

# 0匹入れる場合を除外
count -= 1

count += zeros
print(count % MOD)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
C = defaultdict(lambda: 0)
for i in range(int(input())):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        C[(0, 0)] += 1
        continue
    g = gcd(x, y)
    x, y = x // g, y // g
    if y < 0:
        x, y = -x, -y
    C[(x, y)] += 1
S = set()
for x, y in C:
    if x > 0 and y >= 0:
        S.add((x, y))
    if x <= 0 and y > 0:
        S.add((y, -x))
ans = 1
p = 10**9 + 7
for x, y in S:
    ans *= pow(2, C[(x, y)], p) + pow(2, C[(-y, x)], p) - 1
    ans %= p
print((ans + C[(0, 0)] - 1) % p)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math

n = int(input())

mod = 10**9+7

data = {}
zero_zero = 0

for i in range(n):
    a, b = list(map(int, input().split()))
    # # print(a, b)
    if a == 0 and b == 0:
        zero_zero += 1
        continue
    gcd = math.gcd(a, b)
    a, b = a//gcd, b//gcd
    if a < 0:
        a, b = -a, -b

    if a == 0:  # (0, 1)
        a, b = 0, 1

    elif b == 0:  # (1, 0)
        a, b = 1, 0

    # print(a, b)
    # print()

    if b <= 0:  # (+, -) or (1, 0)
        if (-b, a) in data:
            data[(-b, a)][1] += 1
        else:
            data[(-b, a)] = [0, 1]
    elif b > 0:  # (+, +) or (1, 0)
        if (a, b) in data:
            data[(a, b)][0] += 1
        else:
            data[(a, b)] = [1, 0]

# print(data)
# print(zero_zero)

power_2 = [1]
for i in range(1, 2*10**5+100):
    power_2.append(power_2[i-1]*2 % mod)

ans = 1
# print(ans)
# print()
for (a, b), (l, m) in data.items():
    ans *= (power_2[l]+power_2[m]-1) % mod
    # print(power_2[l]+power_2[m]-1)
    # print(ans)
    # print()

ans = ans - 1  # removed not selected

print(ans % mod)
# count_pp = 0
# count_pm = 0
# ans = 0
# while(1):
#     pp_tmp = plus_plus[count_pp]
#     pm_tmp = plus_minus[count_pm]

#     print("pp_tmp", pp_tmp)
#     print("pm_tmp", pm_tmp)

#     if pp_tmp[0]*pm_tmp[0] + pp_tmp[1]*pm_tmp[1] == 0:
#         pp_mag, pm_mag = 1, 1  # magnitude
#         while(1):
#             if count_pp < len(plus_plus)-1:
#                 if plus_plus[count_pp] == plus_plus[count_pp+1]:
#                     pp_mag += 1
#                     count_pp += 1
#                 else:
#                     break
#             else:
#                 break
#         while(1):
#             if count_pm < len(plus_minus)-1:
#                 if plus_minus[count_pm] == plus_minus[count_pm+1]:
#                     pm_mag += 1
#                     count_pm += 1
#                 else:
#                     break
#             else:
#                 break
#         ans += pp_mag*pm_mag

#     elif pp_tmp[2]*pm_tmp[2] > -1:
#         count_pp += 1

#     elif pp_tmp[2]*pm_tmp[2] < -1:
#         count_pm += 1

#     if count_pp == len(plus_plus)-1:
#         break
#     if count_pm == len(plus_minus)-1:
#         break
#     print(1)

# ans += zero_zero
# n = n - zero_zero
# count = ((n % mod) * ((n-1) % mod))//2
# count -= (negative) % mod

# print(count % mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod) - 1
        ans %= mod
        n -= 1
    elif a == 0:
        x.append(0)
        y.append(-inf)
    elif b == 0:
        x.append(inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1

lst.sort(reverse=1)
for i in lst:
    j = 0
    while j + 1 < i:
        if n - (i-(j+2)) - (j+2) >= 0:
            ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
            ans %= mod
        j += 1
    n -= i
    if n <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod) - 1
        ans %= mod
        n -= 1
    elif a == 0:
        x.append(0)
        y.append(-inf)
    elif b == 0:
        x.append(inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1

for i in lst:
    j = 0
    while j + 1 < i:
        if n - (i-(j+2)) - (j+2) >= 0:
            ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
            ans %= mod
        j += 1
    n -= i
    if n <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod) - 1
        ans %= mod
        n -= 1
    elif a == 0:
        x.append(0)
        y.append(inf)
    elif b == 0:
        x.append(-inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1

for i in lst:
    j = 0
    while j + 1 < i:
        if n - (i-(j+2)) - (j+2) >= 0:
            ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
            ans %= mod
        j += 1
    n -= i
    if n <= 0:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n, r):
    return fact[n]*pow(fact[n-r], mod-2, mod)*pow(fact[r], mod-2, mod) % mod
n = I()
ab = [LI() for _ in range(n)]
ans = pow(2, n, mod) - 1
fact = [1]*(n+1)
for i in range(1, n+1):
    fact[i] = i * fact[i-1]
    fact[i] %= mod

x = []
y = []
for a, b in ab:
    if a == 0 and b == 0:
        ans -= pow(2, n-1, mod) - 1
        ans %= mod
        n -= 1
    elif a == 0:
        x.append(0)
        y.append(inf)
    elif b == 0:
        x.append(-inf)
        y.append(0)
    else:
        x.append(a/b)
        y.append(-b/a)
lst = []
z = defaultdict(lambda : 0)
for i,j in enumerate(x):
    if z[j]:
        lst.append(z[j]+1)
    z[y[i]] += 1

for i in lst:
    j = 0
    while j + 1 < i:
        if n - (i-(j+2)) - (j+2) >= 0:
            ans -= comb(i, j+2) * pow(2, n - (i-(j+2)) - (j+2), mod)
            ans %= mod
        j += 1
    n -= i
print(ans)

Submission status: Wrong Answer

Solution code:
import sys, os

if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

f = lambda:list(map(int,input().split()))


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

def quick_pow(x,n, mod):
    ans= 1
    while n:
        if n&1:
            ans *= x
            ans %= mod
        x *= x
        x %= mod
        n >>= 1
    
    return ans


def solve():
    mod = 1000000007
    n = f()[0]

    from collections import defaultdict
    dirs = defaultdict(dict)

    all0 = 0
    x0 = 0
    y0 = 0

    for _ in range(n):
        a,b = f()
        if a ==0 or b == 0:
            all0 += 1
            continue
        if a == 0:
            x0 += 1
            continue
        if b == 0:
            y0 += 1
            continue

        if a <0:
            a = -a
            b = -b
        g = gcd(abs(a),abs(b))
        a //= g
        b //= g



        if a*b >0:
            dirs[(a,b)][0] = dirs[(a,b)].get(0, 0)+ 1
        else:
            dirs[(-b,a)][1] = dirs[(-b,a)].get(1,0) + 1
            
    
    ans = 1
    if x0 and y0:
        ans *= (quick_pow(2, x0, mod) + quick_pow(2, y0, mod)-1 + mod) % mod
    elif x0:
        ans *= quick_pow(2, x0, mod)
    elif y0: 
        ans *= quick_pow(2, y0, mod)
    
    ans %= mod
    for _, l in dirs.items():
        if len(l) == 1:
            if 0 in l:
                ans *= quick_pow(2, l[0],mod)
            else:
                ans *= quick_pow(2, l[1], mod)
        else:
            ans *= (quick_pow(2, l[0], mod) + quick_pow(2, l[1], mod)-1 + mod)%mod
        ans %= mod

    
    ans -= 1
    if all0:
        ans+= all0
    
    ans += mod
    ans%= mod
    print(ans)
    

solve()