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:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,cos,radians,sqrt
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7



def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n=I()
bekit=[0 for i in range(n+1)]
bekit[0]=1
for i in range(n):
    bekit[i+1]=(bekit[i]*2)%mod
#print(bekit)
countz=0
countx=0
county=0
nump=[]
numm=[]
for i in range(n):
    a,b=MI()
    if a==0 and b==0:
        countz+=1
    elif a==0:
        if b<0:
            b*=(-1)
        countx+=1
    elif b==0:
        if a<0:
            a*=(-1)
        county+=1
    elif (a>0 and b<0) or (a<0 and b>0):
        #print(a,b)
        if b<0:
            a*=(-1)
            b*=(-1)
        g=gcd(abs(a),b)
        a=a//g
        b=b//g
        #print(a,b)
        numm.append([a,b])
    else:
        g=gcd(abs(a),abs(b))
        a//=g
        b//=g
        nump.append([abs(a),abs(b)])
#print(nump)
#print(numm)
nump=list(map(tuple,nump))
numm=list(map(tuple,numm))
u=Counter(nump)
v=Counter(numm)
#print(u)
#print(v)
nums=[]
pairs=[]
for k in u.keys():
    vz=((-1)*k[1],k[0])
    s=u[k]
    t=v[vz]
    #print(vz)
    #print(s)
    #print(t)
    if t>0:
        nums.append([s,t])
        pairs.append(s+t)
#print(nums)
#print(nums)
#print(n-sum(pairs)-countx-county-countz)
#print(pairs)
#print(n-sum(pairs)-countx-county-countz)
if countx>0 and county>0:
    cou=countx+county
else:
    cou=0
ans=bekit[n-sum(pairs)-cou-countz]
#print(ans)
for j in range(len(nums)):
    q=bekit[nums[j][0]]
    p=bekit[nums[j][1]]
    #print(q)
    #print(p)
    ans=(ans*(q+p-1))%mod
if countx>0 and county>0:
    ans=(ans*(bekit[countx]+bekit[county]-1))%mod
ans-=1
if countz>0:
    ans+=countz%mod
print(ans%mod)

Submission status: Accepted

