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 sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+100
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        elif A==0:
            d[0]=d.get(0,0)+1
        else:
            sa=sb=1
            if A<0:
                sa=-1
                A*=-1
            if B<0:
                sb=-1
                B*=-1

            g=math.gcd(A,B)
            A=A//g
            B=B//g
            if sa==-1 and sb==-1:
                t=(A,B)
            elif sb==-1:
                t=(-A,B)
            else:
                t=(sa*A,sb*B)
            d[t]=d.get(t,0)+1
    
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):
        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        if k==m:
            ik=0
        elif k==0:    
            ik=m
        elif k[0]<0:
            ik=(k[1],-k[0])
        else:
            ik=(-k[1],k[0])
        #print(ik)
        if ik in ks:
            d1,d2=d[k],d[ik]
            tot=(tot*((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)%mod)%mod
            d[ik]=-1

        else:
            tot=(tot*pow(2,d[k],mod))%mod

    tot-=1
    tot+=d.get(-m,0)%mod
    tot%=mod
    
    print(tot)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from collections import defaultdict
from math import gcd

P=defaultdict(lambda :0)
n=int(input())
AB=[tuple(map(int,input().split()))for i in range(n)]

zero=0 #これがいるときは一匹のみ
a0=0 #a0とb0はお互いがペア
b0=0
for a,b in AB:
    g=gcd(a,b)
    if a==0 and b==0:
        zero+=1
    elif a==0:
        a0+=1
    elif b==0:
        b0+=1
    elif a<0:
        a//=-g
        b//=-g
        P[(a,b)]+=1
    else:
        a//=g
        b//=g
        P[(a,b)]+=1

ans=1
others=n-zero-a0-b0
mod=1000000007
from copy import copy
k=copy(list(P.keys()))
for p in k:
    me=P[p]
    if me==0:
        continue
    a,b=p
    oppidx=(-b,a) if b<0 else (b,-a)
    opp=P[oppidx]
    if P[oppidx]!=0:
        others-=me+opp
        ans*=pow(2,me,mod)+pow(2,opp,mod)-1
        ans%=mod
    P[p]=0
    P[oppidx]=0

if a0!=0 and b0!=0:
    ans*=pow(2,a0,mod)+pow(2,b0,mod)-1
    ans%=mod
elif a0!=0 or b0!=0:
    others+=a0+b0

ans*=pow(2,others,mod)
ans%=mod
ans=ans+zero-1
ans%=mod

print(ans)

"""
7
0 1
0 1
1 0
1 0
1 -1
1 1
1 3
"""

Submission status: Accepted

Solution code:
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
d = dict()
zeros = 0
a_zeros = 0
b_zeros = 0
for _ in range(N):
    a, b = tuple(map(int, input().split()))
    if not any((a, b)):
        zeros += 1
        continue
    if not a:
        a_zeros += 1
        continue
    if not b:
        b_zeros += 1
        continue
    g = gcd(a, b) * (a // abs(a))
    p = a // g, b // g
    d[p] = d.get(p, 0) + 1
counts = dict()
for k, v in d.items():
    a, b = k
    if counts.get((b, -a), False) or counts.get((-b, a), False):
        continue
    counts[k] = v, d.get((b, -a), 0) + d.get((-b, a), 0)
total = 1
for k, v in counts.items():
    a, b = v
    total = (total * (pow(2, a, MOD) + pow(2, b, MOD) - 1)) % MOD
total = (total * (pow(2, a_zeros, MOD) + pow(2, b_zeros, MOD) - 1)) % MOD
print((total + zeros + MOD - 1) % MOD)

Submission status: Accepted

Solution code:
import numpy as np

mod = 10 ** 9 + 7


def regularize(a, b):
    if a < 0 or (a == 0 and b < 0):
        a, b = -a, -b
    if b > 0:
        return 0, a, b
    else:
        return 1, -b, a


n = int(input())
edict = dict()
zero_num = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero_num += 1
        continue
    ab_gcd = np.gcd(a, b)
    a, b = a // ab_gcd, b // ab_gcd
    index, a, b = regularize(a, b)
    key = (a, b)
    if key not in edict.keys():
        edict[key] = [0, 0]
    edict[key][index] += 1


not_zeros = 1
for key in edict.keys():
    a, b = key
    pp, pm = edict[key]
    not_zeros *= (pow(2, pp, mod) + pow(2, pm, mod) - 1) % mod
    not_zeros %= mod

print((zero_num + not_zeros - 1) % mod)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(500000)

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

def frac(a,b):
    d = gcd(abs(a),abs(b))
    if a<0:
        a = -a
        b = -b
    return (a//d,b//d)

def inv(a,b):
    return frac(-b,a)

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())

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

    arg = defaultdict(int)
    zero = 0
    for v in vec:
        if v[0] == 0 and v[1] == 0:
            zero += 1
        elif v[1]==0:
            arg[float("inf")] += 1
            arg[0] += 0
        elif v[0]==0:
            arg[0] += 1
            arg[float("inf")] += 0
        else:
            arg[frac(v[0],v[1])] += 1
            arg[frac(-v[1],v[0])] += 0

    pair = []
    ll = lambda : False

    checked_list = defaultdict(ll)
    for key in arg:
        if not checked_list[key]:
            if key==0:
                pair.append([arg[0],arg[float("inf")]])
                checked_list[float("inf")] = True
            elif key==float("inf"):
                pair.append([arg[0],arg[float("inf")]])
                checked_list[0] = True

            else:
                #print(key)
                pair.append([arg[key],arg[inv(*key)]])
                #print(pair)
                checked_list[inv(*key)] = True

    mod = 1000000007

    ans = 1

    for p1,p2 in pair:
        ans *= pow(2,p1,mod) + pow(2,p2,mod) - 1
        ans %= mod

    ans += zero
    ans %= mod

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import gcd
from collections import defaultdict


n = readint()

mod = 1000000007

d = defaultdict(int)

for i in range(n):
    a,b = readints()
    g = gcd(a,b)
    if g!=0:
        a//=g
        b//=g
    if a<0:
        a*=-1
        b*=-1
    elif a==0 and b<0:
        b*=-1
    d[(a,b)]+=1

ans = 1
k = tuple(d.keys())
ans2 = 0
for x in k:
    if x[0]>0:
        if x[1]>0:
            ans *= pow(2,d[x],mod)+pow(2,d[(x[1],-x[0])],mod)-1
        elif x[1]<0:
            if d[(-x[1],x[0])]==0:
                ans *= pow(2, d[x], mod)
        else:
            ans *= pow(2,d[x],mod)+pow(2,d[(x[1],x[0])],mod)-1
    else:
        if x[1]==0:
            ans2 += d[x]
        else:
            if d[(x[1], x[0])] == 0:
                ans *= pow(2, d[x], mod)
    ans %= mod

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

Submission status: Accepted

Solution code:
from math import gcd
from collections import Counter
n=int(input())

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

for i in range(n):
    ai,bi=iw[i]
    if bi<0:#biは正に設定
        iw[i][0]*=-1;iw[i][1]*=-1
    if bi==0 and ai<0:#biがゼロならaiは正かゼロ
        iw[i][0]*=-1
    if ai and bi:##互いに素にする
        g=gcd(ai,bi)
        iw[i][0]//=g;iw[i][1]//=g
    else:#どちらか0なら残りを1か0にする
        if ai:#biがゼロでaiが非ゼロ
            iw[i][0]=1
        elif bi:#aiがゼロでbiが非ゼロ
            iw[i][1]=1
    
iw = [tuple(iwi) for iwi in iw]
C=Counter(iw)
ans=1
mod=10**9+7
#print(C)
#ai bi=0,0は別に処理が要る
tmp=0
if (0,0) in C:
    tmp= C.pop((0,0))
#片方0も分けておく
if (0,1) in C and (1,0) in C:
    tmpx=C.pop((0,1))
    tmpy=C.pop((1,0))
    ans*=(pow(2,tmpx,mod)+pow(2,tmpy,mod)-1)
elif (0,1) in C :
    tmpx=C.pop((0,1))
    ans*=pow(2,tmpx,mod)
elif (1,0) in C :
    tmpx=C.pop((1,0))
    ans*=pow(2,tmpx,mod)

for ai,bi in C:
    if C[(ai,bi)]<0:##集計済
        continue

    if ai>0:#ai>0
        if (-bi,ai) in C and C[(-bi,ai)]>0:
            ans*=(pow(2,C[(-bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(-bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    else:#ai<0
        if (bi,-ai) in C and C[(bi,-ai)]>0:
            ans*=(pow(2,C[(bi,-ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,-ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    #print((ai,bi),C[(ai,bi)],ans)
print((ans+tmp-1)%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

MOD = 10 ** 9 + 7
N = int(input())
AB = []
NUMS = defaultdict(int)
zeros = 0
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

    if a == b == 0:
        zeros += 1
        continue

    d = gcd(a, b)
    x, y = a // d, b // d
    if y < 0:
        x, y = -x, -y
    NUMS[x, y] += 1

todo = set(NUMS.keys())
ans = 1
while todo:
    x, y = todo.pop()
    if (-y, x) in todo or (y, -x) in todo:
        assert not ((-y, x) in todo and (y, -x) in todo)
        if (-y, x) in todo:
            v = NUMS[-y, x]
        else:
            v = NUMS[y, -x]
        ans = ans * (2 ** NUMS[x, y] + 2 ** v - 1) % MOD
        todo -= {(-y, x), (y, -x)}
    else:
        ans = ans * (2 ** NUMS[x, y]) % MOD
ans += zeros - 1
print(ans % MOD)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from math import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    d=defaultdict(lambda:[0,0])
    zz=0
    for _ in range(N):
        a,b=map(int,input().split())
        g=gcd(a,b)
        if g==0:
            zz+=1
        else:
            a//=g
            b//=g
            if a<0:
                a*=-1
                b*=-1
            if a*b>0:
                d[(a,b)][0]+=1
            elif a*b<0:
                d[(-b,a)][1]+=1
            else:
                if a:
                    d[(1,0)][0]+=1
                else:
                    d[(1,0)][1]+=1
    l=[]
    other=0
    for k,a in d.items():
        if a[0] and a[1]:
            l.append((a[0],a[1]))
        else:
            other+=sum(a)
    ans=pow(2,other,MOD)
    ans%=MOD
    dp=[[0]*2 for _ in range(len(l)+1)]
    dp[0][0]=1
    for i in range(len(l)):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        dp[i+1][1]=(dp[i][0]+dp[i][1])*(pow(2,l[i][0],MOD)+pow(2,l[i][1],MOD)-2)
        dp[i+1][0]%=MOD
        dp[i+1][1]%=MOD
    ans*=sum(dp[-1])
    ans-=1
    ans+=zz
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from math import gcd
import sys
input = sys.stdin.readline
n = int(input())
same, diff, zero_a, zero_b, zero_zero = 0, 0, 0, 0, 0
same_cnt = Counter()
diff_cnt = Counter()

for i in range(n):
    a, b = map(int, input().split())
    if a == b == 0:
        zero_zero += 1
    elif a == 0:
        zero_a += 1
    elif b == 0:
        zero_b += 1
    elif a * b > 0:
        x = gcd(a, b)
        a, b = a // x, b // x
        same += 1
        same_cnt[(abs(a), abs(b))] += 1
    else:
        x = gcd(a, b)
        a, b = a // x, b // x
        diff += 1
        diff_cnt[(abs(a), -abs(b))] += 1


ans = 1
mod = 10 ** 9 + 7

for (a, b) in diff_cnt.keys():
    s = same_cnt[(-b, a)]
    d = diff_cnt[(a, b)]
    if s > 0:
        same -= s
        diff -= d
        ans = ans * (pow(2, s, mod) + pow(2, d, mod) - 1) % mod

ans = ans * pow(2, same + diff, mod) % mod

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

Submission status: Accepted

Solution code:
def f():
    return [0,0]

from collections import defaultdict
import math
mod=1000000007
n=int(input())
dic=defaultdict(f)
x=[]
zerozero,azero,bzero=0,0,0
two=[1]

for i in range(n):
    two.append(two[-1]*2%mod)

for _ in range(n):
        
    a,b=map(int,input().split())
    if a==0 and b==0: zerozero+=1
    elif a==0: azero+=1
    elif b==0: bzero+=1
    else:
        k=math.gcd(a,b)
        a//=k;b//=k
        if a<0: a*=-1;b*=-1
        if a*b>0: dic[(a,b)][0]+=1
        else: dic[(-b,a)][1]+=1

for (a,b) in dic:
    x.append(dic[(a,b)])
x.append([azero,bzero])
ans=1
for [p,q] in x:
    ans*=(two[p]+two[q]-1)
    ans%=mod

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

Submission status: Accepted

Solution code:
from collections import Counter
from fractions import Fraction
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        f = Fraction(a, b)
        ct[(f.numerator, f.denominator)] += 1
ans = pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in ct.keys():
    if (a, b) in visited:
        continue
    inv = Fraction(-b, a)
    ia, ib = inv.numerator, inv.denominator
    visited.add((a, b))
    visited.add((ia, ib))
    tmp = pow(2, ct[(a, b)], MOD) + pow(2, ct[(ia, ib)], MOD) - 1
    ans *= tmp
    ans %= MOD
ans += Allzero
print((ans-1) % MOD)

Submission status: Accepted

Solution code:
import sys
from math import gcd
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    zero, inf, ng = 0, 0, 0
    for x, y in F:
        if x == 0 and y == 0: ng += 1
        elif x == 0: inf += 1
        elif y == 0: zero += 1
        else: 
            g = gcd(abs(x), abs(y))
            if x < 0:
                y *= -1
                x *= -1
            x //= g
            y //= g
            tan = (y, x)
            if tan in D: D[tan] += 1
            else: D[tan] = 1

    ans = 1
    ans *= (pow(2, zero, mod) + pow(2, inf, mod) - 1) % mod
    ans %= mod
    used = set()
    for key in D:
        if key not in used:
            this = D[key]
            used |= {key}
            y, x = key
            rev = ((-x, y) if y > 0 else (x, -y))
            op = (0 if rev not in D else D[rev])
            used |= {rev}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    ans += ng
    ans %= mod
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import math


def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


n = int(input())
ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))

my_dict = dict()

ab_mod = []
for item in ab:
    a, b = item
    if a == 0 and b == 0:
        ab_mod.append((0, 0))
    elif a == 0:
        ab_mod.append((0, 1))
    elif b == 0:
        ab_mod.append((1, 0))
    else:
        gcd = math.gcd(abs(a), abs(b))
        if a < 0:
            a = -a
            b = -b
        ab_mod.append((a // gcd, b // gcd))

for item in ab_mod:
    if item not in my_dict:
        my_dict[item] = 1
    else:
        my_dict[item] += 1


if (0, 0) in my_dict:
    num_dame = my_dict.pop((0, 0))
else:
    num_dame = 0

num_total = n - num_dame
dame_tuple = []

for item in my_dict:
    a, b = item
    val1 = my_dict[item]
    if (b, -a) in my_dict:
        val2 = my_dict[(b, -a)]
        dame_tuple.append((val1, val2))
        num_total -= (val1 + val2)

ret = 1

ret *= modpow(2, num_total, 10 ** 9 + 7)


for item in dame_tuple:
    val1, val2 = item
    zenbu = modpow(2, val1 + val2, 10 ** 9 + 7)
    dame1 = modpow(2, val1, 10 ** 9 + 7) - 1
    dame2 = modpow(2, val2, 10 ** 9 + 7) - 1
    ret *= (zenbu - (dame1 * dame2))

ret -= 1

print((ret + num_dame) % (10 ** 9 + 7))

Submission status: Accepted

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

MOD = 10 ** 9 + 7
n, *ab = map(int, sys.stdin.buffer.read().split())
ab_zero = 0
a_zero = 0
b_zero = 0
nonzero = defaultdict(int)

for a, b in zip(ab[0::2], ab[1::2]):
    if a == 0 and b == 0:
        ab_zero += 1
    elif a == 0:
        a_zero += 1
    elif b == 0:
        b_zero += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a, b = -a, -b
        if a == 0 and b < 0:
            b = -b
        nonzero[a, b] += 1

n -= ab_zero
# print(nonzero)

dame_pairs_pattern = 1
dame_pairs_cnt = 0

if a_zero > 0 and b_zero > 0:
    dame_pairs_pattern *= pow(2, a_zero, MOD) + pow(2, b_zero, MOD) - 1
    dame_pairs_cnt += a_zero + b_zero

checked = set()

for (a, b), cnt in nonzero.items():
    if (a, b) in checked:
        continue
    if b < 0:
        c, d = -b, a
    else:
        c, d = b, -a
    if (c, d) in nonzero:
        cnt2 = nonzero[c, d]
        dame_pairs_pattern *= pow(2, cnt, MOD) + pow(2, cnt2, MOD) - 1
        dame_pairs_pattern %= MOD
        dame_pairs_cnt += cnt + cnt2
        checked.add((c, d))

ans = dame_pairs_pattern * pow(2, n - dame_pairs_cnt, MOD) - 1

print((ans + ab_zero) % MOD)

Submission status: Accepted

Solution code:
MOD = 1000000007


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


def normalize(a, b):
    if a == 0 and b == 0:
        return 0, 0
    elif a != 0 and b == 0:
        return 1, 0
    elif a == 0 and b != 0:
        return 0, 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        return a, b


def rotate(a, b):
    if b > 0:
        return b, -a
    else:
        return -b, a


n = int(input())
dv = {}
for _ in range(n):
    a, b = map(int, input().split())
    a, b = normalize(a, b)
    dv[(a, b)] = dv.get((a, b), 0) + 1


counted = {k: False for k in dv.keys()}
nc = 1
for k, v in dv.items():
    if not counted[k]:
        if k != (0, 0):
            a0, b0 = k
            a1, b1 = rotate(a0, b0)
            w = dv.get((a1, b1), 0)

            nc *= 1 + (pow(2, v, MOD) - 1) + (pow(2, w, MOD)- 1)
            nc %= MOD

            # counted[(a0, b0)] = True
            counted[(a1, b1)] = True


nc += dv.get((0, 0), 0)

nc -= 1
nc %= MOD
print(nc)

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 = 1
    other = N
    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:
import sys
from math import gcd
input = sys.stdin.readline
n = int(input())
fish = dict()
zero = 0
for i in range(n):
    a, b = map(int, input().split())
    if a == 0:
        if b == 0:
            zero += 1
            continue
        else:
            b = -1
    elif b == 0:
        a = 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0 and b < 0:
            a = -a
            b = -b
        elif b < 0:
            a = -a
            b = -b

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

ans = 1
pair = []
mod = 10**9+7
while fish:
    key, value = fish.popitem()
    a, b = key
    if a < 0:
        if (b, -a) in fish:
            pair.append((value, fish[(b, -a)]))
            fish.pop((b, -a))
        else:
            ans *= pow(2, value, mod)
    elif b == 0:
        if (0, -1) in fish:
            pair.append((value, fish[(0, -1)]))
            fish.pop((0, -1))
        else:
            ans *= pow(2, value, mod)

    else:
        if (-b, a) in fish:
            pair.append((value, fish[(-b, a)]))
            fish.pop((-b, a))
        else:
            ans *= pow(2, value, mod)

for a, b in pair:
    temp = 1
    temp += pow(2, a, mod)-1
    temp += pow(2, b, mod)-1
    ans *= temp
    ans %= mod


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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 1000000007

    def pow_k(x, n):
        """
        O(log n)
        """
        if n == 0:
            return 1

        K = 1
        while n > 1:
            if n % 2 != 0:
                K *= x
            x *= x
            x = x%p
            n //= 2

        return (K * x)%p

    n = int(input())
    ab_0 = 0
    a_0 = 0
    b_0 = 0
    a_div_b_dict = defaultdict(int)
    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            ab_0 += 1
            continue
        if a == 0:
            a_0 += 1
            continue
        if b == 0:
            b_0 += 1
            continue
        if a*b > 0:
            front = ''
        else:
            front = '-'
        ab_gcd = math.gcd(a, b)
        a = str(abs(a//ab_gcd))
        b = str(abs(b//ab_gcd))
        a_div_b_dict[front+a.zfill(19)+b.zfill(19)] += 1
    # print(a_div_b_dict)
    visited = set()
    ans = 1
    for_loop = dict(a_div_b_dict)
    for key, value in for_loop.items():
        # print(visited)
        if key in visited:
            continue
        if key[0] == '-':
            front = key[1:20]
            back = key[20:]
            inverse = back + front
            visited.add(inverse)
            num = pow_k(2, value) + pow_k(2, a_div_b_dict[inverse])-1
            ans = (ans*num)%p
        else:
            front = key[:19]
            back = key[19:]
            inverse = '-' + back + front
            visited.add(inverse)
            num = pow_k(2, value) + pow_k(2, a_div_b_dict[inverse])-1
            ans = (ans*num)%p
    ans *= (pow_k(2, a_0) + pow_k(2, b_0)-1)
    ans += ab_0
    print((ans-1)%p)

Submission status: Accepted

Solution code:
MOD = 1000000007
N = int(input())

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

T1 = []
T2 = []
T0 = 0

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

for i in range(N): #第一象限、第二象限だけを考える
    if E[i][0] <= 0 and E[i][1] <= 0:
        E[i][0] = -E[i][0]
        E[i][1] = -E[i][1]
    elif E[i][0] >= 0 and E[i][1] < 0:
        E[i][0] = -E[i][0]
        E[i][1] = -E[i][1]

for i in range(N):
    if E[i][0] == E[i][1] == 0:
        T0 += 1
    elif E[i][0] > 0:
        if E[i][1] > 0:
            g = gcd(E[i][0], E[i][1])
            T1.append([E[i][0]//g, E[i][1]//g])
        else:
            T1.append([1, 0])
    else:
        if E[i][0] < 0:
            a, b = E[i][0], E[i][1]
            g = gcd(-a, b)
            T2.append([E[i][1]//g, ((-E[i][0])//g)])
        else:
            T2.append([1, 0])

from collections import defaultdict

D = defaultdict(lambda :[0, 0])

for i in range(len(T1)):
    D[(T1[i][0], T1[i][1])][0] += 1

for i in range(len(T2)):
    D[(T2[i][0], T2[i][1])][1] += 1

res = 1

for x, y in D.values():

    if x > 0 and y > 0:
        res *= (1 + pow(2, x, MOD) - 1 + pow(2, y, MOD) - 1)
        res %= MOD
    elif x > 0:
        res *= pow(2, x, MOD)
        res %= MOD
    elif y > 0:
        res *= pow(2, y, MOD)
        res %= MOD

print((res - 1 + T0) % MOD)

Submission status: Accepted

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

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

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)

Submission status: Accepted

Solution code:
n = int(input())

abl = [map(int, input().split()) for _ in range(n)]

from collections import defaultdict
dic = defaultdict(int)

# a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

ab0 = 0
a0 = 0
b0 = 0
for a,b in abl:
    if a == 0 and b == 0:
        ab0 += 1
        continue
    elif a == 0:
        a0 += 1
        continue
    elif b == 0:
        b0 += 1
        continue
    gc = abs(gcd(a,b))
    if a < 0:
        a, b = -a // gc, -b // gc
    else:
        a, b = a // gc, b // gc
    dic[(a,b)] += 1
MOD = 1000000007
ans = 1
used = defaultdict(int)
for (a,b) in dic:
    if b > 0:
        target = (b, -a)
    else:
        target = (-b, a)
    if target in dic:
        if used[target] == 0:
            ans *= pow(2, dic[(a,b)], MOD) + pow(2, dic[target], MOD) - 1
            used[(a,b)] = 1
    else:
        ans *= pow(2, dic[(a,b)], MOD)
    ans %= 1000000007

ans *= pow(2, a0, MOD) + pow(2, b0, MOD) - 1
ans %= 1000000007

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

Submission status: Accepted

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

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
mod = 10**9 + 7
l = 2*10**5 + 10

M = [1]  # i!のmod
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション
    if y < 0 or y > x:
        return 0
    elif x > l:  # O(min(y, x-y))
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return (ans * MI[y]) % mod
    else:  # O(1)
        ans = M[x]
        ans = (ans * MI[y]) % mod
        return (ans * MI[x-y]) % mod


M2 = [1]
for i in range(l):
    M2.append((M2[-1] * 2) % mod)

import math

D = {}
m = 0
for i in range(n):
    x = A[i][0]
    y = A[i][1]
    if x != 0 or y != 0:
        m += 1
        
        s = 0
        while not (x >= 0 and y > 0):
            x, y = -y, x
            s += 1
        g = math.gcd(x, y)
        x //= g
        y //= g
        try:
            D[(x,y)][s] += 1
        except:
            D[(x,y)] = [0,0,0,0]
            D[(x,y)][s] += 1
    
# print(D,m)

def minus(ll,x):
    ans0 = 0
    # hu = -1
    for i in range(2, x+1):
        ans0 = (ans0 + M2[ll-x] * C(x, i)) % mod
        # hu *= -1
    return ans0

# ans = M2[m] - 1 + (n-m)
ans = 1
DV = list(D.values())
ld = len(DV)
# print(DV)
for i in range(len(DV)):
    s = sum(DV[i])
    s0 = DV[i][0] + DV[i][2]
    s1 = DV[i][1] + DV[i][3]
    ans = (ans * (M2[s0] + M2[s1] - 1)) % mod
    # print(s,s0,s1)
    # print(minus(s) ,minus(s0) , minus(s1))
    # ans = (ans - minus(ld,s) + minus(s0,s-s0) + minus(s1,s-s1)) % mod

print((ans-1 + (n-m)) % mod)