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)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log,gcd #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))



def main():
    N=I()
    A,B=[],[]
    for i in range(N):
        a,b = MI()
        A.append(a)
        B.append(b)
    both_zero_cnt = 0
    num_of_group = defaultdict(int) ##既約分数にしてあげて、(分子,分母)がkeyで、負なら分子が負になる他は正
    for i in range(N):
        a,b = A[i], B[i]
        if(a==b==0):
            both_zero_cnt+=1
            continue
        elif(a==0):
            num_of_group[-inf,inf] += 1
            num_of_group[inf,inf] += 0

        elif(b==0):
            num_of_group[inf,inf] += 1
        else:
            if(a*b<0):
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(-b,a)] += 1
                num_of_group[(b,a)] += 0
            else:
                a,b=abs(a),abs(b)
                g = gcd(a,b)
                a//=g
                b//=g
                num_of_group[(a,b)] += 1
    # print(num_of_group.items())
    if(both_zero_cnt==N):
        print(N)
        return
    ##solve
    ans = ModInt(1)
    two_pow = [1]
    for i in range(N):
        two_pow.append((2*two_pow[-1])%mod)
    # print(two_pow,"#######")
    for (a,b),cnt1 in num_of_group.items():
        if(a<0):
            continue
        tmp = two_pow[cnt1]
        # print((a,b),cnt1)
        # print(tmp)

        if (-a,b) in num_of_group:
            cnt2 = num_of_group[-a,b]
            tmp += two_pow[cnt2]
            tmp-=1
        if(tmp):
            ans *= tmp
    ans -= 1 ##全部選ばない
    ans += both_zero_cnt
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    d = defaultdict(int)
    d2 = defaultdict(int)
    d3 = defaultdict(int)
    aa = 0
    for a, b in ab:
        if a == b == 0:
            aa += 1
            continue
        if a == 0:
            d[0] += 1
            d3[0] = 1
        elif b == 0:
            d2[0] += 1
            d3[0] = 1
        else:
            if a * b > 0:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d[(abs(a) , abs(b))] += 1
                d3[(abs(a) , abs(b))] = 1
            else:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d2[(abs(b), abs(a))] += 1
                d3[(abs(b), abs(a))] = 1
    ans = 1
    for k in d3.keys():
        ans *= (2 ** d[k] + 2 ** d2[k] - 1)
        ans %= mod
    ans -= 1
    ans += aa
    print(ans % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math,sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
MOD = 1000000007
d = defaultdict(int)
l,r = 0,0
count = 0
for i in range(n):
  a,b = map(int,input().split())
  if a == b == 0:
    count += 1
    continue
  elif a == 0 or b == 0:
    if a == 0:
      l += 1
    else:
      r += 1
  else:
    g = math.gcd(a,b)
    a,b = a//g,b//g
    if a<0:
      a,b = -a,-b
    d[str(a)+':'+str(b)] += 1
c = 1
for i in d.keys():
  if d[i] != 0:
    cur = pow(2,d[i],MOD)
    if '-' in i:
      ind = i.index(':')
      ci = i[ind+2:] + ':' + i[:ind]
    else:
      ind = i.index(':')
      ci = i[ind+1:] + ':-' + i[:ind]
    if ci in d.keys():
      cur += pow(2,d[ci],MOD)-1
      d[ci] = 0
    c = (c*cur)%MOD
c = (c*(pow(2,l,MOD)+pow(2,r,MOD)-1)-1+count)%MOD
print(c)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict
from math import gcd

n = int(readline())
data = list(map(int,read().split()))
mod = 1000000007

it = iter(data)
a_b = defaultdict(lambda :[0,0])
a0 = 0
b0 = 0
ab0 = 0
ans = 0
for a,b in zip(it,it):
    if(a==b==0):
        ab0 += 1
        continue
    if(a*b==0):
        if(a==0):
            a0 += 1
        if(b==0):
            b0 += 1
    else:
        if(a/b > 0):
            a = abs(a)
            b = abs(b)
            gcd_num = gcd(a,b)
            a_b[(a//gcd_num,b//gcd_num)][0] += 1
        else:
            a = abs(a)
            b = abs(b)
            gcd_num = gcd(a,b)
            a_b[(b//gcd_num,a//gcd_num)][1] += 1

exp2 = [1] * (n+1)
for i in range(n):
    exp2[i+1] = exp2[i] * 2
    exp2[i+1] %= mod


ans += (ans+1) * ( exp2[a0]-1  + exp2[b0]-1)
ans %= mod

for key,val in a_b.items():
    ans += (ans+1) * ( exp2[val[0]]-1  + exp2[val[1]]-1)
    ans %= mod

ans += ab0
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from math import gcd, atan2

MOD = 10**9 + 7
class mint:
    def __init__(self, i):
        self.i = i
    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)
    def __mul__(self, m):
        return mint(self.i * (m.i if isinstance(m, mint) else m) % MOD)
    def __sub__(self, m):
        t = self.i - (m.i if isinstance(m, mint) else (m % MOD))
        if t < 0:
            t += MOD
        return mint(t)
    def __pow__(self, m):
        i = self.i
        return mint(pow(i, m, MOD))
    def __truediv__(self, m):
        return mint(self.i * pow(m, MOD - 2, MOD) % MOD)
    def __repr__(self):
        return repr(self.i)


n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
zeros = len(list(filter(lambda x: x[0] == x[1] == 0, ab)))
ab = list(filter(lambda x: x[0] ** 2 + x[1] ** 2 > 0, ab))

t = []
for a, b in ab:
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        a *= -1
        b *= -1
    elif a == 0:
        b = abs(b)
    t.append((a, b)) # a >= 0
m = Counter()
for a, b in t:
    m[(a, b)] += 1
l = []
for a, b in m:
    if b > 0 and ((b, -a) in m):
        continue
    l.append((m[(a, b)], m[(-b, a)]))
ans = mint(1)

for v, w in l:
    #print('hi', ans, v, w)
    ans *= pow(2, v, MOD) - 1 + pow(2, w, MOD) - 1 + 1
#print(ans)
print(ans + zeros - 1)

Submission status: Accepted

Solution code:
mod = 10**9+7
n = int(input())
inf = 10**20
fish = {}
rish = {}
att = 0
raw = []
raz = []
def lon(a,b,p):
  return p*10**40 + a*10**20 + b
def rev(z):
  p,a,b = z//(10**40),(z//(10**20))%(10**20),z%(10**20)
  return lon(b,a,1-p)
for _ in range(n):
  a,b = map(int,input().split())
  r = 1
  if a*b == 0:
    if a == b == 0:
      att += 1
    elif a == 0:
      raw.append(lon(0,1,1))
      raz.append(lon(1,0,0))
      fish[lon(0,1,1)] = [0,0]
      fish[lon(1,0,0)] = [0,0]
    else:
      raw.append(lon(1,0,0))
      raz.append(lon(0,1,1))
      fish[lon(1,0,0)] = [0,0]
      fish[lon(0,1,1)] = [0,0]
    continue
  if a*b < 0:
    r = 0
  a = abs(a)
  b = abs(b)
  big = int(a)
  sml = int(b)
  while sml != 0:
    big,sml = sml,big%sml
  a //= big
  b //= big
  raw.append(lon(a,b,r))
  raz.append(lon(b,a,1-r))
  fish[lon(a,b,r)] = [0,0]
  fish[lon(b,a,1-r)] = [0,0]
for x in raw:
  fish[x][0] += 1
for x in raz:
  fish[x][1] += 1
double = [1]
for _ in range(3*10**5):
  double.append(double[-1]*2%mod)
ans = 1
#print(fish)
for x in fish:
  re = rev(x)
  #print(x,fish[x][0],fish[x][1])
  #print(re)
  ans *= double[fish[x][0]] + double[fish[x][1]] - 1
  ans %= mod
  fish[x] = [0,0]
  fish[re] = [0,0]
ans -= 1
ans += att
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from math import gcd
mod = 10**9+7
n = int(input())
dic = defaultdict(lambda:[[0,0],[0,0]])
zero = [0,0]
zerozero = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            zerozero += 1
            continue
        else:
            if a == 0:
                zero[0] += 1
            else:
                zero[1] += 1
        continue
    minus = False
    rev = False
    if a * b < 0:
        minus = True
    a,b = abs(a),abs(b)
    g = gcd(a,b)
    a,b = a//g,b//g
    if a > b:
        a,b = b,a
        rev = True
    if minus:
        if rev:
            dic[(a,b)][0][1] += 1
        else:
            dic[(a,b)][0][0] += 1
    else:
        if rev:
            dic[(a,b)][1][1] += 1
        else:
            dic[(a,b)][1][0] += 1
ans = 1
for y in dic.keys():
    x = dic[y]
    if y == (1,1):
        ans *= 2**sum(x[0])+2**sum(x[1])-1
    else:
        ans *= 2**x[0][1]+2**x[1][0]-1
        ans *= 2**x[0][0]+2**x[1][1]-1
        ans %= mod
ans *= 2**zero[0]+2**zero[1]-1
ans += zerozero
ans %= mod
ans += 10**9+6
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import math

MOD = 1000000007

def revKey(v):
    if v == (1,0):
        return (0,1)

    if v[1] < 0:
        return (-v[1], v[0])
        
    return (v[1], -v[0])


N = int(input())

POW2 = [0]*(N+1)
p = 1
for i in range(N+1):
    POW2[i] = p
    p = p*2%MOD


V = {}
for _ in range(N):
    A,B = map(int, input().split())

    v = None
    if A == 0:
        if B == 0:
            v = (0,0)
        else:
            v = (0, 1)
    elif B == 0:
        v = (1, 0)

    else:
        if A < 0:
            A,B = -A,-B

        g = math.gcd(A,B)
        A //= g
        B //= g

        v = (A,B)

    if not(v in V):
        V[v] = 0

    V[v] += 1


ans = 1
for v in V:
    if v == (0,0):
        continue

    n = V[v]
    if n == None:
        continue

    n2 = 0
    revV = revKey(v)
    if revV in V:
        n2 = V[revV]
        V[revV] = None
        ans = ans * (POW2[n] + POW2[n2] - 1) % MOD
    else:
        ans = ans * POW2[n] % MOD

if (0,0) in V:
    ans += V[(0,0)]

ans -= 1
print(ans % MOD)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

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

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

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

mod = 1000000007
cnt = 1
for pair in d.values():
    cnt *= pow(2, pair[0], mod) + pow(2, pair[1], mod) - 1
    cnt %= mod
cnt += zeros - 1
cnt %= mod
print(cnt)

Submission status: Accepted

Solution code:
import math
MOD = 1000000007
N = int(input())
A = []
d = {}
for i in range(N):
	a,b = map(int,input().split())
	g = math.gcd(a,b)
	if a < 0:
		a *= -1
		b *= -1
	if a == 0 and b < 0:
		b *= -1
	if g != 0:
		a = a // g
		b = b // g
	if (a,b) in d:
		d[(a,b)] += 1
	else:
		d[(a,b)] = 1

ans_sp = 0
if (0,0) in d:
	ans_sp += d[(0,0)]

def pow(n, k):
	ret = 1
	while k > 0:
		if k % 2 == 1:
			ret = ret * n % MOD
		n = n * n % MOD
		k = k // 2
	return ret

ans = 1
for k in d:
	a,b = k[0], k[1]
	if a == 0 and b == 0:
		continue
	v = d[k]
	x,y = b,-a
	if x < 0:
		x *= -1
		y *= -1
	if x == 0 and y < 0:
		y *= -1
	if y == 0 and x < 0:
		x *= -1
	if (x,y) in d:
		if  b > y:
			continue
		tmp = (pow(2,v) + pow(2,d[(x,y)]) - 1) % MOD
		ans = (ans * tmp) % MOD
	else:
		ans = (ans * pow(2,v)) % MOD
print((ans_sp + ans - 1) % MOD)

Submission status: Accepted

Solution code:
import math
from collections import Counter
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __row__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))#2進表現に
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res

    def combination(self,n,r=-1):
        if r==-1:
            r = n
        #nCrの一覧を返す。rの上限も
        if (r<0) or (n<r):
            return 0
        cur = ModInt(1)
        res = []
        res.append(cur)
        for i in range(1,r+1):
            cur *= n + 1 -i
            cur /= i
            res.append(cur)
        return res



#グローバル変数MODを決めてあげてください
MOD = 1000000007

N = int(input())
#双方ノンゼロ...
#Ai*Aj = - Bi* Bj　⇔　Ai/Bi == -Bj/Ai
#絶対値が同じやつら
#片方ゼロ→ノンゼロとは食い合わないがもう片方がゼロならダメ
#両方ゼロ→単騎で選ぶしかない
#ノンゼロ組、片方ゼロ組、両方ゼロ組に分ける
#ノンゼロ*(1 + Aだけゼロ + Bだけゼロ) + 両方ゼロ単騎
#1,1組→ 
NonZeroPlus = []
NonZeroMinus = []
a = ModInt(2)
AZero = 0
BZero = 0
TwoZero = 0
TwoOne = 0
for n in range(N):
    A,B = [int(hoge) for hoge in input().split()]
    if A!=0 and B!=0:
        G = math.gcd(abs(A),abs(B))
        if B < 0:
            G *= -1
            #B//Gが必ず正
        if A//G > 0:
            NonZeroPlus.append((A//G,B//G))
        else:#A//B < 0
            NonZeroMinus.append((B//G,-A//G))
    elif A==B==0:
        TwoZero += 1
    elif A == 0:
        AZero += 1
    else:
        BZero += 1
P = Counter(NonZeroPlus)
M = Counter(NonZeroMinus)
NonZero = ModInt(1)
Daburazu = ModInt(0)
for k in P.keys():
    X,Y = P[k],M[k]
    if Y:
        NonZero *= (a**X -1) + (a**Y -1) + 1 
    else:
        Daburazu += X
for k in M.keys():
    X,Y = P[k],M[k]
    if X == 0:
        Daburazu += Y
#ノンゼロ組…コレ(0含む)
NonZero *= a**Daburazu
NonZero *= (a**AZero -1) + (a**BZero -1) + 1
NonZero += TwoZero
print(NonZero -1)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

N = Int()
mod = 1000000007
ans = 1
import math

from collections import defaultdict
XX = defaultdict(list)
YY = defaultdict(list)

zeros = 0

for i in range(N):
    A,B = Ints()
    if A!=0 and B!=0:
        GCD = math.gcd(A,B)
        A //=GCD
        B //=GCD
        if A<0 and B<0:
            A *= -1
            B *= -1
        elif A>0 and B<0:
            A *= -1
            B *= -1
        XX[(A,B)].append(i)
        
        B *= -1
        if A<0 and B<0:
            A *= -1
            B *= -1
        elif A<0 and B>0:
            A *= -1
            B *= -1
        YY[(B,A)].append(i)
        
    elif A==0 and B!=0:
        XX[(0,1)].append(i)
        YY[(1,0)].append(i)
    elif A!=0 and B==0:
        XX[(1,0)].append(i)
        YY[(0,1)].append(i)
    else:
        zeros += 1


D = {}

for key in XX:
    if not key in D:
        l = len(XX[key])
        m = len(YY[key])
        ans *= (pow(2,l,mod)+pow(2,m,mod)-1)
        ans %= mod
        D[key] = 1
        
        a,b = key
        if a==0 and b==1:
            D[(1,0)] = 1
        elif a==1 and b==0:
            D[(0,1)] = 1
        else:
            b *= -1
            if a < 0:
                b*=-1
                a*=-1
            D[(b,a)] = 1
    
ans -= 1
ans += zeros
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

def main():
    N = int(input())
    mod = 10**9 + 7
    AB = {}
    pos = set()
    for _ in range(N):
        a, b = map(int, input().split())
        g = gcd(a, b)
        if g == 0:
            AB[(0, 0)] = AB.get((0, 0), 0) + 1
            continue
        a, b = a // g, b // g
        if a * b < 0 and a > 0:
            a, b = -a, -b
        if a * b > 0 and a < 0:
            a, b = -a, -b
        if a * b == 0:
            a, b = abs(a), abs(b)
        if a * b > 0:
            pos.add((a, b))
        AB[(a, b)] = AB.get((a, b), 0) + 1
    t = N - AB.get((0, 0), 0)
    r = 1
    for a, b in pos:
        p = AB[(a, b)]
        n = AB.get((-b, a), 0)
        r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
        r %= mod
        t -= (p + n)
    p = AB.get((0, 1), 0)
    n = AB.get((1, 0), 0)
    r *= (pow(2, p, mod) - 1) + (pow(2, n, mod) - 1) + 1
    t -= (p + n)
    r *= pow(2, t, mod)
    r -= 1

    if (0, 0) in AB:
        r += AB[(0, 0)]

    return r % mod

print(main())

Submission status: Accepted

Solution code:
import math
import collections
def main():

    mod = pow(10, 9) + 7
    N = int(input())
    AB = []
    pos = collections.defaultdict(int)
    neg = collections.defaultdict(int)
    x = 0
    y = 0

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

    point = 0
    for _ in range(N):
        A, B = map(int, input().split())
        if A == 0 and B == 0:
            point += 1
        elif A == 0:
            y += 1
        elif B == 0:
            x += 1
        else:
            g = gcd(abs(A), abs(B))
            A = A // g
            B = B // g
            if A < 0:
                A, B = -A, -B
            if B > 0:
                pos[(A, B)] += 1
            else:
                neg[(A, B)] += 1


    pow2 = [1]
    for _ in range(1, N+1):
        pow2.append((pow2[-1] * 2) % mod)

    # print(pos)
    # print(neg)
    # print(x)
    # print(y)
    # print("----")

    v = 1
    if x > 0 and y > 0:
        v *= (pow2[x] + pow2[y] - 1)
    elif x > 0:
        v *= pow2[x]
    else:
        v *= pow2[y]
    v %= mod

    for z in pos:
        A, B = z
        w = (B, -A)
        if w not in neg:
            v *= pow2[pos[z]]
        else:
            v *= (pow2[pos[z]] + pow2[neg[w]] - 1)
        v %= mod
    # print("here", v)

    for w in neg:
        A, B = w
        z = (-B, A)
        if z not in pos:
            # print('ya', z)
            v *= pow2[neg[w]]
        v %= mod
    # print("there", v)

    return (v - 1 + point) % mod
if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
def p2(x):
  return pow(2,x,mod)
dc = defaultdict(int)
st = set()
from math import gcd
n00 = 0
n0x = 0
nx0 = 0
nxy = 0
ls = []
for i in range(n):
  if a[i][0] == a[i][1] == 0:
    n00 += 1
  elif a[i][0] == 0:
    n0x += 1
  elif a[i][1] == 0:
    nx0 += 1
  else:
    nxy += 1
    if a[i][0] < 0 and a[i][1] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    elif a[i][0] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    ls.append(a[i])
if len(ls) == 0:
  print((p2(n0x)+p2(nx0)-1+n00-1)%mod)
  exit()
def part(x,y):
  g = gcd(x,y)
  return (x//g,y//g)
for i in range(nxy):
  p = part(*ls[i])
  st.add(p)
  dc[p] += 1
banned = []
for i,j in dc:
  if i*j > 0 and (j,-i) in st:
    banned.append((dc[(i,j)],dc[(j,-i)]))
sm = sum([banned[i][0]+banned[i][1] for i in range(len(banned))])
ans = p2(nxy-sm)
for i,j in banned:
  ans = (ans*(p2(i)+p2(j)-1))%mod
k = p2(n0x)+p2(nx0)-1
ans *= k
ans += n00-1
print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
import sys
from collections import defaultdict
input = sys.stdin.readline
N= int(input())
AB = [list(map(int,input().split())) for i in range(N)]

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

ans = 0

PAB = []
for a,b in AB:
    d = gcd(a,b)
    if d == 0:
        PAB.append((0,0))
        continue
    PAB.append((a//d,b//d)) # a//d >= 0
    
dic1 = defaultdict(int)
dic4 = defaultdict(int)

yaxis = 0
xaxis = 0
origin = 0
vs = []
for a,b in PAB:
    if a == 0 and b == 0:
        origin += 1
        continue
    if a == 0:
        yaxis += 1
        continue
    if b == 0:
        xaxis += 1
        continue
    if b > 0:
        dic1[(a,b)] += 1
        vs.append((a,b))
    else:
        dic4[(-b,a)] += 1
        vs.append((-b,a))

vs = list(set(vs))

ans = 1
for v in vs:
    n1 = dic1[v]
    n4 = dic4[v]
    ans *= (pow(2,n1,MOD) + pow(2,n4,MOD) - 1)
    ans %= MOD

ans *= (pow(2,xaxis,MOD)+pow(2,yaxis,MOD)-1)
ans -= 1 # no fish
ans += origin
print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 1000000007
n = int(input())


def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


# GCD(-2, 4)

iwasi_cnt = defaultdict(int)
for _ in range(n):
    a, b = map(int, input().split())
    if b < 0:
        a, b = -a, -b
    # iwasi.append((a, b))

    g = GCD(abs(a), abs(b))
    if g == 0:
        # (0, 0)
        iwasi_cnt[(a, b)] += 1
    else:
        iwasi_cnt[(a // g, b // g)] += 1

iwasi_cnt = dict(iwasi_cnt)
# print(iwasi_cnt)
cand = []
cnt0 = 0
for (a, b), v in iwasi_cnt.items():
    if a == 0 and b == 0:
        cnt0 += v
    else:
        if (-b, a) in iwasi_cnt:
            m = iwasi_cnt[(-b, a)]
            cand.append((v, m))
        elif (b, -a) not in iwasi_cnt:
            cand.append((v, ))

# print(*cand, sep='\n')
ans = 1
for i in range(len(cand)):
    if len(cand[i]) == 1:
        x = cand[i][0]
        ans *= pow(2, x, MOD)
        ans %= MOD
    else:
        x, y = cand[i]
        ans *= (MOD + pow(2, x, MOD) + pow(2, y, MOD) - 1) % MOD
        ans %= MOD

ans -= 1  # 0匹を取り除く
ans %= MOD
ans += cnt0  # (0, 0)を追加
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
INF=10**9+7
D={}
z=0
import math
for i in range(n):
    a,b=map(int,input().split())
    if a==0:
        if b==0:
            z+=1
        else:
            if (0,1) in D:
                D[(0,1)]+=1
            else:
                D[(0,1)]=1
    elif b==0:
        if (1, 0) in D:
            D[(1,0)] += 1
        else:
            D[(1,0)] = 1
    else:
        if b<0:
            b=-b
            a=-a
        if a>0:
            c=math.gcd(a,b)
            a//=c
            b//=c
            if (a,b) in D:
                D[(a,b)] += 1
            else:
                D[(a,b)] = 1
        else:
            a=-a
            c = math.gcd(a, b)
            a //= c
            b //= c
            a=-a
            if (a, b) in D:
                D[(a, b)] += 1
            else:
                D[(a, b)] = 1
ans=1
p=[1]
for i in range(n):
    temp=(p[-1]*2)%INF
    p.append(temp)
for i in D:
    if not D[i]==0:
        x=i[0]
        y=i[1]
        if x>0:
            if (-y,x) in D:
                temp=D[(-y,x)]
                D[(-y,x)]=0
                ans=(ans*(p[D[i]]+p[temp]-1))%INF
            else:
                ans=ans*p[D[i]]%INF
        else:
            if (y,-x) in D:
                temp=D[(y,-x)]
                D[(y,-x)]=0
                ans=(ans*(p[D[i]]+p[temp]-1))%INF
            else:
                ans=ans*p[D[i]]%INF
if z!=0:
    ans=(z+ans-1)%INF
else:
    ans=(ans-1)%INF
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
import math
MOD = 10**9 + 7

n = int(input())
fish = dict() 
azero = 0
bzero = 0
abzero = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        abzero += 1
        continue
    if a == 0:
        azero += 1
        continue
    if b == 0:
        bzero += 1
        continue
    a_abs = abs(a); b_abs = abs(b)
    g = math.gcd(a_abs, b_abs)
    if (a > 0 and b > 0) or (a < 0 and b < 0): 
        key = (a_abs // g, b_abs // g)
    else:
        key = (a_abs // g, -b_abs // g)
    if key not in fish:
        fish[key] = 1
    else:
        fish[key] += 1

ans = 1
for a, b in fish:
    if fish[(a, b)] == 0:
        continue
    if b < 0:
        inv_key = (-b, a)
    else:
        inv_key = (b, -a)
    if inv_key in fish:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        val2 = ans * (pow(2, fish[inv_key], MOD) - 1)
        fish[inv_key] = 0
        ans = val1 + val2 + ans
    else:
        val1 = ans * (pow(2, fish[(a, b)], MOD) - 1)
        ans = val1 + ans
    ans %= MOD
# think a == 0 or b == 0
val1 = ans * (pow(2, azero, MOD) - 1)
val2 = ans * (pow(2, bzero, MOD) - 1)
ans = val1 + val2 + ans
ans += abzero
print((ans - 1) % MOD)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict
P = 7 ** 21 + 52
mod = 10 ** 9 + 7
N = int(input())
D = defaultdict(int)
C00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        C00 += 1
    elif a == 0:
        D[-1] += 1
    elif b == 0:
        D[-2] += 1
    else:
        x = a * pow(b, P - 2, P) % P
        D[x] += 1
ans = 1
for x in D:
    y = pow(-x, P - 2, P) if x > 0 else -3 - x
    if y in D and x > y: continue
    ans *= 1 + pow(2, D[x], mod) - 1 + pow(2, (D[y] if y in D else 0), mod) - 1
    ans %= mod
print((ans + C00 - 1) % mod)