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:
import math
N = int(input())
T = []
for i in range(N):
    a = list(map(int, input().split()))
    T.append(a)

mod = 10**9+7

A = {}
c_zero = 0
a_zero = 0
b_zero = 0
for i in range(N):
    if T[i][0] == 0 and T[i][1] == 0:
        c_zero += 1
    elif T[i][0] == 0:
        a_zero += 1
    elif T[i][1] == 0:
        b_zero += 1
    else:
        t = math.gcd(abs(T[i][0]),abs(T[i][1]))
        c = 0
        if T[i][0] < 0:
            T[i][0] *= -1
            c += 1
        if T[i][1] < 0:
            T[i][1] *= -1
            c += 1
        if (T[i][0]//t,T[i][1]//t,c%2) in A:
            A[T[i][0]//t,T[i][1]//t,c%2] += 1
        else:
            A[T[i][0]//t,T[i][1]//t,c%2] = 1

used = {}
for i in A.keys():
    used[i] = 0

ans = 1
for k,v in A.items():
    if used[k] == 0:
        if k[2] == 1:
            p = A.get((k[1],k[0],0),0)
            if p != 0:
                used[(k[1],k[0],0)] = 1
        else:
            p = A.get((k[1],k[0],1),0)
            if p != 0:
                used[(k[1],k[0],1)] = 1
        ans *= ( pow(2,v,mod)+pow(2,p,mod) - 1 )
        ans %= mod

ans *= ( pow(2,a_zero,mod)+pow(2,b_zero,mod) - 1 )
ans += c_zero
ans -= 1
print(ans%mod)

Submission status: Accepted

Solution code:
# 解説と 13355391 を参考に実装予定


import math


def solve():
    N = int(input())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]
    mod = 10 ** 9 + 7

    lonlieness = 0
    pairs = {}
    for AB in ABs:
        a, b = AB
        if a == 0 and b == 0:
            lonlieness += 1
            continue
        elif a == 0:
            a, b = -1, 0
            bad_a, bad_b = 0, 1
        elif b == 0:
            a, b = (0, 1)
            bad_a, bad_b = -1, 0
        else:
            _gcd = math.gcd(a, b)
            a //= _gcd
            b //= _gcd
            bad_a = -b
            bad_b = a
            if b < 0:
                a, b = -a, -b
            if bad_b < 0:
                bad_a, bad_b = -bad_a, -bad_b
        pairs.setdefault((a, b), 0)
        pairs.setdefault((bad_a, bad_b), 0)  # 仲の悪いグループも登録しておく
        pairs[(a, b)] += 1

    permutations = []
    for i, pair in enumerate(pairs.keys()):
        if i % 2 == 1:
            continue  # 仲の悪いグループは隣り合っているので飛び石で計算
        a, b = pair
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_a, bad_b = -bad_a, -bad_b
        # gourp1 から1匹以上選ぶパターン + group2 から1匹以上選ぶパターン + どちらからも選ばないパターン計算する.
        # group1 と group2 は仲が悪いので同時に選ばれることはない.
        group_num = pow(2, pairs[(a, b)], mod) - 1
        badgroup_num = pow(2, pairs[(bad_a, bad_b)], mod) - 1
        permutations.append(group_num + badgroup_num + 1)

    result = 1
    for p in permutations:
        result = result * p % mod

    # 全員と仲が悪いイワシのパターンを足し, すべてのイワシを選ばないパターンを除外.
    result = (result + lonlieness - 1) % mod
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# 解説と 13355391 を参考に実装予定


import math


def solve():
    N = int(input())
    ABs = [[int(i) for i in input().split()] for _ in range(N)]
    mod = 10 ** 9 + 7

    lonlieness = 0
    pairs = {}
    for AB in ABs:
        a, b = AB
        if a == 0 and b == 0:
            lonlieness += 1
            continue
        elif a == 0:
            a, b = -1, 0
            bad_a, bad_b = 0, 1
        elif b == 0:
            a, b = (0, 1)
            bad_a, bad_b = -1, 0
        else:
            _gcd = math.gcd(a, b)
            a //= _gcd
            b //= _gcd
            bad_a = -b
            bad_b = a
            if b < 0:
                a, b = -a, -b
            if bad_b < 0:
                bad_a, bad_b = -bad_a, -bad_b
        pairs.setdefault((a, b), 0)
        pairs.setdefault((bad_a, bad_b), 0)  # 仲の悪いグループも登録しておく
        pairs[(a, b)] += 1

    permutations = []
    for i, pair in enumerate(pairs.keys()):
        if i % 2 == 1:
            continue
        a, b = pair
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_a, bad_b = -bad_a, -bad_b
        group_num = pow(2, pairs[(a, b)], mod) - 1
        badgroup_num = pow(2, pairs[(bad_a, bad_b)], mod) - 1
        permutations.append(group_num + badgroup_num + 1)

    result = 1
    for p in permutations:
        result = result * p % mod

    result = (result + lonlieness - 1) % mod
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math

N = int(input())
d_ab = defaultdict(int)
d_ba = defaultdict(int)
mod = 1000000007
a0 = 0
b0 = 0
all0 = 0

for i in range(N):
    A,B = map(int,input().split())
    if A == 0 and B == 0:
        all0 += 1
    elif A == 0:
        a0 += 1
    elif B == 0:
        b0 += 1
    else:
        gcd = math.gcd(A,B)
        if (A < 0 and B > 0) or (A > 0 and B < 0):
            minus_f = True
        else:
            minus_f = False
        A //= gcd
        B //= gcd
        A = abs(A)
        B = abs(B)
        if minus_f:
            d_ab[(-A,B)] += 1
            d_ba[(B,A)] += 1
        else:
            d_ab[(A,B)] += 1
            d_ba[(-B,A)] += 1
        

ans = 1

#print(d_ab)
#print(d_ba)

pairs = list(map(list,d_ab.keys()))
visited = defaultdict(int)
#print(pairs)

for pair in pairs:
    ab = d_ab[tuple(pair)]
    ba = d_ba[tuple(pair)]
    r_pair = list(reversed(pair))
    if r_pair[0] > 0 and r_pair[1] > 0:
        r_pair[0] *= -1
    elif r_pair[1] < 0:
        r_pair[1] *= -1
    r_pair = tuple(r_pair)
    if ba != 0 and visited[tuple(pair)] == 0:
        visited[r_pair] = 1
        ans *= (pow(2,ab)+pow(2,ba)-1)
        ans %= mod
    if ba == 0 and visited[tuple(pair)] == 0:
        ans *= (pow(2,ab))
        ans %= mod
#    print(ans)

#print(visited)
ans *= (pow(2,a0)+pow(2,b0)-1)
ans %= mod

ans += all0 -1
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = (10 ** 9) + 7
assert MOD == 1000000007

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

n = int(raw_input())

ns = []
d = defaultdict(int)
zero = 0

for i in xrange(n):
    a, b = map(int, raw_input().split())
    ns.append((a, b))
    if a and b:
        s = 1 if a * b >= 0 else -1
        g = gcd(abs(a), abs(b))
        m1 = (s * abs(a) / g, abs(b) / g)
        m2 = (-s * abs(b) / g, abs(a) / g)
    elif a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        m1 = (1, 0)
        m2 = (0, 1)
    elif b == 0:
        m1 = (0, 1)
        m2 = (1, 0)

    d[m1] += 1
    d[m2] += 0

'''
res = 0
for i in xrange(1 << n):
    fs = []
    flag = True
    for j in xrange(n):
        if i & (1 << j):
            fs.append(ns[j])
    for i, f1 in enumerate(fs):
        for f2 in fs[i + 1:]:
            (a1, b1) = f1
            (a2, b2) = f2
            if a1 * a2 + b1 * b2 == 0:
                flag = False
                break
        if not flag:
            break
    if flag:
        res += 1
print res - 1
'''

pre = 1
for k in d.keys():
    if k[0] <= 0:
        assert (k[1], -k[0]) in d
        continue
    else:
        k1 = k
        k2 = (-k[1], k[0])

        tot = pow(2, d[k1], MOD) + pow(2, d[k2], MOD) - 1
        pre = pre * tot % MOD
print (pre - 1 + zero + MOD) % MOD

Submission status: Accepted

Solution code:
#E
from math import gcd
N=int(input())

mod=1000000007
ans=1
P=dict()
M=dict()
zero=0
zero1=0
zero2=0
for i in range(N):
    a,b=map(int,input().split())
    if a==0 and b==0:
        zero+=1
    elif a==0 and b!=0:
        zero1+=1
    elif a!=0 and b==0:
        zero2+=1
    elif (a>0 and b<0) or (a<0 and b>0):
        GCD=gcd(abs(a),abs(b))
        a=abs(a)//GCD
        b=abs(b)//GCD
        s=str(a)+"/"+str(b)
        P[s]=P.get(s,0)+1
        
    else:
        GCD=gcd(abs(a),abs(b))
        a=abs(a)//GCD
        b=abs(b)//GCD
        s=str(b)+"/"+str(a)
        M[s]=M.get(s,0)+1

P["0/0"]=zero1
M["0/0"]=zero2
for v,cnt_p in P.items():
    if v in M:
        cnt_m=M[v]
        ans*=(2**cnt_p+2**cnt_m-1)
        M.pop(v)
    else:
        ans*=2**cnt_p
    ans%=mod
    
for v,cnt_m in M.items():
    ans*=2**cnt_m
    ans%=mod

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

Submission status: Accepted

Solution code:
def resolve():
    import math
    from math import gcd
    MOD=10**9+7
    n=int(input())
    zero=0
    cnt={}
    for i in range(n):
        a,b=map(int,input().split())
        if a==0 and b==0:
            zero+=1
            continue
        g=gcd(a,b)
        a//=g
        b//=g
        if b<0:
            a*=-1
            b*=-1
        if b==0 and a<0:
            a*=-1
        if a<=0:
            a,b=b,-a
            if (a,b) in cnt:
                cnt[(a,b)][0]+=1
            else:
                cnt[(a,b)]=[1,0]
        else:
            if (a,b) in cnt:
                cnt[(a,b)][1]+=1
            else:
                cnt[(a,b)]=[0,1]
    ans=1
    for i,v in cnt.items():
        ans*=pow(2,v[0],MOD)+pow(2,v[1],MOD)-1
        ans%=MOD
    print((zero-1+ans)%MOD)    

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
import math


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter = defaultdict(lambda: defaultdict(int))
    for _ in range(n):
        x, y = [int(x) for x in input().split()]

        if x == y == 0:
            zeroes += 1
            continue

        denominator = math.gcd(x, y)
        x, y = x // denominator, y // denominator

        if y < 0:
            # quadrant III, IV -> I, II
            x, y = -x, -y

        if x <= 0:
            # round 90° from quadrant II to I
            x, y = y, -x
            counter[(x, y)][1] += 1
        else:
            counter[(x, y)][0] += 1

    ans = 1
    for v in counter.values():
        now = 1
        now += pow(2, v[0], mod) - 1
        now += pow(2, v[1], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  # choose no fish
    return ans % mod


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
import math


def ggg(a, b):
    """規約分数を作る。n/0, 0/n は n=1,-1 にして返す。"""
    if a == b == 0:
        return 0, 0

    denominator = math.gcd(a, b)
    x, y = a // denominator, b // denominator
    return x, y


def main():
    n = int(input())
    mod = 1000000007
    zeroes = 0
    counter = defaultdict(lambda: defaultdict(int))
    for _ in range(n):
        a, b = [int(x) for x in input().split()]
        x, y = ggg(a, b)

        if x == y == 0:
            zeroes += 1
            continue
        if y < 0:
            # quadrant III, IV -> I, II
            x, y = -x, -y

        if x <= 0:
            # round 90° from quadrant II to I
            x, y = y, -x
            counter[(x, y)][1] += 1
        else:
            counter[(x, y)][0] += 1

    ans = 1
    for v in counter.values():
        now = 1
        now += pow(2, v[0], mod) - 1
        now += pow(2, v[1], mod) - 1
        ans = ans * now % mod
    ans += zeroes
    ans -= 1  # choose no fish
    return ans % mod


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
N,*L = map(int, open(0).read().split())
dic = defaultdict(int)
ans = 0
MOD = 10**9+7
S = set()
for a,b in zip(*[iter(L)]*2):
  if a==0 and b==0:
    ans += 1
    continue
  g = gcd(a,b)
  if b>0:
    dic[(a//g,b//g)] += 1
    S.add((a//g,b//g))
  elif b<0:
    dic[(-a//g,-b//g)] += 1
    S.add((-a//g,-b//g))
  else:
    dic[(1,0)] += 1
    S.add((1,0))
m = 1
for a,b in S:
  if a<=0:
    if dic[(b,-a)]==0:
      m *= pow(2,dic[(a,b)],MOD)
      m %= MOD
      continue
  else:
    if dic[(-b,a)]==0:
      m *= pow(2,dic[(a,b)],MOD)
      m %= MOD
      continue
    c = pow(2,dic[(a,b)],MOD)+pow(2,dic[(-b,a)],MOD)-1
    m *= c
    m %= MOD
ans = (m-1+ans)%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

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

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    a, b = a // abs(gcd(a, b)), b // abs(gcd(a, b))

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    elif b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    elif (a < 0) ^ (b < 0):
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += MOD
ans += zeros
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import functools
MOD=10**9+7

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

def gcd(nums):
  return functools.reduce(euclid, nums)

n=int(input())
t=[]
for i in range(n):
    a,b=map(int,input().split())
    t.append((a,b))
z=0
y={}
for i in range(n):
    if t[i][0]==0 and t[i][1]==0:
        z+=1
    else:
        g=abs(gcd([t[i][0],t[i][1]]))
        if t[i][1]==0:
            a=(1,0)
        elif t[i][1]>0:
            a=(t[i][0]//g , t[i][1]//g)
        else:
            a=(-t[i][0]//g , -t[i][1]//g)
        if a not in y:
            y[a]=1
        else:
            y[a]+=1

cnt=0
x=1
for i in y:
    if (-i[1],i[0]) in y:
        x  *= pow(2,y[(-i[1],i[0])],MOD) + pow(2,y[(i[0],i[1])],MOD)-1
        cnt+= y[(-i[1],i[0])] + y[(i[0],i[1])]

ans = pow(2,n-z-cnt,MOD) *x -1
print((ans+z)%MOD)

Submission status: Accepted

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
d={}
mod=10**9+7
def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y
z=0
for i in range(n):
    a,b=ab[i]
    if a==0 and b==0:
        z+=1
        continue
    if a==0:
        b=1
        y=(a,b)
        if y in d:
            d[y]+=1
        else:
            d[y]=1
        continue
    if b==0:
        a=1
        y=(a,b)
        if y in d:
            d[y]+=1
        else:
            d[y]=1
        continue
    x=gcd(a,b)
    a//=x
    b//=x
    if a<0:
        a*=-1
        b*=-1
    y=(a,b)
    if y in d:
        d[y]+=1
    else:
        d[y]=1
ans=1
re={}
for t,v in d.items():
    if t in re:
        continue
    a,b=t
    c=0
    if (b,-a) in d:
        c+=d[(b,-a)]
        re[(b,-a)]=1
    if (-b,a) in d:
        c+=d[(-b,a)]
        re[(-b,a)]=1
    ans*=(2**v-1+2**c-1+1)
    ans%=mod
ans-=1
ans+=z
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

N = int(input())
# 常にy座標の方を正にする
zero = 0
d = {}
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    # 最大公約数で割って互いに素である状態にする（既約分数にする）
    g = gcd(a, b)
    a //= g
    b //= g
    # 常にbを正の状態に保つ
    if b < 0:
        a = -a
        b = -b
    if b == 0 and a == -1:
        a = 1

    if a > 0:
        if (a, b) in d:
            d[(a, b)][0] += 1
        else:
            d[(a, b)] = [1, 0]
    else:
        if (b, -a) in d:
            d[(b, -a)][1] += 1
        else:
            d[(b, -a)] = [0, 1]
MOD = 10**9+7
ans = 1
for (a, b), (k, l) in d.items():
    ans *= (pow(2, k, MOD)-1) + (pow(2, l, MOD)-1) + 1
    ans %= MOD
ans += zero
ans -= 1
print(ans%MOD)

Submission status: Accepted

Solution code:
from sys import stdin
from math import gcd
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=[0]*n
    b=[0]*n
    for i in range(n):
        a[i],b[i]=map(int,readline().split())

    mod=1000000007
    d=dict()
    d[(1,0)]=[0,0]
    ans=1
    zeros=0
    for i in range(n):
        up=a[i]
        down=b[i]
        if up==0 and down==0:
            zeros+=1
        else:
            g=gcd(up,down)
            up//=g
            down//=g
            if up==0:
                down=1
            elif down==0:
                up==1
            elif down<0:
                down*=-1
                up*=-1

            if up==1 and down==0:
                d[(1,0)][0]+=1
            elif up==0 and down==1:
                d[(1,0)][1]+=1
            elif up>0:
                if (up,down) not in d and (-down,up) not in d:
                    d[(up,down)]=[1,0]
                elif (up,down) in d:
                    d[(up,down)][0]+=1
                else:
                    d[(-down,up)][1]+=1
            elif up<0:
                if (up,down) not in d and (down,-up) not in d:
                    d[(up,down)]=[1,0]
                elif (up,down) in d:
                    d[(up,down)][0]+=1
                else:
                    d[(down,-up)][1]+=1

    for v in d.values():
        ans*=pow(2,v[0])+pow(2,v[1])-1
        ans%=mod
    ans-=1
    ans+=zeros
    ans%=mod
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd

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

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

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai * bi < 0
        if ai < 0:
            ai, bi = -ai ,-bi
        elif ai == 0:
            bi = -1
            t = 1

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


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

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

        if k2 in a1: continue

        z1 += v
    ans *= pow(2, z1, mod)

    print((ans-1+z0) % mod)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys
from collections import defaultdict
from math import gcd

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

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

    d1 = [defaultdict(int), defaultdict(int)]
    z0 = 0
    for ai, bi in zip(it, it):
        if ai == 0 and bi == 0:
            z0 += 1
            continue

        ci = gcd(ai, bi)
        ai, bi = ai // ci, bi // ci

        t = ai * bi < 0
        if ai < 0:
            ai, bi = -ai ,-bi
        elif ai == 0:
            bi = -1
            t = 1

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


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

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

        if k2 in a1: continue

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

    print((ans-1+z0) % mod)



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd

def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    x0,y0,xy0 = 0,0,0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0 and y==0:
            xy0 += 1
        elif x==0 and y!=0:
            x0 += 1
        elif y==0:
            y0 += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    ans = pow(2,x0,mod)+pow(2,y0,mod)-1
    other = N-x0-y0-xy0
    for k,v in dplus.items():
        ans *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans *= pow(2,other,mod)
    ans += xy0-1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
n = int(input())
zeros = 0
ab = {}
for _ in range(n):
    a, b = [int(i) for i in input().split()]
    if a == b == 0:
        zeros += 1
    elif a == 0 or b == 0:
        if None not in ab:
            ab[None] = [0, 0]
        if a == 0:
            ab[None][0] += 1
        else:
            ab[None][1] += 1
    else:
        x = 1 if a * b > 0 else -1
        c = max(abs(a) * 10 ** 100 // abs(b) * x,
                abs(b) * 10 ** 100 // abs(a) * (-x))
        if c not in ab:
            ab[c] = [0, 0]
        if a * b > 0:
            ab[c][0] += 1
        else:
            ab[c][1] += 1
ans = 1
mod = 10 ** 9 + 7
for _, v in ab.items():
    ans *= pow(2, v[0], mod) + pow(2, v[1], mod) - 1
    ans %= mod
ans += zeros - 1
print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd

def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero,yzero,xyzero = 0,0,0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            if y==0:
                xyzero += 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    ans = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero-xyzero
    for k,v in dplus.items():
        ans *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans *= pow(2,other,mod)
    ans += xyzero-1
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd
def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero = 0
    yzero = 0
    xyzero = 0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            if y==0:
                xyzero += 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    pattern = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero-xyzero
    for k,v in dplus.items():
        pattern *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans = pattern * pow(2,other,mod) - 1
    ans += xyzero
    ans %= mod
    return ans
print(solve())

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
XY = [tuple(map(int, input().split())) for i in range(n)]
C = {}
z = 0
for x, y in XY:
    if x == 0 and y == 0:
        z += 1
        continue
    g = gcd(x, y)
    x, y = x // g, y // g
    if y < 0:
        x, y = -x, -y
    try:
        C[(x, y)] += 1
    except KeyError:
        C[(x, y)] = 1
ans = 1
p = 10**9 + 7
for x, y in C:
    if C[(x, y)] == 0:
        continue
    a = C[(x, y)]
    if x > 0:
        x0, y0 = -y, x
    else:
        x0, y0 = y, -x
    try:
        b = C[(x0, y0)]
        C[(x0, y0)] = 0
    except KeyError:
        b = 0
    ans *= pow(2, a, p) + pow(2, b, p) - 1
    ans %= p
    C[(x, y)] = 0
print((ans + z - 1) % p)

Submission status: Accepted

Solution code:
import math
import collections

n = int(input())
iwashi = []
sub_ans = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        sub_ans += 1
    else:
        if b == 0:
            iwashi.append('1/0')
        elif b > 0:
            c = math.gcd(a, b)
            iwashi.append('{}/{}'.format(a//c, b//c))
        else:
            c = math.gcd(a, b)
            iwashi.append('{}/{}'.format(-a//c, -b//c))
# 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]
    if k == '1/0':
        anti_k = '0/1'
    elif k == '0/1':
        anti_k = '1/0'
    else:
        c, d = k.split('/')
        if int(c) < 0:
            anti_k = '{}/{}'.format(d, -int(c))
        else:
            anti_k = '{}/{}'.format(-int(d), c)

    b = iwashi[anti_k]
    if a*b != 0:
        ans *= (pow(2, a, mod) + pow(2, b, mod) -1)
    else:
        ans *= pow(2, a, mod)
    iwashi[k] = 0
    iwashi[anti_k] = 0
    # print(k, anti_k ,a, b, ans)
    ans %= mod
print((ans+sub_ans-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
mod_val = 1000000007
def simplify(A, B):
  a = A//gcd(A,B)
  b = B//gcd(A,B)
  if b<0:
    return (-a, -b)
  return (a, b)
n = int(input())
count_simple_fish = dict()
bad_fish = 0
for _ in range(n):
  A, B = map(int, input().split())
  if A == B == 0:
    bad_fish = (bad_fish + 1)%mod_val
    continue
  if B == 0:
    if (1, 0) in count_simple_fish:
      count_simple_fish[(1, 0)][1] += 1
    else:
      count_simple_fish[(1, 0)] = [0, 1]
  elif A == 0:
    if (1, 0) in count_simple_fish:
      count_simple_fish[(1, 0)][0] += 1
    else:
      count_simple_fish[(1, 0)] = [1, 0]
  else:
    a, b = simplify(A, B)
    if a>0:
      if (a, b) in count_simple_fish:
        count_simple_fish[(a, b)][1] += 1
      else:
        count_simple_fish[(a, b)] = [0, 1]
    else:
      if (b, -a) in count_simple_fish:
        count_simple_fish[(b, -a)][0] += 1
      else:
        count_simple_fish[(b, -a)] = [1, 0]
big_total = 1
for simple_fish, count_leftright in count_simple_fish.items():
  group_pair_combos = 1
  group_pair_combos = (group_pair_combos + pow(2, count_leftright[1], mod_val) - 1)%mod_val
  group_pair_combos = (group_pair_combos + pow(2, count_leftright[0], mod_val) - 1)%mod_val
  big_total = (big_total * group_pair_combos)%mod_val
big_total = (big_total + bad_fish - 1)%mod_val
print(big_total)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.buffer.readline
mod=10**9+7
n=int(input())
d={}
z=0
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f
        if x<0:x*=-1;y*=-1
        if x==0 and y<0:y=-y
        if (x,y)not in d:d[(x,y)]=1
        else:d[(x,y)]+=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
from collections import defaultdict
d=defaultdict(int)#各点の方向ベクトルを管理
z=0#原点にいる際は例外処理したいので別途数える
from math import gcd 
for i in range(n):
    x,y=map(int,input().split())
    if x==y==0:z+=1
    else:
        f=gcd(x,y)
        x//=f;y//=f#非本質な定数倍を削除
        if x<0:x*=-1;y*=-1#偏角は|theta|<=pi/2で十分
        if x==0 and y<0:y=-y
        d[(x,y)]+=1
ans=1
for (a,s) in d:
    if d[(a,s)]==0:continue#すでに数えた
    ng=0
    if (s,-a)in d:ng+=d[(s,-a)];d[(s,-a)]=0
    if (-s,a)in d:ng+=d[(-s,a)];d[(-s,a)]=0
    ans*=(pow(2,d[(a,s)],mod)-1 + pow(2,ng,mod)-1 +1)%mod
    #(a,s)を一本以上使う,ngを((a,s)と直交するもの)を一本以上使う,どちらも使わない
    ans%=mod
    d[(a,s)]=0
print((ans+z-1)%mod)#原点はそれ1つのみでしか使えない　+　1つも使わない例を除外

Submission status: Accepted

Solution code:
import math
N=int(input())
A={}
mod=10**9+7
AZ,BZ,ZZ=0,0,0
for i in range(N):
  a,b=map(int, input().split())
  if a==b and a==0:
    ZZ+=1
  elif a==0:
    AZ+=1
    if (0,-1) not in A:
      A[(0,-1)]=1
    else:
      A[(0,-1)]+=1
  elif b==0:
    BZ+=1
    if (1,0) not in A:
      A[(1,0)]=1
    else:
      A[(1,0)]+=1
  else:
    if a<0:
      a*=-1
      b*=-1
    d=math.gcd(abs(a),abs(b))
    a//=d
    b//=d
    if (a,b) not in A:
      A[(a,b)]=1
    else:
      A[(a,b)]+=1
c=0
D=[]
for x,y in A:
  if (y,-x) in A:
    D.append((A[(x,y)],A[(y,-x)]))
    c+=A[(x,y)]+A[(y,-x)]
n=N-c-ZZ
p=pow(2,n,mod)
ans=p
for a,b in D:
  f=pow(2,a+b,mod)-(pow(2,a,mod)-1)*(pow(2,b,mod)-1)
  ans*=f
ans-=1
print((ans+ZZ)%mod)

Submission status: Accepted

Solution code:
import sys
import math
mod = 1000000007
 
n = int(sys.stdin.readline().rstrip())
ab = {}
for i in range(n):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a,b)
        a //= gcd
        b //= gcd
        if a < 0:
            a = -a
            b = -b
    ab.setdefault((a,b),0)
    ab[(a,b)]+=1
ans = 0
pairs=[]
s = set(ab.keys())
for i in ab.keys():
    a = i[0];b = i[1]
    if a == 0 and b == 0:
        ans = ab[(0,0)]
        n -= ans
    else:
        if (-b, a) in s:
            pairs.append([ab[(a,b)],ab[(-b,a)]])
select = 1
for pair in pairs:
    select*= (pow(2,pair[0],mod) + pow(2,pair[1],mod) -1)
    n -= (pair[0]+pair[1])
all_ans = (pow(2,n,mod) * select) % mod + ans -1
all_ans %= mod
print(all_ans)