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: Accepted

Solution code:
# ほぼ写経
from math import gcd
from collections import defaultdict
mod = 10**9+7
n = int(input())
mp = defaultdict(lambda: [0, 0])
zero_zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    rot_cnt = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        # ベクトルの成分が(正,正)となるまで90度回転、奇数回の時は元のベクトルと直行することになるのでrot_cntで記録
        # 今回の問題においては内積0を計算すればいいので逆ベクトルは考慮しなくてよい
        rot_cnt += 1
    mp[(a, b)][rot_cnt % 2] += 1
ans = 1
for s, t in mp.values():
    now = (pow(2, s, mod) + pow(2, t, mod) - 1) % mod
    ans = (ans * now) % mod
ans = (ans - 1 + zero_zero) % mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import math
    from collections import defaultdict

    mod = 1000000007

    N = int(input())

    zero_pair = 0
    zero_a = 0
    zero_b = 0
    pair_plus = defaultdict(int)
    pair_minus = defaultdict(int)
    for a, b in [tuple(map(int, input().split())) for _ in range(N)]:
        if a == 0 and b == 0:
            zero_pair += 1
            continue
        if a == 0:
            zero_a += 1
            continue
        if b == 0:
            zero_b += 1
            continue

        abs_a = abs(a)
        abs_b = abs(b)
        g = math.gcd(abs_a, abs_b)
        abs_a = abs_a//g
        abs_b = abs_b//g
        if a * b > 0:
            pair_plus[(abs_a, abs_b)] += 1
        else:
            pair_minus[(abs_a, abs_b)] += 1

    ans = 1
    ans *= (pow(2, zero_a, mod) + pow(2, zero_b, mod) - 1) % mod
    ans %= mod

    count_all = 0
    for item in pair_plus.items():
        a, b = item[0]
        cnt = item[1]
        if (b,a) in pair_minus:
            ans *= (pow(2, cnt, mod) + pow(2, pair_minus[(b,a)]) - 1) % mod
            ans %= mod
            del pair_minus[(b, a)]
        else:
            count_all += cnt

    for val in pair_minus.values():
        count_all += val

    ans = (ans * pow(2, count_all, mod)) % mod
    ans += zero_pair
    print((ans - 1) % mod)

main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict
mod = 10**9+7
n = int(input())
mp = defaultdict(lambda: [0, 0])
zerozero = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zerozero += 1
        continue
    g = gcd(a, b)
    a //= g
    b //= g
    rot_cnt = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rot_cnt += 1
    mp[(a,b)][rot_cnt%2] += 1
ans = 1
for s, t in mp.values():
    now = (pow(2, s, mod) + pow(2, t, mod) - 1) % mod
    ans = (ans * now) % mod
ans = (ans - 1 + zerozero) % mod 
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
p = 10**9+7
from math import gcd
from collections import Counter
from collections import defaultdict
used = defaultdict(list)

n = int(input())

ctr = Counter()
az = bz = zz = 0
for i in range(n):
    a, b = map(int, input().split())
    if a==b==0:
        zz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
    else:
        g = gcd(a,b)
        a,b = a//g, b//g
        if b < 0:
            a*=-1
            b*=-1
        ctr[(a,b)]+=1
        used[(a,b)]=False

ans = 1

# 仲の悪いグループ対ごとに処理する
for (a1,b1),v1 in ctr.items():
    if used[(a1,b1)]:
        continue
    a2,b2=-b1,a1
    if b2 < 0:
        b2*=-1
        a2*=-1
    v2 = ctr[(a2,b2)]

    r = (pow(2,v1,p)+pow(2,v2,p)-1)%p
    ans*=r
    ans%=p
    used[(a1,b1)]=True
    used[(a2,b2)]=True

# 片方が0のクループ対
r = (pow(2,az,p)+pow(2,bz,p)-1)%p
ans*=r
ans%=p

ans+=zz # 0匹のケースは禁止されている
ans-=1 # 0匹のケースは禁止されている
ans%=p
print(ans)

Submission status: Accepted

