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
# mを法とするときのa^n
def modpow(a,n):
    res = 1
    t = a
    while n:
        if n%2:
            res = (res*t)%MOD
        t = (t*t)%MOD
        n //= 2
    return res

def solve(fish):
    def helper(a,b):
        if a == 0 and b == 0:
            return (0, 0, 0)
        elif a == 0:
            return (1, 1, 0)
        elif b == 0:
            return (-1, 0, 1)

        g = gcd(a,b)
        sign = 1 if a*b > 0 else -1
        return (sign, abs(a//g), abs(b//g))

    counter = defaultdict(int)
    for a,b in fish:
        counter[helper(a,b)] += 1

    goods = 1

    for (a,b,c),s in tuple(counter.items()):
        if a == 0:
            continue

        t = counter[(-a,c,b)]
        if t == 0:
            goods *= modpow(2,s)
        elif a > 0:
            goods *= modpow(2,s)+modpow(2,t)-1
        goods %= MOD

    goods += counter[(0,0,0)]-1
    goods %= MOD
    return goods

def naive(fish):
    from itertools import combinations, product
    bad_pair = []
    for i,j in combinations(range(len(fish)), 2):
        if fish[i][0]*fish[j][0] + fish[i][1]*fish[j][1] == 0:
            bad_pair.append((i,j))

    cnt = 0
    for s in product(range(2), repeat=len(fish)):
        cnt += all(s[i]+s[j] < 2 for i,j in bad_pair)
    return cnt-1

if __name__ == '__main__':


    N = int(input())
    fish = tuple(tuple(map(int,input().split())) for _ in range(N))
    print(solve(fish))

    # from random import randint

    # N = 4
    # for _ in range(10000):
    #     fish = [(randint(-5,5),randint(-5,5)) for _ in range(N)]
    #     if solve(fish) != naive(fish):
    #         print(fish)
    #         print(solve(fish))
    #         print(naive(fish))

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def normalize(A, B):
    if A < 0:
        A = -A
        B = -B
    elif A == 0:
        B = abs(B)
    g = gcd(A, B)
    A //= g
    B //= g
    return (A, B)

N = int(input())

d = defaultdict(int)

for _ in range(N):
    A, B = map(int, input().split())
    if A == 0 and B == 0:
        d[(0, 0)] += 1
    else:
        A, B = normalize(A, B)
        d[(A, B)] += 1

if len(d) == 1:
    print(N) 
else:
    ans_without_0 = 1
    seen = []
    for k, v in d.items():
        if k != (0, 0) and k not in seen:
            k_2 = normalize(k[1], -k[0])
            if k_2 in d:
                seen.append(k_2)
                ans_without_0 *= (pow(2, v, MOD) + pow(2, d[k_2], MOD) - 1)
            else:
                ans_without_0 *= pow(2, v, MOD)
            ans_without_0 %= MOD
    print((ans_without_0 + d[(0, 0)] - 1) % MOD)

Submission status: Accepted

Solution code:
def examA():
    S = {0:"pon",1:"pon",2:"hon",3:"bon",4:"hon",5:"hon",6:"pon",7:"hon",8:"pon",9:"hon"}
    N = SI()
    ans = S[int(N[-1])]
    print(ans)
    return

def examB():
    K = I()
    S = SI()
    N = len(S)
    if N<=K:
        ans = S
    else:
        ans = S[:K]+"..."
    print(ans)
    return

def examC():
    A, B, H, M = LI()
    a = abs(H*30 - M*5.5)
    deg = min(360-a,a)*math.pi/180
    #print(deg)
    ans = (A**2 + B**2 - 2*A*B*math.cos(deg))**(0.5)
    print(ans)
    return

def examD():

    N, M = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)

    ans = [-1]*N

    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = now
                    que.append(ne)
        return W
    ans = bfs(N,0,V)
    for a in ans:
        if a==-1:
            print("No")
            return
    print("Yes")
    for v in ans[1:]:
        print(v+1)
    return

def examE():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    N = I()
    D = defaultdict(int)
    D0 = [0,0]
    D00 = 0
    for i in range(N):
        A = LI()
        if A[0]==0 and A[1]==0:
            D00 += 1
            continue
        if A[0]==0:
            D0[0] += 1
            continue
        if A[1]==0:
            D0[1] += 1
            continue
        if A[1]<0:
            A = [-A[0],-A[1]]
        if A[0]<0:
            k = gcd(-A[0],A[1])
            V = [A[0] // k, A[1] // k]
        else:
            k = gcd(A[0],A[1])
            V = [A[0]//k,A[1]//k]
        D[(V[0], V[1])] += 1
    ans = 1
    ans *= (pow(2,D0[0],mod)-1 + pow(2,D0[1],mod)-1 +1)
    ans %= mod
    #print(ans)
    #print(D)
    C = deepcopy(D)
    for (a,b),d in C.items():
        if D[(a,b)]==0:
            continue
        if D[(-b,a)]>0:
            ans *= (pow(2,d,mod)-1 + pow(2,D[(-b,a)])-1 + 1)
            D[(-b,a)] = 0
        elif D[(b,-a)]>0:
            ans *= (pow(2,d,mod)-1 + pow(2,D[(b,-a)])-1 + 1)
            D[(b,-a)] = 0
        else:
            ans *= pow(2,d,mod)
        ans %= mod
        #print(ans,a,b,d)
    ans = (ans+mod+D00-1)%mod
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

mod = 10**9 + 7
def gcd(x, y):
    x = abs(x); y = abs(y)
    while y:
        x, y = y, x%y
    return x

azr = bzr = czr = 0
n = ni()
d = dict()
for _ in range(n):
    a, b = nm()
    if a < 0:
        a = -a
        b = -b
    if a == b == 0:
        czr += 1
    elif a == 0 :
        azr += 1
    elif b == 0:
        bzr += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if (a, b) not in d:
            d[(a, b)] = 0
        d[(a, b)] += 1

ans = (pow(2, azr, mod) + pow(2, bzr, mod) - 1) % mod
for x, y in d.items():
    if d[x] == 0:
        continue
    p, q = x
    if q < 0:
        q = -q
        p = -p
    if (q, -p) in d:
        z = d[(q, -p)]
        ans = ans * (pow(2, y, mod) + pow(2, z, mod) - 1) % mod
        d[x] = d[(q, -p)] = 0
    else:
        ans = ans * pow(2, y, mod) % mod
        d[x] = 0
ans = (ans - 1 + czr) % mod
print(ans)

Submission status: Accepted

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

n = int(input())

ab = [list(map(int, input().split())) for i in range(n)]

ans = 0
d = defaultdict(int)
s = set()
for a,b in ab:
    if a == 0 and b == 0:
        ans += 1
        continue
    if a == 0:
        b = 1
        x = 1
        y = 0
    elif b == 0:
        a = 1
        x = 0
        y = 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a = -a
            b = -b
        x = b
        y = -a
        if x < 0:
            x = -x
            y = -y
    d[(a,b)] += 1
    k = tuple(sorted([(a,b), (x,y)]))
    s.add(k)

s = list(s)
n = len(s)
if n == 0:
    print(ans)
    exit()
DP = [0]*(n+1)
DP[0] = 1
for i in range(n):
    l,r = s[i]
    DP[i+1] = DP[i]*(1 + pow(2,d[l], mod)-1 + pow(2, d[r], mod)-1)
    DP[i+1] %= mod

ans += DP[-1]-1
ans %= mod
print(ans)

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

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

def solve(N: int, A: "List[int]", B: "List[int]"):
    s = {}
    for i in range(N):
        if A[i] == 0 and B[i] == 0:
            a, b = 0, 0
        elif A[i] == 0:
            a, b = 0, 1
        elif B[i] == 0:
            a, b = 1, 0
        else:
            g = gcd(A[i], B[i])
            a, b = A[i] // g, B[i] // g
        k = (a, b)
        if not k in s:
            s[k] = 0
        s[k] += 1
    count = 0
    checked = set()
    cums = []
    #print(s)
    for (a, b), cnt in s.items():
        if (a, b) in checked:
            continue
        checked.add((a, b))
        tmp = 0
        if a == 0 and b == 0:
            count += cnt
            #cum = cnt + 1
            #cums.append(cum)
            #count += cnt + tmp
            continue
        if (-b, a) in s and (-b, a) not in checked:
            tmp += s[(-b, a)]
            checked.add((-b, a))
        if (b, -a) in s and (b, -a) not in checked:
            tmp += s[(b, -a)]
            checked.add((b, -a))
        if tmp > 0:
            cum = pow(2, cnt, MOD) + pow(2, tmp, MOD) - 1
            cum %= MOD
            cums.append(cum)
            count += cnt + tmp
    #print(cums, count)
    ret = pow(2, (N - count), MOD)
    for cum in cums:
        ret *= cum
        ret %= MOD
    if (0, 0) in s:
        ret += s[(0, 0)]
    ret -= 1
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import bisect
import collections
import sys
import math
from fractions import Fraction

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]", B: "List[int]"):
    ab = collections.defaultdict(lambda: [0, 0])  # [posi][nega]
    zeros = 0
    for i in range(N):
        if A[i] == B[i] == 0:
            zeros += 1
        elif A[i] == 0:
            ab[0][1] += 1
        elif B[i] == 0:
            ab[0][0] += 1
        elif A[i] * B[i] >= 0:
            v = math.gcd(A[i], B[i])
            ab[(abs(B[i]) // v, abs(A[i]) // v)][0] += 1
        else:
            v = math.gcd(A[i], B[i])
            ab[(abs(A[i]) // v, abs(B[i]) // v)][1] += 1

    # check B[i] ==0
    ans = 1
    for x, y in ab.values():
        pattern = 1  # not select
        pattern += 2 ** x - 1
        pattern += 2 ** y - 1
        ans = ans * pattern % MOD
    print((ans - 1) % MOD + zeros)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
from math import gcd
n=N()
mod=10**9+7
az=0
bz=0
zz=0
l=LL(n)
ans=1
import collections
d=collections.defaultdict(int)
for a,b in l:
    if a==0 and b==0:
        zz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
    elif a<0 and b<0:
        a=-a
        b=-b
        x=gcd(a,b)
        d[(a//x,b//x)]+=1
    elif a<0:
        a=-a
        x=gcd(a,b)
        d[(-a//x,b//x)]+=1
    elif b<0:
        b=-b
        x=gcd(a,b)
        d[(-a//x,b//x)]+=1
    else:
        x=gcd(a,b)
        d[(a//x,b//x)]+=1
pow2=[1]*(n+1)
t=1
for i in range(1,n+1):
    t*=2
    t%=mod
    pow2[i]=t
ans*=(1+(pow2[az]-1)+(pow2[bz]-1))
for a,b in list(d.keys()):
    if a>0 and b>0:
        x=d[(a,b)]
        y=d[(-b,a)]
        ans*=(1+(pow2[x]-1)+(pow2[y]-1))
        ans%=mod
    else:
        if not (b,-a) in d:
            ans*=pow2[d[(a,b)]]
            ans%=mod
print((ans+zz-1)%mod)

Submission status: Accepted

Solution code:
mod = 1000000007
from collections import defaultdict
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
ca = 0
cb = 0
cc = 0
for i in range(N):
    a,b = AB[i]
    if a==0 and b!=0:
        ca += 1
        continue
    elif a!=0 and b==0:
        cb += 1
        continue
    elif a==0 and b==0:
        cc += 1
        continue
    a_ = abs(a)
    b_ = abs(b)
    d = gcd(a,b)
    if d != 0:
        a //= d
        b //= d
    if a < 0:
        a *= -1
        b *= -1
    if b>0:
        d1[(a,b)] += 1
    else:
        d2[(a,b)] += 1
        d1[(-b,a)] += 0

ans = pow(2,ca)+pow(2,cb)-1
for a,b in d1:
    x = d1[(a,b)]
    y = d2[(b,-a)]
    ans *= pow(2,x,mod)+pow(2,y,mod)-1
    ans %= mod
ans -= 1
ans += cc
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
readline = sys.stdin.readline

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

C = [(a,b) for a,b in AB if (a==0 and b==0)]
AB = [(a,b) for a,b in AB if not (a==0 and b==0)]
P = 1000000007
def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret

def gcd(_a,_b):
    a,b = abs(_a), abs(_b)
    if a < b:
        a,b = b,a
    if b == 0:
        return a
    while a % b != 0:
        a, b = b, a % b
    
    return b

def norm(a,b):
    g = gcd(a,b)
    a,b = a//g, b//g
    if a < 0:
        a,b = -a, -b
    if a == 0 and b < 0:
        b = -b
    return a,b

dic = defaultdict(int)
for a,b in AB:
    a,b = norm(a,b)
    dic[(a,b)] += 1

ans = len(C)
keys = list(dic.keys())

x = 1
for a,b in keys:
    n = dic[(a,b)]
    if n != 0:
        p,q = norm(b, -a)
        m = dic[(p,q)]
        x = x * (mod_pow(2, n) + mod_pow(2, m) - 1)
        x %= P
        dic[(p,q)] = 0
        dic[(a,b)] = 0
x -= 1
ans += x
ans %= P
print(ans)

Submission status: Accepted

Solution code:
import math
import sys
from collections import defaultdict



MOD = 1000000007

def get_pair(val):
    a, b = val
    paired_a = -b
    paired_b = a
    if paired_a < 0 or (paired_a == 0 and paired_b < 0):
        paired_a = -paired_a
        paired_b = -paired_b
    return (paired_a, paired_b)


def main():
    N = int(input())
    lines = sys.stdin.read().split('\n')
    vals = [0] * N
    zero_count = 0
    for ix, line in enumerate(lines):
        if not line:
            continue
        a, b = map(int, line.split(' '))
        if a == 0 and b == 0:
            zero_count += 1
            vals[ix] = (0, 0)
            continue
        gcd = math.gcd(a, b)
        if (a < 0 or (a == 0 and b < 0)):
            gcd = -gcd
        a //= gcd
        b //= gcd
        vals[ix] = (a,b)

    vals_set = defaultdict(int)
    for val in vals:
        if val == (0, 0):
            continue
        vals_set[val] += 1

    processed_set = set()
    result = 1
    for val, count in vals_set.items():
        if val in processed_set:
            continue
        # print(f'processing val: {val}')
        processed_set.add(val)
        # print(f'val: {val}')
        pair = get_pair(val)
        mult = pow(2, count, MOD)
        if pair in vals_set:
            # print(f'processing pair: {pair}')
            processed_set.add(pair)
            mult += pow(2, vals_set[pair], MOD) - 1 # don't double count 0 of each
        # print(f"mult: {mult}")
        result = (result * mult) % MOD

    result = (result - 1 + zero_count + MOD) % MOD
    # print(f'zero_count: {zero_count}')
    print(result)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
MOD = 1000000007
inpl = lambda: list(map(int,input().split()))
groups = defaultdict(int)
null = 0
N = int(input())
for _ in range(N):
    A, B = inpl()
    if A == 0 and B == 0:
        null += 1
    elif A == 0:
        groups[(0,1)] += 1
    elif B == 0:
        groups[(1,0)] += 1
    else:
        g = gcd(A,B)
        A //= g
        B //= g
        if A < 0:
            A *= -1
            B *= -1
        groups[(A, B)] += 1
ans = 1
for k in list(groups.keys()):
    A, B = k
    if B <= 0:
        C, D = -B, A
    else:
        C, D = B, -A
    groups[(C,D)]
for k, v in groups.items():
    A, B = k
    if B <= 0:
        continue
    u = groups[(B,-A)]
    p = pow(2,v,MOD) + pow(2,u,MOD) - 1
    ans *= p
    ans %= MOD
ans -= 1
ans += null
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import gcd


MOD = 10**9 + 7

n = int(input())

cnt = {}

zero_cnt = 0
for i in range(n):
    a, b = map(int, input().split())
    if (a,b) == (0,0):
        zero_cnt += 1
        continue
    g = gcd(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

ans = 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
print(ans % MOD)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

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

def main():
    md = 1000000007
    n = II()
    cnt = {}
    cnt[(0, 0)] = [0, 0]
    zero = 0
    for _ in range(n):
        a, b = MI()
        if a * b == 0:
            if a == b == 0:
                zero += 1
            elif a == 0:
                cnt[(0, 0)][0] += 1
            else:
                cnt[(0, 0)][1] += 1
            continue
        par = a * b > 0
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        a //= g
        b //= g
        if par:
            cnt.setdefault((a, b), [0, 0])
            cnt[(a, b)][1] += 1
        else:
            cnt.setdefault((b, a), [0, 0])
            cnt[(b, a)][0] += 1
    # print(cnt)
    ans = 1
    for x, y in cnt.values():
        cur = pow(2, x, md) + pow(2, y, md) - 1
        ans = ans * cur % md
    ans += zero
    ans = (ans - 1) % md
    print(ans)

main()

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
ab = {}
ans = 0
mod = 10 ** 9 + 7


def go(a, b):
    if a == 0 and b == 0:
        return 0, 0
    elif a == 0:
        return 0, 1
    elif b == 0:
        return 1, 0
    c = gcd(a, b)
    a, b = a // c, b // c
    if a < 0:
        a *= - 1
        b *= - 1
    return a, b


def la(a, b):
    r = max((a, b), go(b, -a))
    if r == (a, b):
        return r, 0
    else:
        return r, 1


zero = 0
for i in range(n):
    a, b = [int(i) for i in input().split()]
    a, b = go(a, b)
    if a == b == 0:
        zero += 1
    else:
        l, ind = la(a, b)
        if l in ab:
            ab[l][ind] += 1
        else:
            ab[l] = [0, 0]
            ab[l][ind] += 1
ans = 1
for i in ab:
    ans *= pow(2, ab[i][0], mod) + pow(2, ab[i][1], mod)-1
    ans %= mod
print((ans + zero-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd
import sys

input=sys.stdin.readline

N=int(input())
dicplus={}
dicminus={}
dicinf=0
diczero=0
dicnan=0
for i in range(N):
    a,b=map(int,input().split())
    g=gcd(a,b)
    if a==0 and b==0:
        dicnan+=1
    elif a==0:
        diczero+=1
    elif b==0:
        dicinf+=1
    else:
        A=a//g
        B=b//g
        if A*B>0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicplus:
                dicplus[(A,B)]=0
            dicplus[(A,B)]+=1
        elif A*B<0:
            A=abs(A)
            B=abs(B)
            if (A,B) not in dicminus:
                dicminus[(A,B)]=0
            dicminus[(A,B)]+=1


ans=1
mod=10**9+7
for a,b in dicplus:
    if (b,a) in dicminus:
        ans*=(pow(2,dicplus[(a,b)],mod)-1+pow(2,dicminus[(b,a)],mod)-1+1)
        ans%=mod
    else:
        ans*=pow(2,dicplus[(a,b)],mod)
        ans%=mod

for a,b in dicminus:
    if (b,a) not in dicplus:
        ans*=pow(2,dicminus[(a,b)],mod)
        ans%=mod

ans*=(pow(2,dicinf,mod)-1+pow(2,diczero,mod)-1+1)
ans%=mod
ans=ans-1+dicnan
ans%=mod

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
from math import gcd

MOD = 1000000007
(N,) = [int(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for i in range(N)]

count00 = 0
badTerms = defaultdict(lambda: list([0, 0]))
for i, (a, b) in enumerate(AB):
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            count00 += 1
        elif a == 0:
            badTerms[0][0] += 1
        else:
            assert b == 0
            badTerms[0][1] += 1

    else:

        assert a * b != 0
        isNeg = a * b < 0

        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0 and b < 0:
            a *= -1
            b *= -1
        if a < 0 or b < 0:
            a, b = -b, a
        if a < 0 and b < 0:
            a *= -1
            b *= -1
        assert a > 0 and b > 0

        if isNeg:
            badTerms[(a, b)][0] += 1
        else:
            badTerms[(a, b)][1] += 1

ways = 1

for key, (negCount, posCount) in badTerms.items():
    ways *= pow(2, negCount, MOD) + pow(2, posCount, MOD) - 1
    ways %= MOD

if count00:
    # Can't work with anything else, must be taken on it's own
    ways += count00


print((ways - 1) % MOD)

Submission status: Accepted

Solution code:
N = int(input())
D = {}

def gcd(x,y):
    if x>y: x,y=y,x
    while x:
        x,y=y%x,x
    return y

for _ in range(N):
    A, B = map(int, input().split())
    if   A==0 and B==0: key=(0,0)
    elif A==0: key=(0,1)
    elif B==0: key=(1,0)
    else:
        if A<0:
            A=-A
            B=-B
        g = gcd(A,abs(B))
        key = (A//g, B//g)

    if key not in D: D[key]=0
    D[key]+=1

mod = 10**9+7

ans = 1
n00 = 0
for k1, v1 in D.items():
    if k1==(0,0):
        n00+=v1
        continue
    if v1==0: continue
        
    k2 = (k1[1], -k1[0]) if k1[1]>0 else (-k1[1], k1[0])
    if k2 not in D:
        ans = ans * pow(2, v1, mod) % mod
    else:
        v2 = D[k2]
        m = (pow(2, v1, mod) + pow(2, v2, mod) - 1) % mod
        ans = ans * m % mod
        D[k2]=0
        
print((ans+n00-1)%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
from math import gcd
import sys
input = lambda: sys.stdin.readline().strip()

n = int(input())
indet = 0
d = {}
for i in range(n):
    a, b = [int(x) for x in input().split()]
    if b < 0:
        a *= -1
        b *= -1
    if a == 0 and b == 0:
        indet += 1
        continue
    elif a == 0:
        p = (0, 1)
    elif b == 0:
        p = (-1, 0)
    else:
        g = gcd(a, b)
        p = (a // g, b // g)
    d[p] = d.get(p, 0) + 1

sizes = []
ignore = set()
for p, size in d.items():
    if p not in ignore:
        a, b = -p[1], p[0]
        if b < 0:
            a *= -1
            b *= -1
        if (a, b) in d:
            ignore.add((a, b))
            sizes.append((size, d[(a, b)]))
        else:
            sizes.append((size, 0))
M = 10**9 + 7
ans = 1
for n1, n2 in sizes:
    ans *= (pow(2, n1, M) + pow(2, n2, M) - 1)
    ans %= M
print((indet + ans - 1) % M)

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
plus = {}
minus = {}
mod = 10**9 + 7
gen = pow(10,19)
zero = 0 # 両方
for i in range(n):
    a,b = map(int,input().split())
    if a == b == 0:
        zero += 1
        continue
    if a < 0:a,b = -a,-b
    elif a == 0 and b < 0:b = -b
    g = gcd(a,b)
    a //= g
    b //= g
    key = a*gen + b
    if b > 0:
        if key not in plus.keys():plus[key] = 0
        plus[key] += 1
    else:
        if key not in minus.keys():minus[key] = 0
        minus[key] += 1
ans = pow(2,n-zero,mod)
for k,v in plus.items():
    a = k//gen
    b = k%gen
    opo = b*gen - a
    if opo in minus.keys():
        o = minus[opo]
        ans = ans*pow(2,v*(mod-2)%(mod-1),mod) + ans*pow(2,o*(mod-2)%(mod-1),mod) - ans*pow(2,(v+o)*(mod-2)%(mod-1),mod)
        ans %= mod
print((ans + zero - 1)%mod)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.buffer.readline

    N = int(input())
    cnt = {}
    zz = 0
    for _ in range(N):
        a, b = map(int, input().split())
        if a == b == 0:
            zz += 1
            continue
        if a < 0:
            a = -a
            b = -b
        elif a == 0:
            if b < 0:
                b = -b
        g = gcd(abs(a), abs(b))
        x = (a // g, b // g)
        if x in cnt:
            cnt[x] += 1
        else:
            cnt[x] = 1

    ans = 1
    num = 0
    for x in cnt:
        if cnt[x] == 0:
            continue
        a, b = x
        if b > 0:
            y = (b, -a)
        else:
            y = (-b, a)
        if y in cnt:
            nx = cnt[x]
            ny = cnt[y]
            cnt[y] = 0
            ans = (ans * ((pow(2, nx, mod) - 1) + (pow(2, ny, mod) - 1) + 1)%mod)%mod
        else:
            num += cnt[x]
    ans = (ans * pow(2, num, mod))%mod
    ans = (ans - 1)%mod
    print((ans + zz)%mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())

dic = {}
zz = 0
az = 0
bz = 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 = math.gcd(A,B)
        A //= g
        B //= g

        if A*B > 0:
            now = (A,B)
            ind = 0
        else:
            now = (-1*B,A)
            ind = 1

        if now[0] < 0:
            now = (-1 * now[0] , -1 * now[1])
            

        if now not in dic:
            dic[now] = [0,0]
        dic[now][ind] += 1

mod = 10**9+7
ans = pow(2,az,mod) + pow(2,bz,mod) - 1

for i in dic:

    aa,bb = dic[i]
    now = pow(2,aa,mod) + pow(2,bb,mod) - 1
    ans *= now
    ans %= mod

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read


n,*ab = [int(i) for i in read().split()]

M = iter(ab)
d = {}

zero = 0
from math import gcd
for a,b in zip(M,M):
    if a==b==0:
        zero += 1
        continue
    g = gcd(a,b)
    a//=g
    b//=g
    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 = 1000000007
ans = 1

pow2 = [1]
for _ in range(200005):
    pow2.append(pow2[-1]*2%MOD)

#print(d)
for (a,b),(k,l) in d.items():
    ans *= pow2[k]+pow2[l]-1
    ans %= MOD


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

Submission status: Accepted

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

def gcd(x, y):
    x = abs(x)
    y = abs(y)

    if x < y:
        x, y = y, x

    while y:
        x, y = y, x%y
        
    return x

N = int(input())
seen = dict()
zeroes = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeroes += 1
        continue
    
    if a < 0 or a == 0 and b < 0:
        a, b = -a,-b
    if b <= 0:
        a, b = -b, a
        flip = 1
    else:
        flip = 0
    g = gcd(a,b)
    a//=g
    b//=g
    if (a,b) not in seen:
        seen[(a,b)] = [0,0]
    
    seen[(a,b)][flip] += 1

MOD = 10 ** 9 + 7
    
out = 1
for v in seen:
    a, b = seen[v]
    out *= (pow(2,a,MOD) + pow(2,b,MOD) - 1)
    out %= MOD
out -= 1

out += zeroes
out %= MOD
print(out)

Submission status: Accepted

Solution code:
import sys
from functools import cmp_to_key

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

mod = 1000000007
n = ni()
co = []
z = 0
for i in range(n):
    x = na()
    if x[0] == 0 and x[1] == 0:
        z += 1
    else:
        co.append(x)
n = len(co)

for c in co:
    if c[1] < 0 or c[1] == 0 and c[0] < 0:
        c[1] = -c[1]
        c[0] = -c[0]

mod = 1000000007
ans = 1

co.sort(key=cmp_to_key(lambda x,y: -(x[0]*y[1]-y[0]*x[1])))

p = 0
while p < n and co[p][0] > 0:
    p += 1

col = []
i = 0
rem = n
while i < n:
    if co[i][0] <= 0:
        break
    while p < n and co[i][0]*co[p][0]+co[i][1]*co[p][1] > 0:
        p += 1

    op = p
    while p < n and co[i][0]*co[p][0]+co[i][1]*co[p][1] == 0:
        p += 1

    oi = i
    while i < n and co[i][0]*co[oi][1]-co[i][1]*co[oi][0] == 0:
        i += 1

    if p-op > 0:
        ans = ans * (pow(2, i-oi, mod) + pow(2, p-op, mod) - 1) % mod
        rem -= (p-op) + (i-oi)

ans = ans * pow(2, rem, mod) % mod
print((ans+z+mod-1)%mod)