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 collections import defaultdict
from math import atan2, gcd

N = int(input())
MOD = 1000000007

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

zero = 0
pos = []
neg = []
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    if a < 0:
        a = -a
        b = -b
    elif a == 0 and b > 0:
        b = -b
    if b >= 0:
        pos.append((a, b))
    else:
        neg.append((a, b))

for a, b in pos:
    if b != 0:
        g = gcd(a, b)
    else:
        g = a
    d[(a // g, b // g)][0] += 1
for a, b in neg:
    a, b = -b, a
    if b != 0:
        g = gcd(a, b)
    else:
        g = a
    d[(a // g, b // g)][1] += 1

ans = 1
for p, n in d.values():
    ans *= pow(2, p, MOD) + pow(2, n, MOD) - 1
    ans %= MOD

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

Submission status: Accepted

Solution code:
N = int(input())
data = [list(map(int,input().split())) for i in range(N)]
mod = 10**9+7
ans = 0

from math import gcd

A = []

for i in range(N):
    if data[i][0] == 0 and data[i][1] == 0:  #(0,0)の場合は以降取り除いて考える
        ans += 1
    else:                                 #各々の成分をgcdで割り、第1成分が非負になるように調整
        if data[i][0] < 0:
            data[i][0] *= -1
            data[i][1] *= -1
        g = gcd(data[i][0],data[i][1])
        data[i][0] //= g
        data[i][1] //= g
        if data[i][0] == 0:
            A.append((0,1))
        elif data[i][1] == 0:
            A.append((1,0))
        else:
            A.append((data[i][0],data[i][1]))


from collections import Counter

C = Counter(A)
D = []             #仲が悪いイワシの数の組

for i,j in list(C.keys()):
    if j <= 0:
        continue
    else:
        if j == 0:
            if C[(0,1)] > 0:
                D.append((C[(1,0)],C[(0,1)]))
        else:
            if C[(j,-i)] > 0:
                D.append((C[(i,j)],C[(j,-i)]))

r = 0  #仲が悪くなり得るイワシの数
for i,j in D:
    r += i+j

a = 1  #仲が悪くなり得るイワシたちの選び方
for i,j in D:
    a = (a*(pow(2,i,mod)+pow(2,j,mod)-1)) % mod

a = (a*pow(2,len(A)-r,mod)) % mod  #仲が悪くなり得ないイワシたちの選び方

ans += a-1  #全部選ばないものを除く

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if a != 0 and a * b >= 0:
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)

Submission status: Accepted

Solution code:

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)


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=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:
def main():
  from math import gcd
  from collections import defaultdict
  import sys
  input = sys.stdin.readline
  N = int(input())
  AB = [list(map(int,input().split())) for _ in range(N)]

  MOD = 10**9 + 7

  zero_zero_count = 0
  zero_one_count = 0
  one_zero_count = 0
  dd_ba = defaultdict(int, {})
  for a,b in AB:
    if (a==0)and(b==0):
      zero_zero_count += 1
    elif (a==0):
      zero_one_count += 1
    elif (b==0):
      one_zero_count += 1
    else:
      if a * b < 0:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(b//g, a//g)] += 1
      else:
        a = abs(a)
        b = abs(b)
        g = gcd(a, b)
        dd_ba[(-b//g, a//g)] += 1

  ans = (2**zero_one_count + 2**one_zero_count -1)
  dd_flag = defaultdict(bool, {})

  for key,value in tuple(dd_ba.items()):
    if dd_flag[key]:
      continue
    
    key_0 = key[0]
    key_1 = key[1]
    if key_0<0:
      x = (key_1, -key_0)
    else:
      x = (-key_1, key_0)
    y = dd_ba[x]
    ans *= (2**y + 2**value - 1) % MOD
    ans %= MOD
    dd_flag[x] = True

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

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
from fractions import Fraction
import math

n = int(input())


ab = []
ba = []

a0 = 0
b0 = 0
ab0 = 0


def irr(a, b):
    gcd = math.gcd(a, b)
    a = a // gcd
    b = b // gcd

    if b < 0:
        return (-a, -b)
    else:
        return (a, b)


for i in range(n):
    a, b = map(int, input().split())
    if a != 0 and b != 0:
        ab.append(irr(a, b))
        ba.append(irr(-b, a))
    elif a == 0 and b == 0:
        ab0 += 1
    elif a == 0 and b != 0:
        a0 += 1
    elif a != 0 and b == 0:
        b0 += 1


d_ab = dict()
d_ba = dict()

# d_done = dict()

for i in range(len(ab)):
    cur = ab[i]
    if cur in d_ab:
        d_ab[cur] += 1
    else:
        d_ab[cur] = 1

    cur = ba[i]
    if cur in d_ba:
        d_ba[cur] += 1
    else:
        d_ba[cur] = 1

mod = 1000000007
ans = 1

d_done = set()

for k, v in d_ab.items():
    x = v
    if k in d_ba:
        if k in d_done:
            continue
        else:
            y = d_ba[k]
            kake = 0
            kake += ((2**x) % mod + (2**y) % mod - 1)
            ans *= kake
            ans %= mod
            # d_done[Fraction(-k.denominator, k.numerator)] = 1
            d_done.add(irr(-k[1], k[0]))
    else:
        kake = (2**x) % mod
        ans *= kake
        ans %= mod

ans *= ((2**a0) % mod+(2**b0) % mod-1)
ans %= mod

ans -= 1

ans += ab0
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    # a/bでbが0にならないように、かつ両方正の整数となるまで(a,b)->(-b,a)に変換
    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

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

d = {}
for a, b in X:
    if a == b == 0:
        pass
    elif a == 0:
        if b > 0:
            b = 1
        else:
            b = -1
    elif b == 0:
        if a > 0:
            a = 1
        else:
            a = -1
    else:
        v = gcd(a, b)
        a //= v
        b //= v

    if (a > 0 and b >= 0) or (a < 0 and b <= 0):
        pair = (abs(a), abs(b))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][0] += 1
    else:
        pair = (abs(b), abs(a))
        if pair not in d:
            d[pair] = [0, 0]
        d[pair][1] += 1

mod = 10 ** 9 + 7
zero = 0
ans = 1
for p in d:
    if p == (0, 0):
        zero = d[p][1]
    else:
        a, b = d[p]
        ans *= pow(2, a, mod) + pow(2, b, mod) - 1
        ans %= mod
        
print((ans + zero - 1) % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def main():
    MOD = 1000000007
    N = int(input())
    # Ai * Aj + Bi * Bj = 0
    # -> Ai * Aj = -Bi * Bj
    # -> (Ai/Bi) = -(Aj/Bj)
    # のとき、そのイワシ同士は入れられない

    # そこで、 Ci = Ai/Bi を約分したもの（かつBi>0としておく）
    # を覚えておき、Ci = -Cj となるようなペア同士を数えていく

    C = defaultdict(int)
    n00 = 0
    for i in range(N):
        a, b = map(int, input().split())
        # (0, 0) はどのイワシとも仲が悪いので、考慮の対象から外して置き、
        # 後で(0, 0)のイワシの本数分足す
        if a == 0 and b == 0:
            n00 += 1
            continue

        # Bが0の場合、Aが0のイワシであればなんでも仲が悪くなるので、
        # C = -1 / 0 で統一する。
        if b == 0:
            C[(-1, 0)] += 1
            continue
        # Aが0の場合、Bが0のイワシであればなんでも仲が悪くなるので、
        # C = 0 / 1 で統一する。
        elif a == 0:
            C[(0, 1)] += 1
            continue
        _gcd = gcd(a, b)
        a = a // _gcd
        b = b // _gcd
        # bは常に0以上にする
        if b < 0:
            b = -b
            a = -a
        C[(a, b)] += 1
    
    C = dict(C)
    flag = {k: False for k in C.keys()}

    groups = []
    for c, nc in C.items():
        a, b = c
        # 仲の悪いイワシの個数
        bad_a, bad_b = -b, a
        if bad_b < 0:
            bad_b = -bad_b
            bad_a = -bad_a
        nBad = C.get((bad_a, bad_b), 0)
        # 仲の悪いイワシがいなければ、
        # この中からイワシを選ぶ時のすべての組み合わせ（全て選択しない場合を含む）の数を考える
        if nBad == 0:
            groups.append(2 ** nc)
            continue
        # 中の悪いグループがすでに調査済みなら何もしない
        elif flag[(bad_a, bad_b)]:
            continue

        # あるCのイワシがnc本、それと中の悪いイワシがnBad本あるとする。
        # nc + nBad 本のイワシのうち、OKな組み合わせの個数は
        # [nc本から1本以上選ぶ組み合わせ] + [nc本から1本以上選ぶ組み合わせ] + [イワシを全て選択しない場合]
        # (2^nc - 1) + (2^nBad - 1) + 1 = 2^nc + 2^nBad - 1
        groups.append((2 ** nc) + (2 ** nBad) - 1)
        flag[(a, b)] = True

    # 各グループの選択肢を掛け合わせ、-1する
    # (全て選択しないパターンを除外する)
    ans = 1
    for g in groups:
        ans = (ans * g) % MOD
    # -1 するついでに(0, 0) のイワシから1本以上選ぶ場合の数も足しておく
    ans = (ans + n00 - 1) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    a=fish[i][0]
    b=fish[i][1]
    g=ggcd(a,b)
    if g!=0:
        a=a//g
        b=b//g
    if b<0:
        a=-a
        b=-b
    if (a!=0)or(b!=0):
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
        fishcomp.append([a, b])
    else:
        both0=both0+1
#print(d)
#print(fishcomp)
fishcomp=list(map(list,set(map(tuple,fishcomp))))
#print(fishcomp)
length=N-both0
sets=[]
for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    #print(a,b,val1)
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]
            sets.append([val1,val2])
            length=length-(val2+val1)
#print(sets,length)
pro=1
for i in sets:
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p
#print(pro)
print((pow(2,length,p)*pro-1+both0)%p)

Submission status: Accepted

Solution code:
import math
n = int(input())
mod = 10**9 + 7
cou = 0
pdic = {}
kan = []
betu = [0,0,0]

for i in range(n):
    a , b = map(int,input().split())
    if a*b != 0:
        g = math.gcd(abs(a),abs(b))
        if a*b > 0:
            m = 1
        elif a*b < 0:
            m = -1
        p = (m*abs(a)//g,abs(b)//g)
        q = ((-m)*abs(b)//g,abs(a)//g)
        if pdic.get(q,-1) != -1:
            kan[pdic[q]][1] += 1
        elif pdic.get(p,-1) == -1:
            pdic[p] = cou
            kan.append([1,0])
            cou += 1
        elif pdic.get(p,-1) != -1:
            kan[pdic[p]][0] += 1
    elif a*b == 0:
        if a == 0 and b == 0:
            betu[2] += 1
        elif a == 0:
            betu[0] += 1
        elif b == 0:
            betu[1] += 1
        
        
ans = 1
for i in range(len(kan)):
    ans *= (pow(2,kan[i][0],mod) + pow(2,kan[i][1],mod) - 1) % mod
    ans %= mod
ans *= (pow(2,betu[0],mod) + pow(2,betu[1],mod) - 1) % mod
print((ans-1+betu[2])%mod)

Submission status: Accepted

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=10**9+7
p=137053438808121949
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,p-2,p)%p)
  elif a*b<0:
    AA.append(a*pow((-b),p-2,p)%p)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    flip = 0
    while not (a >= 0 and b > 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    #イメージ的にはa/bを格納していく感じ
    #ai/bi==-bj/ajならダメ
    a=fish[i][0]
    b=fish[i][1]
    g=ggcd(abs(a),abs(b))
    if g!=0:        #ggcdの定義よりa=b=0なら0になりそう(a=0,b!=0ならb,逆もしかり)
        a=a//g
        b=b//g
    #ここらへんで、a,bをそのgcdで割ることによる正規化が完了しているはず
    if b<0:
        a=-a
        b=-b
    #b<0の時に強制的にbを正の値に変換しても影響はない(これを噛ませると後々嬉しい)
    if (a!=0)or(b!=0):
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
        fishcomp.append([a, b])
    else:
        both0=both0+1
#print(d)
#print(fishcomp)
fishcomp=list(map(list,set(map(tuple,fishcomp))))   #二次元配列のset(地味にreferenceがないやつ)
#print(fishcomp)
length=N-both0
sets=[]
#以下ではai/bi==-bj/ajの組みを探している。d[a][b]の個数とd[-b][a]の個数のみ探せば良い
#実はbを正に固定したのがここで生きる。[a b]→[-b a][b,-a]と2つ候補が出るが、
#a>0なら[-b a]に、a<0なら[b,-a]の一つになり、a=0なら[±b 0]だが、これは上で一括して1にまとめているため無問題
#同時にd[a][b]と合わせてダメなのはd[b][-a],d[-b][a]であるが、一方のみ取れば大丈夫
for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    #print(a,b,val1)
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]
            sets.append([val1,val2])
            length=length-(val2+val1)
#print(sets,length)
pro=1
for i in sets:
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p
#print(pro)
print((pow(2,length,p)*pro-1+both0)%p)

Submission status: Accepted

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

def main():
    N = int(input())
    MOD = 1000000007
    d = {}
    
    pd = [1]
    for _ in range(N):
        pd.append((pd[-1]*2)%MOD)

    zero = 0
    ab = [0,0]
    for i in range(N):
        a,b = map(int,input().split())
        if a == b == 0:
            zero += 1
        elif a*b == 0:
            if a == 0:
                ab[0] += 1
            else:
                ab[1] += 1
        else:
            gcd = math.gcd(abs(a),abs(b))
            a //= gcd
            b //= gcd
            if a < 0 and b < 0:
                a *= -1
                b *= -1
            elif a < 0 and b > 0:
                a,b = b,a
            elif a > 0 and b < 0:
                a *= -1
                b *= -1
                a,b = b,a
            if (a,b) not in d:
                d[(a,b)] = 1
            else:
                d[(a,b)] += 1

    ans = 1
    use = {}
    
    for k,v in d.items():
        a,b = k
        if (a,-b) in d:
            if (a,-b) in use:
                continue
            ret = pd[d[(a,b)]]+pd[d[(a,-b)]]-1
            ans *= ret
            use[(a,b)] = 1
            use[(a,-b)] = 1
        else:
            ret = pd[d[(a,b)]]
            ans *= ret
            use[(a,b)] = 1
        ans %= MOD

    ret = pd[ab[0]]+pd[ab[1]]-1
    ans *= ret
    ans += zero
    
    print((ans-1)%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    flip = 0
    while not (a > 0 and b >= 0):
        a, b = -b, a
        flip ^= 1

    g = gcd(a, b)
    a //= g
    b //= g
    if not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    else:
        g = gcd(a, b)
        if (a > 0) ^ (b > 0):
            d_plus[(abs(a // g), abs(b // g))] += 1
        else:
            d_minus[(abs(a // g), -abs(b // g))] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        a, b = -p[1], p[0]
        if a < 0:
            a, b = -a, -b
        return a, b


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)

Submission status: Accepted

Solution code:
import collections
import math

n = int(input())
m = 0
mod = 10 ** 9 + 7
c = []
d = []
frac = []

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        n -= 1
        m += 1
        continue
    if a == 0:
        frac.append('0/1')
    elif b == 0:
        frac.append(('1/0'))
    else:
        gcd = abs(math.gcd(a, b))
        sign = 1 if a * b > 0 else -1
        a = sign * abs(a) // gcd
        b = abs(b) // gcd
        frac.append('{}/{}'.format(a, b))

frac = collections.Counter(frac)

def inverse(key):
    if key == '0/1':
        return '1/0'
    elif key == '1/0':
        return '0/1'
    elif key[0] != '-':
        a, b = key.split('/')
        return '-{}/{}'.format(b, a)
    else:
        a, b = key[1:].split('/')
        return '{}/{}'.format(b, a)

for key, value in frac.items():
    if key[0] == '-' or key[0] == '0': continue
    if frac[inverse(key)] > 0:
        c.append(value)
        d.append(frac[inverse(key)])

ans = pow(2, n - sum(c) - sum(d), mod)
for i, j in zip(c, d):
    tmp = (pow(2, i, mod) + pow(2, j, mod) - 1) % mod
    ans = ans * tmp % mod
ans = (ans - 1 + m) % mod

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import Counter as cc
    from fractions import gcd
    n = int(input())
    mod = 10**9 + 7
    C_p,C_n = cc(),cc()
    count= 0
    count_zero_a = count_zero_b = 0
    ans = 1
    for i in range(n):
        a,b = map(int, input().split())
        if a == 0 and b== 0:
            count += 1
        else:
            gcd_ab = gcd(a,b)
            a //= gcd_ab
            b //= gcd_ab
            if b == 0:
                count_zero_b += 1
            elif a == 0: 
                count_zero_a += 1
            else:
                if a/b>0:
                    C_p[a,b] += 1
                else:
                    C_n[a,b] += 1
    count_zero = count
    ans *= (2**count_zero_a + 2**count_zero_b -1)%mod
    count += count_zero_a + count_zero_b    
    for a,b in C_p:
        if (-b,a) in C_n:
            count += C_n[-b,a] + C_p[a,b]
            ans *= (2**C_n[-b,a] + 2**C_p[a,b] -1)%mod
    ans *= pow(2,n-count,mod)%mod
    ans = (ans +count_zero -1) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

N, = map(int, input().split())
d = dict()
X = []
cc = 0
for _ in range(N):
    a, b = map(int, input().split())
    if a == 0 and b==0:
        cc += 1
        continue
    f = to_standard_form(a, b)
    if f not in d:
        d[f] = 0
    d[f] += 1
    X.append(f)

vs = dict()
for a, b in X:
    f1 = (a, b)
    f2 = to_standard_form(-b, a)
    if f2 not in d:
        d[f2] = 0
    if f1 in vs or f2 in vs:
        continue
    vs[f1] = (d[f1], d[f2])

mod = 10**9+7
r = 1
for k in vs:
    a, b = vs[k]
    r = r * (pow(2, a, mod) + pow(2, b, mod)-1) % mod
print((r-1+cc)%mod)

Submission status: Accepted

Solution code:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
X=[]
mod=277078100995604201
for i in range(n):
  a,b=map(int,input().split())
  if a<0:
    a=a*-1
    b=b*-1
  if a*b>0:
    A.append(b*pow(a,mod-2,mod)%mod)
  elif a*b<0:
    AA.append(a*pow((-b),mod-2,mod)%mod)
  else:
    if a==0 and b==0:
      X.append(i)
    elif a==0:
      B.append(i)
    else:
      C.append(i)
mod = 10**9+7
D=collections.Counter(A)
DD=collections.Counter(AA)
E=set(list(D)+list(DD))
a=1
for i in E:
  a=(a*(2**D[i]+2**DD[i]-1))%mod
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print((a+len(X))%mod)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N, *AB = map(int, stdin.buffer.read().split())

d = defaultdict(int)
zeros = 0
for a, b in zip(*[iter(AB)] * 2):
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        if a == 0 and b == -1:
            b = 1
        d[(a, b)] += 1

ans = 1
free = 0
for (a, b), n in d.items():
    if b > 0:
        if (b, -a) in d:
            m = d[(b, -a)]
            ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            free += n
    else:
        if (-b, a) not in d:
            free += n

ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from math import gcd
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
d = Counter()
a = [tuple(map(int, input().split())) for _ in range(N)]
z = 0
for x, y in a:
  if (x, y) == (0, 0):
    z += 1
    continue
  if y < 0:
    x *= -1
    y *= -1
  if x == 0:
    x = 0
    y = 1
  elif y == 0:
    x = 1
    y = 0
  g = gcd(x, y)
  x //= g
  y //= g
  d[(x, y)] += 1

res = 1
itr = list(d.keys())
#print(itr, d)
for x, y in itr:
  t = 0
  if x <= 0 and (d[(y, -x)] > 0): continue
  if (x, y) == (1, 0):
    t = d[(0, 1)]
  else:
    t = d[(-y, x)]
  v = 0
  v += pow(2, d[(x, y)], mod) - 1
  v %= mod
  v += pow(2, t, mod) - 1
  v %= mod
  v += 1
  v %= mod
  res *= v
  res %= mod
  #print(res, d, d[(x, y)], t)
#print(itr, u, res, z)
print((res - 1 + z) % mod)

Submission status: Accepted

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
def ggcd(a,b):
    if(b==0):
        return a
    return ggcd(b,a%b)
import math
import fractions
import collections
import itertools
import pprint
N=int(input())
l1=[]
adivb=[]
bis0=0
bdiva=[]
ais0=0
both0=0
p=10**9+7
fish=[list(map(int,input().split())) for _ in range(N)]
fishcomp=[]
d={}
for i in range(N):
    a=fish[i][0]
    b=fish[i][1]
    g=ggcd(abs(a),abs(b))
    if g!=0:
        a=a//g
        b=b//g
    if (b==0)and(a>0):
        a=1
    elif b<0:
        a=-a
        b=-b
    if (a!=0)or(b!=0):
        if d.get(a)==None:
            d[a]={}
            d[a][b]=1
        else:
            if d[a].get(b)==None:
                d[a][b]=1
            else:
                val=d[a].get(b)
                d[a][b]=val+1
        fishcomp.append([a, b])
    else:
        both0=both0+1
#print(d)
#print(fishcomp)
fishcomp=list(map(list,set(map(tuple,fishcomp))))
#print(fishcomp)
length=N-both0
sets=[]
for i in fishcomp:
    a=i[0]
    b=i[1]
    val1=d[a][b]
    #print(a,b,val1)
    if d.get(-b)!=None:
        if d[-b].get(a)!=None:
            val2=d[-b][a]
            sets.append([val1,val2])
            length=length-(val2+val1)
#print(sets,length)
pro=1
for i in sets:
    pro=(pro*(pow(2,i[0],p)+pow(2,i[1],p)-1))%p
#print(pro)
print((pow(2,length,p)*pro-1+both0)%p)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())

d = defaultdict(int)
zeros = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        if a == 0 and b == -1:
            b = 1
        d[(a, b)] += 1

ans = 1
free = 0
for (a, b), n in d.items():
    if b > 0:
        if (b, -a) in d:
            m = d[(b, -a)]
            ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            free += n
    else:
        if (-b, a) not in d:
            free += n

ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict
from math import gcd

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N, *AB = map(int, stdin.buffer.read().split())
it = iter(AB)

d = defaultdict(int)
zeros = 0
for a, b in zip(it, it):
    if a == 0 and b == 0:
        zeros += 1
    else:
        g = gcd(a, b)
        a //= g
        b //= g
        if a < 0:
            a *= -1
            b *= -1
        if a == 0 and b == -1:
            b = 1
        d[(a, b)] += 1

ans = 1
free = 0
for (a, b), n in d.items():
    if b > 0:
        if (b, -a) in d:
            m = d[(b, -a)]
            ans = ans * (pow(2, n, MOD) + pow(2, m, MOD) - 1) % MOD
        else:
            free += n
    else:
        if (-b, a) not in d:
            free += n

ans = (ans * pow(2, free, MOD) + zeros - 1) % MOD
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

MOD = 10**9+7
N = int(input())
d = {}
zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue

    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 not (a, b) in d:
        d[(a, b)] = [0, 0]
    d[(a, b)][flip] += 1

ans = 1
for (v1, v2) in d.values():
    ans *= pow(2, v1, MOD) + pow(2, v2, MOD)-1
    ans %= MOD
ans -= 1
ans += zero
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

t = []
d = {}
d[0] = {}
d[0][0] = 0
for a, b in AB:
    i = gcd(a, b)
    if i != 0:
        a //= i
        b //= i
    t.append((a, b))
    d.setdefault(a, {})
    d[a].setdefault(b, 0)
    d[a][b] += 1

used = set()
result = 1
for a, b in t:
    if (a, b) in used:
        continue
    used.add((a, b))
    if a == 0 and b == 0:
        continue
    i = d[a][b]
    j, k, l = 0, 0, 0
    if -a in d and -b in d[-a]:
        j = d[-a][-b]
        used.add((-a, -b))
    if -b in d and a in d[-b]:
        k = d[-b][a]
        used.add((-b, a))
    if b in d and -a in d[b]:
        l = d[b][-a]
        used.add((b, -a))
    result *= pow(2, i + j, 1000000007) + pow(2, k + l, 1000000007) - 1
    result %= 1000000007
result += d[0][0] - 1
result %= 1000000007
print(result)