Solution code:
# 約分して、互いに素な(1,3) (3,1)のようなペアを作りカウントする
# 正のグループと負のグループを別々に管理
# 正のグループの相手が負のグループに存在した場合、
# どちらかのグループから好きなだけ選ぶか、どちらも選ばないかしかない
# 誰ともペアにならなかったグループの個数を全て足してP個だとして、2^P通りを掛ける
# (0,0)については、その中から1つ選ぶか、選ばないかしかない

import sys
readline = sys.stdin.readline

N = int(readline())
import math

zeropair = 0
zeroa = 0
zerob = 0
from collections import defaultdict
pluspair = defaultdict(int)
minuspair = defaultdict(int)
for i in range(N):
  a,b = map(int,readline().split())
  if a == 0 and b == 0:
    zeropair += 1
    continue
  if a == 0:
    zeroa += 1
    continue
  if b == 0:
    zerob += 1
    continue
  absa = abs(a)
  absb = abs(b)
  g = math.gcd(absa,absb)
  absa,absb = absa//g,absb//g
  if a * b > 0:
    pluspair[(absa,absb)] += 1
  else:
    minuspair[(absa,absb)] += 1

DIV = 1000000007
ans = 1
# zeroa,zerobから選ぶパターンは、どちらから好きなだけ選ぶか、どちらも選ばないか
ans *= (pow(2,zeroa,DIV) + pow(2,zerob,DIV) - 1) % DIV
ans %= DIV

# 誰とでもペアになれるものをカウント
allcnt = 0

# plusから選ぶパターンで、minusにある対応ペアを探す
for item in pluspair.items():
  a,b = item[0]
  cnt = item[1]
  if (b,a) in minuspair:
    ans *= (pow(2,cnt,DIV) + pow(2,minuspair[(b,a)]) - 1) % DIV
    ans %= DIV
    del minuspair[(b,a)]
  else:
    allcnt += cnt

for val in minuspair.values():
  allcnt += val

ans = (ans * pow(2,allcnt,DIV)) % DIV
# zeropairから選んだ場合、今までのパターンとは独立
ans += zeropair
print((ans - 1) % DIV)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
N = int(input())
mod = 10**9 + 7
D = defaultdict(int)
corner = 0
D[(0,1)]=0
D[(1,0)]=0
for i in range(N):
    x, y = map(int, input().split())
    if x*y != 0:
        x, y = x//gcd(x, y), y//gcd(x, y)
        if y > 0:
            D[(x, y)] += 1
        elif y < 0:
            D[(-x, -y)] += 1
    else:
        if x == 0 and y == 0:
            corner += 1
            continue
        else:
            if x == 0:
                D[(0, 1)] += 1
            elif y == 0:
                D[(1, 0)] += 1
ans = corner
# 以下、(0,0) を入れない時。(X,Y) のYは全て0以上で統一する（何も入れないも一応カウント）
c = 1
sub=[]
for x, y in D.keys():
    if x<0 and y>0:
        if not (y,-x) in D.keys():
            sub.append((y,-x))
for some in sub:
    D[some]=0

