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: Wrong Answer

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

N = 1000000007

def rate(a,b):
    if a==0:
        return (0,1)
    elif b==0:
        return (1,0)
    elif a==b and b==0:
        return (0,0)
    r=1
    a1=a
    b1=b
    while r!=0:
        r=a1%b1
        a1=b1
        b1=r
    return (a//a1 , b//a1)

z =[]

for i in range(n):
    b , c = map(int, input().split())
    z.append(rate(b,c))

c = Counter(z)

k = list(c.keys())
v = list(c.values())


d=[]
e=0

for i in k:
    x,y=i
    if x<0:
        x*=-1
        y*=-1
    if (y*(-1),x) in k:
        t = (y*(-1),x)
        if not (c[t],c[i]) in d:
            d.append((c[i],c[t]))
    else:
        e+=c[i]
e-=c[(0,0)]
ans = 1
for i in d:
    x,y=i
    ans *= pow(2,x,N) + pow(2,y,N)-1
ans*=pow(2,e,N)
print(ans%N-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            f = b / a
            if b / a < 0:
                m.append(-round(a / b, 6))
            elif f > 0:
                p.append(round(b / a, 6))
        else:
            m.append(0.0)

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from math import gcd

def main():
    N = int(input())
    minus_iwashi = {}
    iwashi = {}
    a0 = 0
    b0 = 0
    a0b0 = 0
    
    for _ in range(N):
        a,b = map(int,input().split())
        if a < 0 and b > 0:
            a = -a
            b = -b
        elif a < 0 and b < 0:
            a = -a
            b = -b
        if a == 0 and b == 0:
            a0b0 += 1
            continue
        if a == 0 and b != 0:
            a0 += 1
            continue
        if b == 0 and a != 0:
            b0 += 1
            continue
        #print(a,b)
        if b < 0:
            a,b = -b,a
            #print('mini{}{}'.format(a,b))
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in minus_iwashi:
                minus_iwashi[(a,b)] += 1
            else:
                minus_iwashi[(a,b)] = 1
        elif b > 0:
            x = gcd(a,b)
            a //= x
            b //= x
            if (a,b) in iwashi:
                iwashi[(a,b)] += 1
            else:
                iwashi[(a,b)] = 1
    
    power = [1]
    for _ in range(N):
        power.append(power[-1]*2%MOD)
    '''
    print(power)
    print(iwashi)
    print(minus_iwashi)
    print(a0,b0)
    '''
    
    if a0 > 0 and b0 > 0:
        ans = power[a0] + power[b0] - 1
    elif a0 > 0:
        ans = power[a0]
    elif b0 > 0:
        ans = power[b0]
    else:
        ans = 1

    for k,v in iwashi.items():
        if k in minus_iwashi:
            ans *= (power[v] + power[minus_iwashi[k]] - 1)
            ans %= MOD
        else:
            ans *= power[v]
            ans %= MOD
    
    for k,v in minus_iwashi.items():
        if k in iwashi:
            continue
        else:
            ans *= power[v]
            ans %= MOD
    print((ans - 1)%MOD)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

from collections import Counter
from fractions import Fraction
C=Counter()

for a,b in S:
    if a==0 and b==0:
        continue
    if b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=1

for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

        C[x]=0
        C[Fraction(-d,n)]=0
        
    else:
        ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

        C[float("inf")]=0
        C[Fraction(0,1)]=0

print((ANS-1)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = []
b = []
for _ in range(n):
  tmp = input().split()
  a.append(int(tmp[0]))
  b.append(int(tmp[1]))

counter = 0

for i in range(2 ** n):
  p_list = []
  m_list = []
  z_list = []
  j_list = []
  for j in range(n):
    if (i >> j) & 1:
      j_list.append(j)
      calc = a[j] * b[j]
      if calc > 0:
        p_list.append(calc)
      elif calc < 0:
        m_list.append(-1 * calc)
      else:
        z_list.append(calc)
  if j_list != [] and len(z_list) < 2 and len(set(p_list) & set(m_list)) == 0:
    counter += 1
    counter = counter % 1000000007

print(counter)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

mod = 10**9 + 7


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


col = []
row = []
zero = False
for a, b in A:
    if a == b == 0:
        zero = True
        continue
    if a == 0:
        b = 1
    elif b == 0:
        a = 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g

    if a < 0:
        a *= -1
        b *= -1

    if a >= 0 and b > 0:
        col.append((a, b))
    elif a > 0 and b < 0 or b == 0:
        row.append((-b, a))


C = Counter(col)
D = Counter(row)
S = set(col) | set(row)


ans = 1
for s in S:
    if s in C:
        if s in D:
            mul = modpow(2, C[s], mod) + modpow(2, D[s], mod) - 1
            mul %= mod
        else:
            mul = modpow(2, C[s], mod)
    elif s in D:
        mul = modpow(2, D[s], mod)

    ans *= mul
    ans %= mod

ans -= 1
if zero:
    ans += 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import math
MOD =1000000007


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

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 or b==0:
        zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

ans *= (zero_cnt+1)
ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from fractions import Fraction as Fra, gcd
from collections import Counter

def solve(N, A):
    MOD = 10 **9 + 7
    # Cant if dot product is 0
    count = Counter()
    for x, y in A:
        g = gcd(x, y)
        if g:
            x //= g
            y //= g
        count[x, y] += 1
    m = max(count.itervalues())
    powers = [1]
    for i in xrange(m):
        powers.append(powers[-1] * 2 % MOD)
        
    # x,y = -y,x
    ans = 1
    for (x, y), c1 in count.iteritems():
        px, py = -y, x
        pg = gcd(px, py)
        if pg:
            px//=pg; py//=pg;
        c2 = count[px, py]
        if not c2:
            ans *= powers[c1]
            ans %= MOD
        elif (x,y) < (px,py):
            f = (powers[c1] + powers[c2] - 1)%MOD
            ans *= f
            ans %= MOD
    return (ans - 1) % MOD
    
    
N = rri()
A = [rrm() for _ in xrange(N)]
print solve(N, A)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
import sys
from collections import Counter
from math import gcd
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
ans = 0
c = Counter()
zero = False
for _ in range(n):
	a, b = map(int, input().split())
	if a == b == 0:
		zero = True
		continue
	if a < 0:
		a, b = -a, -b
	if a == 0:
		a, b = 0, 1
	if b == 0:
		a, b = 1, 0
	g = gcd(a, b)
	c[(a//g, b//g)] += 1

ans = 1
for k, v in c.items():
	#print(k, v)
	if k[1] <= 0:
		x, y = -k[1], k[0]
		if c[(x, y)] > 0:
			continue
	else:
		x, y = k[1], -k[0]
	res = 0
	res += pow(2, v, MOD) - 1
	res += pow(2, c[(x, y)], MOD) - 1
	res += 1
	ans *= res
	ans %= MOD

if not zero:
	ans -= 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
MOD = 1000000007
s = {}

for _ in range(N):
    A, B = map(int, input().split())
    if B == 0:
        key = float('inf')
    else:
        key = A/B
    if s.get(key) == None:
        s[key] = 1
    else:
        s[key] += 1

f, ans = 0, 1
while len(s) > 0:
    k1, v1 = s.popitem()
    if k1 == 0:
        key = float('inf')
    else:
        key = -1/k1
    if key in s.keys():
        v2 = s.pop(key)
        Cv1, Cv2 = pow(2, v1, MOD), pow(2, v2, MOD)     # pow(2, n, MOD) は二項定理による組み合わせの総和
        C = ((Cv1 + Cv2) % MOD - 1) % MOD
        ans = (ans * C) % MOD
    else:
        f += v1

ans = ((ans * pow(2, f, MOD)) % MOD - 1) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
from functools import cmp_to_key

MOD = 10 ** 9 + 7


def func(a, b):
    if a[0] * b[1] == a[1] * b[0]:
        return 0
    elif a[0] * b[1] < a[1] * b[0]:
        return - 1
    else:
        return 1


n = int(input())
a = [0] * n
b = [0] * n
i = 0
f = 0
while i < n:
    a[i], b[i] = map(int, input().split())
    if a[i] == 0 and b[i] == 0:
        f = 1
        n -= 1
        continue
    if a[i] < 0:
        a[i] = -a[i]
        b[i] = -b[i]
    if a[i] == 0 and b[i] < 0:
        b[i] = -b[i]
    i += 1
l = sorted(zip(a, b), key=cmp_to_key(func))
if l[0][1] > 0:
    li = [[1, 0, l[0][0], l[0][1]]]
else:
    li = []
for i in range(1, n):
    a, b = l[i - 1]
    c, d = l[i]
    if d <= 0:
        break
    if li and a * d == b * c:
        li[-1][0] += 1
    else:
        li.append([1, 0, c, d])
idx = 0
cnt = 0
for j in range(n):
    a, b = l[j]
    if a == 0 and b == 0:
        f = 1
        continue
    if b > 0:
        continue
    a, b = -b, a
    while idx < len(li) and li[idx][2] * b < li[idx][3] * a:
        idx += 1
    if idx < len(li) and li[idx][2] * b == li[idx][3] * a:
        li[idx][1] += 1
    else:
        cnt += 1
ans = 1
for a, b, c, d in li:
    ans *= (pow(2, a, MOD) + pow(2, b, MOD) - 1)
    ans %= MOD
print((ans * (pow(2, cnt, MOD)) - 1 + f) % MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    if Btmp!=0:
        AB.append(Atmp/Btmp)
    else:
        AB.append(float('inf')*Atmp*Btmp)

def power_func(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

from collections import Counter
C = Counter(AB)

kaburi = []
forsum = []
for key in C:
    if key<0:
        if C[-1/key]!=0:
            kaburi.append([C[key],C[-1/key]])
            forsum.append(C[key]+C[-1/key])

p = 10**9+7

free = N-sum(forsum)
free2 = power_func(2,free,p)
L = len(kaburi)

out = 1
for i in range(len(kaburi)):
    X = kaburi[i][0]
    Y = kaburi[i][1]
    B = power_func(2,X,p)
    C = power_func(2,Y,p)
    out = out*((B+C-1)%p)
    out = out%p
print((out*free2-1)%p)

Submission status: Wrong Answer

Solution code:
import sys,math,bisect
input = sys.stdin.readline

mod = 1000000007
eps = 0.00000000001

n = int(input())

ab = []
ang = []
half = math.pi/2.0

for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0:
        ang.append(half)
    else:
        ang.append(math.atan(b/a))
ang.sort()

res = 1
rest = n

i = 0
while True:
    if i >= n:
        break
    val = ang[i]
    if val > 2*eps:
        break
    cnt = bisect.bisect_right(ang,val+eps) - i
    cnt2 = bisect.bisect_right(ang,val+half+eps) - bisect.bisect_left(ang,val+half-eps)
    if cnt2 > 0:
        rest = rest - cnt - cnt2
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
    i += cnt
rest = max(rest,0)
res = res*pow(2,rest,mod)%mod - 1
print(res%mod)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import math
import sys
MOD = 1000000007  # type: int


def powm(a, n, m):
    if a == 1 or n == 0:
        return 1
    if n % 2 == 0:
        s = powm(a, n // 2, m)
        return s * s % m
    else:
        return a * powm(a, n - 1, m) % m

def solve(N: int, A: "List[int]", B: "List[int]"):
    # fishes = {}
    # zeroFishesB = 0
    # zeroFishesA = 0
    # valueFishes = N
    #
    # def getFishC(a):
    #     return fishes[a] if a in fishes else 0
    # for i in range(N):
    #     if A[i] == 0 and B[i] == 0: # 両方0,0ならばどの魚とも仲良くなれないので消す
    #         valueFishes -= 1
    #         continue
    #     if A[i] == 0:
    #         zeroFishesA += 1
    #     if B[i] == 0:
    #         zeroFishesB += 1
    #     fishes[(A[i],B[i])] = getFishC((A[i],B[i]))+1
    # def countWithZero(a): # aと中の悪い魚の数を返す
    #     if a[0] != 0 or a[1] != 0:
    #         return getFishC((-a[1],a[0]))+getFishC((a[1],-a[0]))
    #     else:
    #         if a[0] == 0:
    #             return zeroFishesB
    #         else:
    #             return zeroFishesA
    #
    # allCandidate = powm(2,valueFishes,MOD)-1
    # print(allCandidate)
    # for k in fishes:
    #     print(f"{k}->{countWithZero(k)}")
    fishes = []
    validFishes = N
    fishRads = dict()
    for i in range(N):
        if A[i] == 0 or B[i] == 0:
            validFishes-=1
            continue
        fishes.append((A[i],B[i]))
        norm = math.sqrt(A[i]**2+B[i]**2)
        normalRad = abs(A[i])/norm/(abs(B[i])/norm)
        cur = (0,0)
        if (A[i] > 0 and B[i] >= 0) or (A[i] < 0 and B[i] <= 0):
            if normalRad in fishRads:
                cur = fishRads[normalRad]
            fishRads[normalRad] = (cur[0]+1,cur[1])
        else:
            rotRad = abs(B[i]) / norm / (abs(A[i]) / norm)
            if rotRad in fishRads:
                cur = fishRads[rotRad]
            fishRads[rotRad] = (cur[0], cur[1]+1)
    current = 1
    for k in fishRads:
        groups = fishRads[k]
        stage= (powm(2,groups[0],MOD) + powm(2,groups[1],MOD)-1)%MOD
        current = current*stage%MOD
    print(current-1)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import Fraction
 
 
 
a = int(input())
resab = dict()
resba = dict()
res0 = 0
res0a = 0
res0b = 0
 
for i in range(a):
    ai, bi = [int(i) for i in input().split()]
    if ai != 0 and bi != 0:
        if Fraction(ai, bi) not in resab:
            resab[Fraction(ai, bi)] = 1
        else:
            resab[Fraction(ai, bi)] += 1
        if Fraction(-bi, ai) not in resba:
            resba[Fraction(-bi, ai)] = 1
        else:
            resba[Fraction(-bi, ai)] += 1
    else:
        if ai == 0 and bi == 0:
            res0 += 1
        elif ai == 0:
            res0a += 1
        elif bi == 0:
            res0b += 1
 

ans = 1
for i in list(resab.keys()):
    if i in resba and i in resab:
        ans *= (2**resab[i] - 1 + 2**resba[i]) 
        #print(ans, i)
        del resab[i]
        del resab[Fraction(-i.denominator, i.numerator)]
        del resba[i]
        del resba[Fraction(-i.denominator, i.numerator)]
    elif i in resba:
        ans *= resba[i] + 1
        #print(ans, i)
        del resba[i]
        try:
            del resab[Fraction(-i.denominator, i.numerator)]
        except:
            pass
    elif i in resab:
        ans *= resab[i] + 1
        #print(ans, i)
        del resab[i]
        try:
            del resba[Fraction(-i.denominator, i.numerator)]
        except:
            pass
        
    ans %= 1000000007
 
ans *= (2 ** res0a)
ans *= (2 ** res0b)
ans *= (res0 + 1)
ans -= 1
ans %= 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:

from collections import defaultdict
from math import gcd

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

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

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

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

ans*=pow(2,others,mod)
ans%=mod

print(ans+zero-1)

"""
4
0 1
0 1
1 0
1 0
"""

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit


def main():
    mod = 10 ** 9 + 7
    input = stdin.buffer.readline
    n = int(input())
    p = []
    m = []

    for _ in range(n):
        a, b = map(int, input().split())
        if a != 0 and b != 0:
            f = b / a
            if b / a < 0:
                m.append(-round(a / b, 6))
            elif f > 0:
                p.append(round(b / a, 6))

    g_p = {}
    for k in p:
        if k in g_p:
            g_p[k] += 1
        else:
            g_p[k] = 1
    g_m = {}
    for k in m:
        if k in g_m:
            g_m[k] += 1
        else:
            g_m[k] = 1

    ans = 1

    for k in g_p:
        if k in g_m:
            ans *= (2 ** g_p[k] + 2 ** g_m[k] - 1)
        else:
            ans *= 2 ** g_p[k]
        ans %= mod
    for k in g_m:
        if not (k in g_p):
            ans *= 2 ** g_m[k]
            ans %= mod
    print((ans - 1) % mod)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Wrong Answer

Solution code:
from fractions import Fraction

PRIME = 1000000007
n = int(input())

fish = {}
taste_0 = 0
flavor_0 = 0

for i in range(n):
  a, b = map(int, input().split())
  if a != 0 and b != 0:
    if Fraction(a, b) in fish:
      fish[Fraction(a, b)] += 1
    else:
      fish[Fraction(a, b)] = 1
  elif a == 0:
    taste_0 += 1
  else:
    flavor_0 += 1

ans = pow(2, taste_0, PRIME)
ans += pow(2, flavor_0, PRIME) - 1
ans %= PRIME

cnt = 0
for f in fish:
  inverse_f = Fraction(-f.denominator, f.numerator)
  if inverse_f in fish and fish[f] > 0:
    ans1 = pow(2, fish[f], PRIME)
    ans1 += pow(2, fish[inverse_f], PRIME) - 1
    ans *= ans1
    ans %= PRIME
    fish[f] = 0
    fish[inverse_f] = 0
  elif inverse_f not in fish:
    cnt += fish[f]

ans *= pow(2, cnt, PRIME)
ans %= PRIME

ans += PRIME - 1
ans %= PRIME

print(ans)

Submission status: Wrong Answer

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

def main():
    n = int(input())
    ans = 1
    C = defaultdict(int)
    z = 0
    for i in range(n):
        a, b = map(int, input().split())
        if b == 0:
            z += 1
        elif a == 0:
            C[0] += 1
        else:
            g = gcd(a, b)
            a //= g
            b //= g
            if a < 0:
                a, b = -a, -b
            C[(a, b)] += 1
    D = tuple(C.items())
    used = {0}
    for c, v in D:
        if c in used:
            continue
        a, b = c
        if b > 0:
            d, e = b, -a
        else:
            d, e = -b, a
        ans *= (pow(2, v, MOD)+pow(2, C[(d, e)], MOD)-1)
        ans %= MOD
        used.add((d, e))
    ans *= (pow(2, C[0], MOD)+pow(2, z, MOD)-1)
    ans -= 1
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math
MOD = 10**9 + 7


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

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 or b==0:
        zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

ans *= (zero_cnt+1)
# ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

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

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

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

from collections import Counter
from fractions import Fraction
C=Counter()

for a,b in S:
    if a==0 and b==0:
        continue
    if b!=0:
        C[Fraction(a,b)]+=1
    else:
        C[float("inf")]+=1
    
ANS=1
print(C)
for x in list(C.keys()):
    if x!=float("inf") and x!=Fraction(0,1):
        n=x.numerator
        d=x.denominator

        ANS=ANS*(pow(2,C[x],mod)+pow(2,C[Fraction(-d,n)],mod)-1)%mod

        C[x]=0
        C[Fraction(-d,n)]=0
        
    else:
        ANS=ANS*(pow(2,C[float("inf")],mod)+pow(2,C[Fraction(0,1)],mod)-1)%mod

        C[float("inf")]=0
        C[Fraction(0,1)]=0

print((ANS-1)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
ls = [list(map(int,input().split())) for _ in range(n)]
mod = 1000000007
ans = 1
visited=[False]*n
for i in range(n):
  if visited[i]:
    continue
  x=1;y=0
  for j in range(i+1,n):
    if ls[i][0]*ls[j][0]+ls[i][1]*ls[j][1]==0:
      visited[j] = True
      y+=1
      #print(i,j,"y")
    if ls[i][0]*ls[j][1]==ls[j][0]*ls[i][1]:
      visited[j] = True
      x+=1
      #print(i,j,"x")
  ans = ans*(pow(2,x,mod)+pow(2,y,mod)-1) % mod
  
  
  
print(ans-1)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)

mod = 10**9 + 7


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


col = []
row = []
zero = False
for a, b in A:
    if a == b == 0:
        zero = True
        continue
    if a == 0:
        b = 1
    elif b == 0:
        a = 1
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g

    if a < 0:
        a *= -1
        b *= -1

    if a >= 0 and b > 0:
        col.append((a, b))
    elif a > 0 and b < 0 or b == 0:
        row.append((-b, a))


C = Counter(col)
D = Counter(row)
S = set(col) | set(row)


ans = 1
for s in S:
    if s in C:
        if s in D:
            mul = modpow(2, C[s], mod) + modpow(2, D[s], mod) - 1
        else:
            mul = modpow(2, C[s], mod)
    elif s in D:
        mul = modpow(2, D[s], mod)

    ans *= mul
    ans %= mod

ans -= 1
if zero:
    ans += 1
ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(500000)

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

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

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

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

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

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

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

    pair = []
    ll = lambda : False

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

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

    mod = 1000000007

    ans = 1

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

    ans += zero
    ans %= mod

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n=int(input())
d={}
ex=0
for i in range(n):
    a,b=map(int,input().split())
    if a==0 and b==0:
        ex+=1
    elif a==0:
        if 0 not in d:
            d[0]=[1,0]
        else:
            d[0][0]+=1
    elif b==0:
        if 0 not in d:
            d[0]=[0,1]
        else:
            d[0][1]+=1
    else:
        if a/b not in d and -b/a not in d:
            d[a/b]=[1,0]
        elif a/b in d:
            d[a/b][0]+=1
        else:
            d[-b/a][1]+=1
sq=[1]*(n+1)
for i in range(n):
    sq[i+1]=2*sq[i]%1000000007

ans=1
r=list(d.values())
for i in range(len(r)):
    ans*=(sq[r[i][0]]+sq[r[i][1]]-1)%1000000007
print(ans+ex-1)

Submission status: Wrong Answer

Solution code:
import math
MOD = 10**9 + 7


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

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        # print(K,x)
        x%=MOD
    return K * x


n = int(input())

a_b_d = {}
# b_a_d = {}

zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 or b==0:
        zero_cnt += 1
    else:
        gcd_ab = math.gcd(a,b)
        a = a//gcd_ab
        b = b//gcd_ab
        if a > 0 and b < 0:
            a *= -1
            b *= -1
        elif a < 0 and b < 0:
            a *= -1
            b *=-1
        a_b_d.setdefault((a,b),0)
        a_b_d[(a,b)] += 1


done_list = set()
pair_cnt = []
uniq_cnt = 0
for k,v in a_b_d.items():
    comp_pair1 = (-k[1], k[0])
    comp_pair2 = (k[1], -k[0])
    if k in done_list:
        continue
    if comp_pair1 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        # print(k, comp_pair)
        done_list.add(comp_pair2)
        pair_cnt.append((v,a_b_d[comp_pair2]))
    else:
        uniq_cnt += 1


ans = pow_k(2,uniq_cnt) % MOD
for pair in pair_cnt:
    ans *= (pow_k(2,pair[0]) + pow_k(2,pair[1]) -1 )
    ans%=MOD

ans *= (zero_cnt+1)
ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
mod = 10**9 + 7
all = (2**N-1)%mod
subtract = ((N+1)*(N-2)//2)%mod
A = [0]*N
B = [0]*N
for i in range(N):
  A[i],B[i] = map(int,input().split())
for i in range(N):
  for j in range(i+1,N):
    if A[i]*A[j] == -B[i]*B[j]:
      all = (all - subtract)%mod
print(all)