Solution code:
import sys

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    
    n = int(input())
    key1 = dict()
    key2 = dict()
    
    a_0 = 0
    b_0 = 0
    ab_0 = 0
    
    for i 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
        k1, k2 = abs(a), abs(b)
        if k2 < k1:
            k1, k2 = k2, k1
        while k2%k1:
            k2, k1 = k1, k2%k1
        a //= k1
        b //= k1
        if a*b > 0:
            k = (abs(a), abs(b))
            if k in key1:
                key1[k] += 1
            else:
                key1[k] = 1
        else:
            k = (abs(b), abs(a))
            if k in key2:
                key2[k] += 1
            else:
                key2[k] = 1
    
    
    left = n-a_0-b_0-ab_0
    key = [(a_0, b_0)]
    for k, v in key1.items():
        if k in key2:
            v2 = key2[k]
            key.append((v, v2))
            left -= v+v2
    
    ans = pow(2, left, mod)
    for a, b in key:
        ans *= pow(2, a, mod)+pow(2, b, mod)-1
        ans %= mod
    ans += mod-1
    ans += ab_0
    ans %= mod
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def mk(a,b):
	if a == 0:
		return 0,1
	if b==0:
		return 1,0
		
	c = -1 if a < 0 else 1
	r = math.gcd(abs(a),abs(b))
	ra = (a //r)*c
	rb = (b //r)*c
	
	return ra, rb
	
def mh(a,b):
	return str(a)+'_'+str(b)
	
def mv(s):
	a,b = map(int, s.split('_'))
	return a,b
	
def ty(s):
	a, b = mv(s)
	sign = 1 if b > 0 else -1
	return mh(b*sign, -a*sign)
	

def main():
	n = int(input())
	dd = defaultdict(lambda : 0)
	zero_fish_num=0
	for _ in range(n):
		a,b=tin()
		if a== 0 and b == 0:
			zero_fish_num += 1
			continue
		a,b = mk(a,b)
		dd[mh(a,b)] += 1
		
	cc = set()
	ret = 1
	for k in dd:
		if k in cc:
			continue
		v = dd[k]
		if ty(k) in dd:
			tv = dd[ty(k)]
			r = pow(2,v,mod)+pow(2,tv,mod)-1
			#pa((r,k, ty(k)))
			ret *= r
			ret %= mod
			cc.add(ty(k))
		else:
			#pa(('v',v,k, ty(k)))
			ret *= pow(2,v,mod)
			ret %= mod
			
	ret -= 1
	ret += zero_fish_num
	ret %= mod
	print(ret) 
			
		
		
	#b , c = tin()
	#s = input()
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys

# sys.stdout.write(str(n)+"\n")
MODULO = 1000000007
# INF = 1e18+10

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

n = int(input())

a_b = [() for i in range(n)]
m_b_a = [() for i in range(n)]

# a_b_value_indices = {}
# m_b_a_value_indices = {}

a_b_value_count = {}
m_b_a_value_count = {}

a_b_value_rep = {}
m_b_a_value_rep = {}

used = [False for _ in range(n)]
zeroes = 0
is_zero = [False for _ in range(n)]

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

	if a == 0 and b == 0:
		zeroes += 1
		used[i] = True
		is_zero[i] = True
	else:
		if a == 0:
			a_b[i] = (0, 1)
			m_b_a[i] = (1, 0)
		elif b == 0:
			a_b[i] = (1, 0)
			m_b_a[i] = (0, 1)
		else:
			neg = False
			if a*b < 0:
				neg = True
			d = gcd(abs(a), abs(b))
			a = abs(a) // d
			b = abs(b) // d

			if neg:
				a_b[i] = (-a, b)
				m_b_a[i] = (b, a)
			else:
				a_b[i] = (a, b)
				m_b_a[i] = (-b, a)

		a_b_value_count[a_b[i]] = a_b_value_count.get(a_b[i], 0) + 1
		# a_b_value_indices[a_b[i]] = a_b_value_indices.get(a_b[i], []) + [i]
 
		m_b_a_value_count[m_b_a[i]] = m_b_a_value_count.get(m_b_a[i], 0) + 1
		# m_b_a_value_indices[m_b_a[i]] = m_b_a_value_indices.get(m_b_a[i], []) + [i]
		if a_b[i] not in a_b_value_rep:
			a_b_value_rep[a_b[i]] = i
		if m_b_a[i] not in m_b_a_value_rep:
			m_b_a_value_rep[m_b_a[i]] = i

ans = 1
for i in range(n):
	if not is_zero[i] and not used[a_b_value_rep[a_b[i]]]:
		# if not connected
		if a_b[i] not in m_b_a_value_count:
			ans *= pow(2, a_b_value_count[a_b[i]], MODULO)
			ans %= MODULO
			used[a_b_value_rep[a_b[i]]] = True
			# for j in a_b_value_indices[a_b[i]]:
			# 	used[j] = True
		else:
			s = a_b_value_count[a_b[i]]
			t = m_b_a_value_count[a_b[i]]
			ans *= ((1*pow(2, s, MODULO) + 1*pow(2, t, MODULO) -1) % MODULO)
			ans %= MODULO

			used[a_b_value_rep[a_b[i]]] = True
			used[m_b_a_value_rep[a_b[i]]] = True
			# for j in m_b_a_value_indices[a_b[i]]:
			# 	used[j] = True
 
			# used_a_b_keys.add(a_b_key)
			# used_a_b_keys.add(-1/a_b_key)
 
 
# -1 is for empty
print((ans-1+zeroes) % MODULO)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
from math import gcd
N = int(input())
from collections import defaultdict
X = defaultdict(lambda: [0, 0])
x = 0
y = 0
z = 0
for i in range(N):
  a, b = map(int, input().split())
  g = abs(gcd(a, b))
  if a * b > 0:
    X[(abs(a) // g, abs(b) // g)][0] += 1
  elif a * b < 0:
    X[(abs(b) // g, abs(a) // g)][1] += 1
  else:
    if a:
      x += 1
    elif b:
      y += 1
    else:
      z += 1
ans = 1
pow2 = [1]
for i in range(N):
  pow2 += [pow2[-1] * 2 % mod]
for i in X.values():
  ans *= pow2[i[0]] + pow2[i[1]]- 1
  ans %= mod
ans *= pow2[x] + pow2[y] - 1
ans += z - 1
ans %= mod
print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N = int(rl())
    AB = tuple(tuple(map(int, rl().split())) for _ in range(N))
    
    zero_pare = 0
    zero_a, zero_b = 0, 0
    counter = defaultdict(int)
    for a, b in AB:
        if a == b == 0:
            zero_pare += 1
        elif a == 0:
            zero_a += 1
        elif b == 0:
            zero_b += 1
        else:
            cd = gcd(a, b)
            a, b = a // cd, b // cd
            if b < 0:
                a, b = -a, -b
            counter[(a, b)] += 1
    
    ans = pow(2, zero_a, MOD) + pow(2, zero_b, MOD) - 1
    memo = set()
    for a, b in list(counter):
        if (a, b) in memo:
            continue
        pa, pb = -b, a
        if pb < 0:
            pa, pb = -pa, -pb
        memo.add((a, b))
        memo.add((pa, pb))
        ans *= pow(2, counter[(a, b)], MOD) + pow(2, counter[(pa, pb)], MOD) - 1
        ans %= MOD
    
    ans = (ans + zero_pare - 1) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def gcd(x, y):
  b = max(x, y)
  s = min(x, y)
  r = b % s
  while r != 0:
    b = s
    s = r
    r = b % s
  return s

def lcm(x, y):
  return (x * y) // gcd(x,y)

def nasu(a, b):
  g = gcd(a, b)
  if g < 0:
    g *= -1
  if b < 0:
    a *= -1
    b *= -1
  return [a // g, b // g]

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

MOD = 10 ** 9 + 7
R = {}

ze = 0
na = 0
su = 0
for a, b in AB:
  if a == 0 and b == 0: 
    ze += 1
    continue
  if b == 0:
    na += 1
  elif a == 0:
    su += 1
  else:
    a, b = nasu(a, b)
    if a in R:
      if b in R[a]:
        R[a][b] += 1
      else:
        R[a][b] = 1
    else:
      R[a] = {}
      R[a][b] = 1

L = []
for i in R.keys():
  for j in R[i].keys():
    a, b = i, j
    x, y = -j, i
    if x < 0 and y < 0:
      x *= -1
      y *= -1
    t = R[i][j]
    if x not in R:
      L.append(pow(2, t, MOD))
      continue
    if y not in R[x]:
      L.append(pow(2, t, MOD))
      continue
    k = R[x][y]
    L.append((pow(2, t) + pow(2, k) - 1) % MOD)
    R[a][b] = 0
    R[x][y] = 0

L.append((pow(2, na) + pow(2, su) - 1) % MOD)

ans = 1
for i in L:
  ans = ans * i % MOD

ans = (ans + ze) % MOD

ans -= 1
if ans < 0:
  ans += MOD
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

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


def main():
    N = I()
    zero = 0
    cnts = defaultdict(int)
    used = set()

    for i in range(N):
        a, b = MI()
        if a == 0 and b == 0:
            zero += 1
            continue

        g = gcd(abs(a), abs(b))
        a = a // g
        b = b // g
        if b < 0:
            a = -a
            b = -b
        cnts[(a, b)] += 1

    # print(cnts)

    ans = 1
    for key, c in cnts.items():
        if key in used:
            continue
        a, b = key
        if a > 0:
            rev = (-b, a)
        else:
            rev = (b, -a)

        if rev in cnts:
            # keyの集合から一個以上選ぶ + revの集合から一個以上選ぶ + どれも選ばない
            ans *= (pow(2, cnts[key], MOD) - 1) + (pow(2, cnts[rev], MOD) - 1) + 1
            # print(key, rev, ans)
            ans %= MOD
            used.add(rev)
        else:
            ans *= pow(2, cnts[key], MOD)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from sys import stdin
from collections import defaultdict
from math import gcd

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    MOD = 1000000007
    
    N, *AB = map(int, stdin.buffer.read().split())
    d = defaultdict(int)
    zeros = 0
    for a, b in zip(AB[::2], AB[1::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)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Contest No.: ABC168
# Problem No.: E
# Solver:      JEMINI
# Date:        20200517

import sys
import heapq

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

def main():
    modVal = 1000000007
    n = int(input())
    ppList = []
    pnList = []
    npList = []
    nnList = []
    znList = []
    nzList = []
    pzList = []
    zpList = []
    zzList = []
    numList = [0] * n
    for _ in range(n):
        a, b = map(int, sys.stdin.readline().split())
        if a > 0 and b > 0:
            ppList.append((a, b))
        elif a > 0 and b < 0:
            pnList.append((a, b))
        elif a < 0 and b > 0:
            npList.append((a, b))
        elif a < 0 and b < 0:
            nnList.append((a, b))
        elif a == 0 and b < 0:
            znList.append((a, b))
        elif a < 0 and b == 0:
            nzList.append((a, b))
        elif a == 0 and b > 0:
            zpList.append((a, b))
        elif a > 0 and b == 0:
            pzList.append((a, b))
        else:
            zzList.append((a, b))
    ans = 1

    # zp, zn, pz, nz
    zAns = 2 ** (len(zpList) + len(znList)) % modVal + 2 ** (len(pzList) + len(nzList)) % modVal - 1
    zAns = zAns % modVal
    ans = zAns

    # pp, pn, np, nn
    ratioDict = {}
    for i in ppList:
        gcdVal = gcd(i[0], i[1])
        ratio = (i[0] // gcdVal, i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1
    for i in nnList:
        gcdVal = gcd(-i[0], -i[1])
        ratio = (-i[0] // gcdVal, -i[1] // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [1, 0]
        else:
            ratioDict[ratio][0] += 1

    for i in npList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in pnList:
        gcdVal = gcd(abs(i[0]), abs(i[1]))
        ratio = (abs(i[1]) // gcdVal, abs(i[0]) // gcdVal)
        if ratio not in ratioDict:
            ratioDict[ratio] = [0, 1]
        else:
            ratioDict[ratio][1] += 1
    for i in ratioDict:
        temp = 2 ** ratioDict[i][0] % modVal
        temp += (2 ** ratioDict[i][1] - 1) % modVal
        ans *= temp
        ans = ans % modVal

    ans -= 1
    ans += len(zzList)
    ans = ans % modVal
    print(ans)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
import collections
from collections import defaultdict
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=10**9+7

L=[]
ct0=0
for i in range(n):
  if l[i][0]==0 and l[i][1]==0:
    ct0+=1
  elif l[i][0]==0:
    L.append((0,1))
  elif l[i][1]==0:
    L.append((1,0))
  elif l[i][0]<0:
    L.append((-l[i][0]//math.gcd(l[i][0],l[i][1]),-l[i][1]//math.gcd(l[i][0],l[i][1])))
  else:
    L.append((l[i][0]//math.gcd(l[i][0],l[i][1]),l[i][1]//math.gcd(l[i][0],l[i][1])))

ans=1
d=set()
c=collections.Counter(L)
for i in c.keys():
  if i[0]==0:
    x=(1,0)
  elif i[1]==0:
    x=(0,1)
  elif i[1]<0:
    x=(-i[1],i[0])
  else:
    x=(i[1],-i[0])
  if i not in d:
    ans*=pow(2,c[i],mod)+pow(2,c[x],mod)-1
    ans%=mod
    d.add(x)
print((ans-1+ct0)%mod)

Submission status: Accepted

Solution code:
from collections import Counter
import math
n = int(input())
pp = []
a0 = 0
b0 = 0
z = 0

for i in range(n):
  a,b = map(int,input().split())
  if a==0 and b==0:
    z += 1
  elif a==0:
    a0 += 1
  elif b==0:
    b0 += 1
  else:
    gomi = math.gcd(a,b)
    if a < 0:
      a *= -1
      b *= -1
    pp.append((a//gomi,b//gomi))
    
mod = 10**9+7
a0 %= mod
b0 %= mod
z %= mod
p = Counter(pp)
r = 1
s = set()

for i,j in p.keys():
  if (i,j) in s:
    continue
  ans = p[(i,j)]
  if j < 0:
    f = (-j,i)
  else:
    f = (j,-i)
  chk = p[f]
  r *= (pow(2,ans,mod)+pow(2,chk,mod)-1)%mod
  r %= mod
  s.add(f)
r *= (pow(2,a0,mod)+pow(2,b0,mod)-1)%mod
r %= mod
print((r+z-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd

mod = 10 ** 9 + 7
n = int(input())
iwashi = dict()
origin_iwashi = 0
for _ in range(n):
  a, b = map(int, input().split())
  if a == b == 0:
    origin_iwashi += 1
  elif a == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][1] += 1
    else:
      iwashi[(1, 0)] = [0, 1]
  elif b == 0:
    if (1, 0) in iwashi:
      iwashi[(1, 0)][0] += 1
    else:
      iwashi[(1, 0)] = [1, 0]
  else:
    if b < 0:
      a, b = -a, -b
    g = gcd(a, b)
    a //= g
    b //= g
    if a > 0:
      if (a, b) in iwashi:
        iwashi[(a, b)][0] += 1
      else:
        iwashi[(a, b)] = [1, 0]
    else:
      if (b, -a) in iwashi:
        iwashi[(b, -a)][1] += 1
      else:
        iwashi[(b, -a)] = [0, 1]
count = 1
for i, j in iwashi.values():
  tmp = pow(2, i, mod) + pow(2, j, mod) - 1
  count = count * tmp % mod
count = (count + origin_iwashi - 1) % mod
print(count)

Submission status: Accepted

Solution code:
def e_bullet(MOD=10**9 + 7):
    from math import gcd
    from collections import defaultdict
    N = int(input())

    zero_all = 0
    pair = defaultdict(int)
    for _ in range(N):
        a, b = [int(i) for i in input().split()]
        if a == 0 and b == 0:
            zero_all += 1
            continue

        # 既約分数にしておきたい
        if a != 0 and b != 0:
            g = gcd(a, b) * a // abs(a)
        elif a != 0:
            g = a
        else:
            g = b
        pair[(a // g, b // g)] += 1  # 既約分数 a/b とみなす

    done = set()
    total = 1
    for (a, b), v in list(pair.items()):
        if (b, -a) in done or (-b, a) in done:
            continue  # a/b に対応するものがあるかはすでに調べた
        done.add((a, b))

        # a/b に対応する b/(-a) か (-b)/a に注目する
        w = pair[(b, -a)] + pair[(-b, a)]
        # それらを選ぶと仲が悪いので、a/b となるものだけ選ぶか b/(-a) か (-b)/a
        # となるものだけ選ぶか、どちらか一方だけ選択したときに仲が悪くならない
        # これまでの選び方に対して仲が悪くならない選び方を決めるので、total は積を取る
        # ただし、両方とも 1 つも選ばないということはできないため、-1 する
        total *= pow(2, v, MOD) + pow(2, w, MOD) - 1
        total %= MOD

    ans = (total + zero_all - 1) % MOD
    return ans

print(e_bullet())

Submission status: Accepted

Solution code:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
AB = [LI() for _ in range(N)]

MOD = 10 ** 9 + 7


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


def create_pairs():
    z = 0
    d = {}
    for a, b in AB:
        # irre
        if a == 0 and b == 0:
            z += 1
            continue
        if a == 0:
            b = 1
        elif b == 0:
            a = 1
        else:
            m = abs(gcd(a, b))
            a, b = a // m, b // m
        
        # 180
        if b < 0:
            a, b = -a, -b

        if a > 0:
            t = (a, b)
            i = 0
        else:
            t = (b, -a)
            i = 1
        if t in d:
            d[t][i] += 1
        else:
            d[t] = [0, 0]
            d[t][i] += 1
    
    return d, z


def main():
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(1, N + 1):
        p2[i] = p2[i - 1] * 2 % MOD
    
    d, z = create_pairs()
    ans = 1
    for x, y in d.values():
        v = p2[x] + p2[y] - 1
        ans = ans * v % MOD

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

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

    s = -1 if (a*b) < 0 else 1
    g = gcd(a, b)
    a //= g
    b //= g

    d[(s, abs(a), abs(b))] += 1

ans = 1
for (s, a, b), c1 in d.items():
    if c1 == 0:
        continue
    k = (-s, b, a)
    if k in d:
        c2 = d[k]
        ans *= pow(2, c1, MOD) + pow(2, c2, MOD)-1
        ans %= MOD
        d[k] = 0
    else:
        ans *= pow(2, c1, MOD)
        ans %= MOD

ans *= pow(2, zero[1], MOD)+pow(2, zero[2], MOD)-1
ans %= MOD

ans += zero[0]
ans -= 1
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque
import heapq
mod = 10**9+7
ans = 1
iw0 = 0

def twoxxn(t,mod):
    ni = t
    an = 1
    n2 = 2
    while ni > 0:
        if ni%2 == 1:
            an = (an*n2)%mod
        n2 = (n2**2)%mod
        ni >>= 1
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        iw0 += 1
        continue
    if a == 0:
        b = 1
        g = 1
    elif b == 0:
        a = 1
        g = 1
    else:
        g = math.gcd(abs(a),abs(b))
    if a < 0 :
        a = -a
        b = -b
    p1 = a//g, b//g
    if p1 in d:
        d[p1] += 1
    else:
        d[p1] = 1
done = []
for (i0,i1), din in d.items():
    if d.get((-i1,i0),1) == 0 or d.get((i1,-i0),1) == 0:
        continue
    w = d.get((i1,-i0),0) + d.get((-i1,i0),0)
    aaa = (twoxxn(w,mod)+twoxxn(din,mod)-1)%mod
    ans = (ans*aaa)%mod
    d[(i0,i1)] = 0

if len(d.keys()) == 0:
    print(iw0)
    exit()

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

Submission status: Accepted

Solution code:
import sys
import math
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict

MOD = 10**9+7
N = int(input())
dic = defaultdict(int)
zero = 0
left_zero = 0
right_zero = 0
for i in range(N):
    a, b = map(int, input().split())
    if b < 0:
        a = -a
        b = -b
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        left_zero += 1
    elif b == 0:
        right_zero += 1
    else:
        g = math.gcd(a, b)
        a //= g
        b //= g
        dic[a,b] += 1
done = set()
ans = 1
for a,b in dic:
    k = (a, b)
    if k in done: continue
    rk = (-b, a)
    rk2 = (b, -a)
    done.add(k)
    done.add(rk)
    done.add(rk2)
    c = pow(2, dic[k], MOD)-1
    if rk in dic:
        c += pow(2, dic[rk], MOD)-1
    if rk2 in dic:
        c += pow(2, dic[rk2], MOD)-1
    c += 1
    ans *= c
    ans %= MOD
c1 = pow(2, left_zero, MOD)-1
c2 = pow(2, right_zero, MOD)-1
c = c1+c2+1
ans *= c
ans += zero
print((ans-1)%MOD)

Submission status: Accepted

Solution code:
import math

n = int(input())
mod = 10 ** 9 + 7

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (pow(2, num2, mod) + pow(2, num3, mod) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= pow(2, n, mod)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 1 ;count = 0 ;pro = 1
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)

n = int(input())
def make_key0(a,b):
  if a == 0 and b != 0:
    return(0,1)
  elif a != 0 and b == 0:
    return(1,0)
  if (a < 0 and b > 0) or (a > 0 and b < 0):hugou = 1
  else: hugou = -1
  a = abs(a)
  b = abs(b)
  G = gcd(a,b)
  return (hugou*(abs(a)//G),abs(b)//G)

C0 = collections.Counter()

for i in range(n):
  a,b = map(int,input().split())
  if (a,b) == (0,0) :count += 1
  else:
    a0,b0 = make_key0(a,b)
    C0[(a0,b0)] += 1

S = set()
for key,val in C0.items():
  a0,b0 = key
  S.add((a0,b0))
  a1,b1 = make_key0(b0,a0)
  if (a1,b1) in S:continue
  ans *= pow(2,val,mod) + pow(2,C0[(a1,b1)],mod) -1
  ans %= mod
ans += count 
print((ans-1)%mod)

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
MOD = 10**9+7
p_map = {}
n_map = {}

p_zero_map = 0
n_zero_map = 0
z_map = 0
for _ in range(n):
    ab = list(map(int, input().split()))
    ab_gcd = gcd(ab[0], ab[1])
    if ab_gcd == 0:
        ab_gcd = 1
    a = ab[0]//ab_gcd
    b = ab[1]//ab_gcd

    if (a > 0 and b > 0) or (a < 0 and b < 0):
        if a < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in p_map:
            p_map[key] = 1
        else:
            p_map[key] += 1
    elif a == 0 and b == 0:
        z_map += 1
    elif a == 0 and b != 0:
        n_zero_map += 1
    elif b == 0 and a != 0:
        p_zero_map += 1
    else:
        if b < 0:
            a = -a
            b = -b
        key = "{}_{}".format(a, b)
        if key not in n_map:
            n_map[key] = 1
        else:
            n_map[key] += 1

ans = 1
for k, v in p_map.items():
    a = int(k.split("_")[0])
    b = int(k.split("_")[1])
    n_num = 0
    key_a = "{}_{}".format(-b, a)
    if key_a in n_map:
        n_num += n_map.pop(key_a)
    res = 0
    res += pow(2, v, MOD)-1
    if n_num > 0:
        res += pow(2, n_num, MOD)-1
    res += 1
    ans *= res
    ans %= MOD

n_num = sum(n_map.values())
if n_num > 0:
    ans *= pow(2, n_num, MOD)
    ans %= MOD

res = 0
if p_zero_map > 0 and n_zero_map > 0:
    res = pow(2, p_zero_map, MOD)-1 + pow(2, n_zero_map, MOD)-1
    res += 1
    res %= MOD
elif p_zero_map > 0 and n_zero_map == 0:
    res = pow(2, p_zero_map, MOD)
elif p_zero_map == 0 and n_zero_map > 0:
    res = pow(2, n_zero_map, MOD)
if res > 0:
    ans *= res
    ans %= MOD


if z_map > 0:
    ans += z_map
ans -= 1
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
mod = 10 ** 9 + 7

ab = {}
for i in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        pass
    elif a == 0:
        b = 1
    else:
        gcd = math.gcd(a, b)
        a //= gcd
        b //= gcd
        if a < 0:
            a, b = -a, -b
    num = (a, b)
    ab.setdefault(num, 0)
    ab[num] += 1
bin_n = [2]
for i in range(len(bin(n)) - 3):
    temp = bin_n[-1]
    temp = temp ** 2
    temp %= mod
    bin_n.append(temp)
def beki2(n):
    num = bin(n)
    temp = 1
    for i in range(len(num) - 2):
        if num[-i-1] == "1":
            temp *= bin_n[i]
            temp %= mod
    return temp

ans = 0
if (0, 0) in ab.keys():
    temp2 = ab[(0, 0)]
    ans += temp2
    n -= temp2
s = set(ab.keys())
pairs = []
for i in ab.keys():
    if i == (0, 0):
        continue
    else:
        a, b = i[0], i[1]
        if (-b, a) in s:
            pairs.append([ab[(a, b)], ab[(-b, a)]])
temp3 = 1
for i in range(len(pairs)):
    num2 = pairs[i][0]
    num3 = pairs[i][1]
    temp3 *= (beki2(num2) + beki2(num3) - 1)
    n = n- num2 - num3
    temp3 %= mod
temp3 *= beki2(n)
temp3 -= 1
temp3 %= mod
ans += temp3
ans %= mod
print(ans)