K=list(D.keys())
for x, y in K:
    if x > 0 and y > 0:
        a = D[(x, y)]
        b = D[(-y, x)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
    elif y == 0:
        a = D[(1, 0)]
        b = D[(0, 1)]
        c *= (pow(2, a, mod)+pow(2, b, mod)-1)
        c %= mod
ans += c-1

print(ans % mod)

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
mod = 1000000007
z=0
d={}
for _ in range(n):
  a,b=map(int,input().split())
  if not any((a,b)):
    z+=1
    continue
  if a==0:
    d[(0,1)]=d.get((0,1),0)+1
    continue
  if b==0:
    d[(1,0)]=d.get((1,0),0)+1
    continue
  g = gcd(a,b)
  s = a//abs(a)
  a,b = (a//g)*s, (b//g)*s
  d[(a,b)]=d.get((a,b),0)+1

done = set()
ans = 1
for (a,b), v in d.items():
  if (a,b) in done:continue
  done.add((a,b))
  done.add((-b,a))
  done.add((b,-a))
  w = d.get((-b,a),0)+d.get((b,-a),0)
  ans *= (pow(2,v,mod)+pow(2,w,mod)-1)
  ans %= mod
ans = (ans + z - 1 + mod)%mod
print(ans)

Submission status: Accepted

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

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

MOD = 10**9 + 7
n = int(input())
cnt = {}
zero_cnt = 0
ans = 1

for _ in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
#    if a == 0 or b == 0: g = max(abs(a), abs(b))
    a //= g
    b //= g

    rotate = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rotate += 1
    if (a, b) not in cnt:
        cnt[(a, b)] = [0, 0]

    cnt[(a, b)][rotate%2] += 1

for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1 #for empty set
print(ans % MOD)

Submission status: Accepted

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

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

MOD = 10**9 + 7
n = int(input())
cnt = {}
zero_cnt = 0
ans = 1

for _ in range(n):
    a, b = map(int, input().split())
    if (a, b) == (0, 0):
        zero_cnt += 1
        continue
    g = gcd(abs(a), abs(b))
    if a == 0 or b == 0: g = max(abs(a), abs(b))
    a //= g
    b //= g

    rotate = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        rotate += 1
    if (a, b) not in cnt:
        cnt[(a, b)] = [0, 0]

    cnt[(a, b)][rotate%2] += 1

for key in cnt:
    A, B = cnt[key]
    ans *= 1 + pow(2, A, MOD) - 1 + pow(2, B, MOD) - 1
    ans %= MOD

ans += zero_cnt
ans -= 1 #for empty set
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import gcd
from numpy import sign
mod = 1000000007
N = int(input())

d = {}
counter = 0

f = 0
l = 0

for _ in range(N):
    a, b = list(map(int, input().split()))
    if a == b == 0:
        counter += 1
    elif a==0:
        f += 1
    elif b==0:
        l += 1
    else:
        g = gcd(a, b)
        a, b =  a // g, b //g
        if b < 0:
            a, b = -a, -b
        if (a, b) not in d:
            d[(a, b)] =1
        else:
            d[(a, b)] +=1

answer = 1

group = set()
for (p, q), v in d.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))

for (p, q) in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if (invp, invq) not in d:
        answer *= (2 ** d[(p, q)])
    else:
        answer *= ((2 ** d[(p, q)]) + (2 ** d[(invp, invq)]) - 1)
        
answer *= 2**f + 2**l - 1
    
print((answer + counter - 1) % mod)

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
n = int(input())
d = {}
zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1
    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1
ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD) - 1 # -1 is because need to remove the case that choose nothing
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import collections
from math import gcd
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    c=collections.Counter()
    mod=10**9+7
    for _ in range(n):
        a,b=map(int,input().split())
        g=abs(gcd(a,b))
        if g==0:
            g=1
        a//=g
        b//=g
        c[(a,b)]+=1
    ans=1
    s=set()
    for i,j in c:
        if (i,j)==(0,0):
            continue
        if (i,j) not in s:
            s.add((i,j))
            s.add((-i,-j))
            s.add((-j,i))
            s.add((j,-i))
            ans*=(pow(2,c[(i,j)]+c[(-i,-j)],mod)+pow(2,c[(j,-i)]+c[(-j,i)],mod)-1)%mod
    print((ans-1+c[(0,0)])%mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

MOD = 1000000007

dic1 = {}
a_zero = 0
b_zero = 0
both_zero = 0

for a, b in AB:
    if a == 0 and b != 0:
        a_zero += 1
    elif a != 0 and b == 0:
        b_zero += 1
    elif a == 0 and b == 0:
        both_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g

        if b < 0:
            a, b = -a, -b

        if (a, b) in dic1:
            dic1[(a, b)] += 1
        else:
            dic1[(a, b)] = 1

pair = []
used = set()

for key, val in dic1.items():
    if key in used:
        continue

    a, b = key
    used.add((a, b))
    cnt = 0

    if a < 0:
        c, d = -b, -a
    else:
        c, d = b, a

    if (-c, d) in dic1:
        cnt += dic1.get((-c, d), 0)
        used.add((-c, d))

    pair.append((val, cnt))


all_cnt = 1
for cnt1, cnt2 in pair:
    all_cnt *= pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    all_cnt %= MOD

all_cnt *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
all_cnt %= MOD

all_cnt += both_zero
all_cnt %= MOD

print((all_cnt - 1) % MOD)

Submission status: Accepted

Solution code:
import math

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

MOD = 1000000007

dic1 = {}
a_zero = 0
b_zero = 0
both_zero = 0

for a, b in AB:
    if a == 0 and b != 0:
        a_zero += 1
    elif a != 0 and b == 0:
        b_zero += 1
    elif a == 0 and b == 0:
        both_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g

        if b < 0:
            a, b = -a, -b

        if (a, b) in dic1:
            dic1[(a, b)] += 1
        else:
            dic1[(a, b)] = 1

pair = []
used = set()

for key, val in dic1.items():
    if key in used:
        continue

    a, b = key
    used.add((a, b))
    cnt = 0

    if a < 0:
        c, d = -b, -a
    else:
        c, d = b, a

    if (-c, d) in dic1:
        cnt += dic1.get((-c, d), 0)
        used.add((-c, d))

    pair.append((val, cnt))


all_cnt = 1
for cnt1, cnt2 in pair:
    all_cnt *= pow(2, cnt1, MOD) + pow(2, cnt2, MOD) - 1
    all_cnt %= MOD

if a_zero != 0 or b_zero != 0:
    all_cnt *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
    all_cnt %= MOD

all_cnt += both_zero
all_cnt %= MOD

print((all_cnt - 1) % MOD)

Submission status: Accepted

Solution code:
import math

def heikatu(A,B):

    
    c = math.gcd(A,B)

    return (A//c,B//c)
 
 
def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod
 
 
 
def resolve():
    N = int(input())
 
    
    km = dict()
    kp = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())
 
        if A == 0 and B == 0:
            zerozero+=1

            continue
        
        if A == 0:
            B = -abs(B)
        if B == 0:
            A = abs(A)

 
        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)
 
 
 
        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    ans = 1

    groups = []
    for (x,y),v in km.items():
        if (-y,x) in kp:
            groups.append((v,kp[(-y,x)]))
            del kp[(-y,x)]
        else:
            groups.append((v,0))

    for v in kp.values():
        groups.append((v,0))


    for i,j in groups:
        ans *= (pow_r(2,i)+pow_r(2,j)-1)%1000000007
        ans %= 1000000007



    print((ans+zerozero-1)%(10**9+7))       

resolve()

Submission status: Accepted

Solution code:
import math
N=int(input())
MOD=10**9+7
fish={}
ans=1
a=0
b=0
w=0
for i in range(N):
    A,B=map(int,input().split())
    if A==0 and B==0:
        w+=1
    elif A==0:
        a+=1
    elif B==0:
        b+=1
    else:
        c=math.gcd(A,B)
        A=A//c
        B=B//c
        if B<0:
            A,B=-A,-B
        k=(A,B)
        if not k in fish:
            fish[k]=0
        fish[k]+=1
group=set()
for (p,q),v in fish.items():
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    if not (invp,invq) in group:
        group.add((p,q))
for p,q in group:
    invp,invq=-q,p
    if invq<0:
        invp,invq=-invp,-invq
    t=2**fish[p,q]
    if (invp,invq) in fish:
        t+=2**fish[invp,invq]-1
    ans=(ans*t)%MOD
ans*=2**a+2**b-1
ans=ans+w-1
print(ans%MOD)

Submission status: Accepted

Solution code:
from collections import Counter

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

MOD = 1000000007

# 2 WA
def main():
    N = int(input())
    d = {}
    d[(1,0)] = (0,0)
    z = 0
    for i in range(N):
      a,b = (int(x) for x in input().split())
      g = gcd(a,b)
      if g != 0:
        a = a//g
        b = b//g
        if a*b<0: a = -abs(a)
        elif a*b>0: a = abs(a)
      b = abs(b)
      
      if a*b==0:
        if a==b==0: z+=1
        elif b==0: d[(1,0)] = (d[(1,0)][0]+1,d[(1,0)][1])
        elif a==0: d[(1,0)] = (d[(1,0)][0],  d[(1,0)][1]+1)
      else:
        if (a,b) in d: d[(a,b)] = (d[(a,b)][0]+1,d[(a,b)][1])
        elif (b, -a) in d: d[(b,-a)] = (d[(b,-a)][0], d[(b,-a)][1]+1)
        elif (-b, a) in d: d[(-b,a)] = (d[(-b,a)][0], d[(-b,a)][1]+1)
        else: d[(a,b)] = (1,0)
    
    ans = 1
    for i, j in d.values():
      ans *= (pow(2,i,MOD) + pow(2,j,MOD) - 1)
      ans %= MOD

    print((ans-1+z)%MOD)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

MOD = 1000000007

def inv(a, b):
    if a < 0:
        a, b = -a, -b
    return (-b, a)

def solve(n, a, b):
    zero_zero = 0
    zero = 0
    inf = 0
    D = {}
    for i in range(n):
        p, q = a[i], b[i]
        if (p == 0) and (q == 0):
            zero_zero += 1
        elif p == 0:
            zero += 1
        elif q == 0:
            inf += 1
        else:
            r = gcd(p, q)
            p, q = (p // r, q // r)
            if q < 0:
                p, q = -p, -q
            k = (p, q)
            if not k in D:
                D[k] = 0
            D[k] += 1
    group = set()
    for (p, q), v in D.items():
        if not inv(p,q) in group:
            group.add((p,q))
    pow2 = [0] * (n+1)
    pow2[0] = 1
    for i in range(n):
        pow2[i+1] = (pow2[i] * 2) % MOD
    ans = 1
    for p, q in group:
        t = pow2[D[p,q]]
        if inv(p, q) in D:
            t += pow2[D[inv(p, q)]] - 1
        ans = (ans * t) % MOD
    ans *= pow2[zero] + pow2[inf] - 1
    return (ans + zero_zero - 1) % MOD

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
print(solve(n, a, b))

Submission status: Accepted

Solution code:
import sys
from collections import namedtuple, defaultdict
from math import gcd
input = sys.stdin.readline

class Point:
    def __init__(self, x, y):
        g = gcd(abs(x), abs(y))

        x //= g
        y //= g

        if x < 0:
            x *= -1
            y *= -1

        elif x == 0 and y < 0:
            y *= -1

        self.x = x
        self.y = y

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def __hash__(self):
        return hash((self.x, self.y))

    def __repr__(self):
        return f'({self.x}, {self.y})'

def main():
    n = int(input())
    
    p = []
    d = defaultdict(lambda: 0)
    zeros = 0

    for _ in range(n):
        x, y = map(int, input().split())

        if x == 0 and y == 0:
            n -= 1
            zeros += 1
            continue

        p.append(Point(x, y))
        d[p[-1]] += 1

    MOD = 10 ** 9 + 7

    pw = [ pow(2, i, MOD) for i in range(n + 1) ]

    ans = 1
    tot = 0

    for x in d.keys():
        if x.x > 0 and x.y >= 0 and Point(-x.y, x.x) in d:
            s = d[x]
            t = d[Point(-x.y, x.x)]

            tot += s + t
            value = (pw[s] + pw[t] - 1 + MOD) % MOD
            ans = ans * value % MOD

    ans = ans * pw[n - tot] % MOD
    ans = (ans - 1 + MOD + zeros) % MOD

    print(ans)
main()

Submission status: Accepted

Solution code:
n = int(input())
ab=[list(map(int,input().split())) for i in range(n)]
import math
from collections import defaultdict
d = defaultdict(int)
zerozero=0
azero=0
bzero=0
for tmp in ab:
    a,b=tmp

    if a==0 and b==0:
        zerozero+=1
        continue
    if a==0:
        azero+=1
        continue
    if b==0:
        bzero+=1
        continue

    absa=abs(a)
    absb=abs(b)
    gcd = math.gcd(absa,absb)

    absa//=gcd
    absb//=gcd

    if a*b >0:
        d[(absa,absb)]+=1
    else:
        d[(absa,-absb)]+=1

found = defaultdict(int)
d[(0,1)]=azero
d[(1,0)]=bzero

ans=1
mod=1000000007
for k in list(d.keys()):
    num = d[k]
    a,b=k

    if b>0:
        bad_ab = (b,-a)
    else:
        bad_ab = (-b,a)

    if found[k]!=0:
        continue
    found[bad_ab] = 1

    bm=d[bad_ab]

    if bm == 0:
        mul = pow(2,num,mod)
    if k==bad_ab:
        mul = num+1
    else:
        mul = pow(2,num,mod) + pow(2,bm,mod) -1
    ans*=mul

ans+=zerozero
ans-=1
print(ans%mod)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


def main():
    N = I()
    zero = 0
    plus_Ai_Bi = defaultdict(int)
    minus_Bj_Aj = defaultdict(int)
    zero_cnt = 0
    used = set()

    for i in range(N):
        a, b = MI()

        if a == 0 and b == 0:
            zero_cnt += 1
            continue

        gcdab = gcd(abs(a), abs(b))
        a = a // gcdab
        b = b // gcdab

        if a > 0 and b > 0:
            # pos
            plus_Ai_Bi[(a, b)] += 1
            # neg
            minus_Bj_Aj[(-b, a)] += 1
        elif a > 0 and b < 0:
            # neg
            plus_Ai_Bi[(-a, -b)] += 1
            # pos
            minus_Bj_Aj[(-b, a)] += 1
        elif a < 0 and b > 0:
            # neg
            plus_Ai_Bi[(a, b)] += 1
            # pos
            minus_Bj_Aj[(b, -a)] += 1
        elif a == 0:
            # neg
            plus_Ai_Bi[(a, abs(b))] += 1
            # pos
            minus_Bj_Aj[(abs(b), a)] += 1
        elif b == 0:
            # neg
            plus_Ai_Bi[(abs(a), b)] += 1
            # pos
            minus_Bj_Aj[(b, abs(a))] += 1
        else:
            # pos
            plus_Ai_Bi[(-a, -b)] += 1
            # neg
            minus_Bj_Aj[(b, -a)] += 1

    # print(plus_Ai_Bi)
    # print(minus_Bj_Aj)
    ans = 1

    for pair, cnt1 in plus_Ai_Bi.items():
        a, b = pair
        if pair in used:
            continue

        if pair in minus_Bj_Aj:
            cnt2 = minus_Bj_Aj[pair]
            group1 = pow(2, cnt1, MOD) - 1
            group2 = pow(2, cnt2, MOD) - 1
            ans *= group1 + group2 + 1
            ans %= MOD

            if a > 0 and b > 0:
                # minus_Bj_Aj[(-b, a)] += 1
                used.add((-b, a))
            elif a > 0 and b < 0:
                # minus_Bj_Aj[(-b, a)] += 1
                used.add((-b, a))
            elif a < 0 and b > 0:
                # minus_Bj_Aj[(b, -a)] += 1
                used.add((b, -a))
            elif a == 0:
                used.add((abs(b), a))
            elif b == 0:
                used.add((b, abs(a)))
            else:
                # minus_Bj_Aj[(b, -a)] += 1
                used.add((b, -a))
            # print(pair, ans)
        else:
            ans *= pow(2, cnt1, MOD)
            ans %= MOD

    print((ans - 1 + zero_cnt) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict


def sign(x):
    if x < 0:
        return -1
    if x > 0:
        return +1
    return 0


def power(a, b, m):
    res = 1
    base = a
    while b:
        if b & 1:
            res = res * base % m
        base = base * base % m
        b = b >> 1
    return res


N = int(input())
M = 1000000007
cnt = defaultdict(int)
case00 = 0

for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:  # (0, 0) cannot pair with anyone
        case00 += 1
        continue

    s = sign(a) * sign(b)
    a, b = abs(a), abs(b)
    g = gcd(a, b)
    a, b = a // g, b // g
    cnt[s, a, b] += 1


ans = 1  # empty set
vis = set()
for (s, a, b) in cnt.keys():
    if (s, a, b) in vis:
        continue

    if (-s, b, a) in cnt:
        mul = 1  # empty set from (s, a, b) and (-s, b, a)
        mul += power(2, cnt[s, a, b], M) - 1  # non-empty subsets from (s, a, b)
        mul += power(2, cnt[-s, b, a], M) - 1  # non-empty subsets from (-s, b, a)
        ans = ans * (mul % M) % M
        vis.add((-s, b, a))
    else:
        ans = ans * power(2, cnt[s, a, b], M) % M

ans = (ans - 1 + M) % M  # Remove empty set
ans = (ans + case00) % M  # Special case
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict
    from math import gcd
    import sys
    input = sys.stdin.readline


    mod = 10 ** 9 + 7
    n = int(input())
    fishes = defaultdict(int)
    zero_zero = 0
    zero = 0
    inf = 0

    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            zero_zero += 1

        elif a == 0:
            zero += 1

        elif b == 0:
            inf += 1

        else:
            div = gcd(a, b)
            a //= div
            b //= div
            if b < 0:
                a *= -1
                b *= -1
            key = (a, b)
            fishes[key] += 1


    def get_bad_pair(fish):
        a, b = fish
        if a < 0:
            a *= -1
            b *= -1
        return (-b, a)


    ans = 1
    counted_key = set()
    for fish_key, count in fishes.items():
        if fish_key in counted_key:
            continue

        bad_pair = get_bad_pair(fish_key)
        if bad_pair in fishes:
            pair_count = fishes[bad_pair]
            pattern = pow(2, count, mod) + pow(2, pair_count, mod) - 1
            counted_key.add(bad_pair)

        else:
            pattern = pow(2, count, mod)

        ans = ans * pattern % mod

    ans *= pow(2, zero, mod) + pow(2, inf, mod) - 1
    if zero_zero:
        ans += zero_zero

    ans -= 1
    print(ans % mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

mod = 10 ** 9 + 7
n = int(input())
fishes = defaultdict(int)
zero_zero = 0
zero = 0
inf = 0

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_zero += 1

    elif a == 0:
        zero += 1

    elif b == 0:
        inf += 1

    else:
        div = gcd(a, b)
        a //= div
        b //= div
        if b < 0:
            a *= -1
            b *= -1
        key = (a, b)
        fishes[key] += 1


def get_bad_pair(fish):
    a, b = fish
    if a < 0:
        a *= -1
        b *= -1
    return (-b, a)


ans = 1
counted_key = set()
for fish_key, count in fishes.items():
    if fish_key in counted_key:
        continue

    bad_pair = get_bad_pair(fish_key)
    if bad_pair in fishes:
        pair_count = fishes[bad_pair]
        pattern = pow(2, count, mod) + pow(2, pair_count, mod) - 1
        counted_key.add(bad_pair)

    else:
        pattern = pow(2, count, mod)

    ans = ans * pattern % mod

ans *= pow(2, zero, mod) + pow(2, inf, mod) - 1
if zero_zero:
    ans += zero_zero

ans -= 1
print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10**9+7
from math import gcd


n = int(input())
ans = 1
C = defaultdict(int)
z = 0
r = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        r += 1
    elif b == 0:
        z += 1
    elif a == 0:
        C[0] += 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        C[(a, b)] += 1
D = tuple(C.items())
used = {0}
for c, v in D:
    if c in used:
        continue
    a, b = c
    if b > 0:
        d, e = b, -a
    else:
        d, e = -b, a
    ans *= pow(2, v, MOD)+pow(2, C[(d, e)], MOD)-1
    ans %= MOD
    used.add((d, e))
ans *= pow(2, C[0], MOD)+pow(2, z, MOD)-1
ans += r
ans -= 1
ans %= MOD
print(ans)