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:
#!/usr/bin/env python3
import sys
import math
from collections import defaultdict
from bisect import bisect_left
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class UnionFind(object):
    def __init__(self, N):
        self.tree = list(range(N))

    def root(self, i):
        if self.tree[i] == i:
            return i
        else:
            self.tree[i] = self.root(self.tree[i])
            return self.tree[i]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            self.tree[x] = y


def solve(N: int, A: "List[int]", B: "List[int]"):
    # 直交するイワシは選べない
    # イワシをソートする
    abtheta = sorted(zip(A, B), key=lambda x: math.atan2(x[1], x[0]))
    # 順にイワシを見てグループを探す。二分探索で探す。
    uf = UnionFind(N)

    circle2 = abtheta*2

    end, end2 = 0, None
    for i in range(N):
        # イワシiと90度、180度、270度角度が異なるものはありますか
        # しゃくとりで
        a, b = abtheta[i]

        # 90度の関係にあるもの
        while end <= N+i:
            ai, bi = circle2[end]
            if ai*a+bi*b <= 0:
                break
            end += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end % N)
            end += 1
            if end >= 2*N:
                break
            ai, bi = circle2[end]

        if end2 == None:
            end2 = end
            while end2 <= N+i:
                ai, bi = circle2[end2]
                if ai*a + bi*b == 0:
                    end2 += 1
                else:
                    break

        # 180度のみなら別グループとして扱えば良いし、
        # 組み合わさるケースは別の点で検出できる

        # 270度の関係にあるもの
        while end2 <= N+i:
            ai, bi = circle2[end2]
            if ai*a+bi*b >= 0:
                break
            end2 += 1

        while ai*a+bi*b == 0:
            uf.unite(i, end2 % N)
            end2 += 1
            if end2 >= 2*N:
                break
            ai, bi = circle2[end2]

        if end == i + 1:
            end += 1

    # デフォルトディクトに変換する
    d = defaultdict(list)
    for i in range(N):
        d[uf.root(i)].append(abtheta[i])

    ans = 1
    for key in d:
        # 各グループをさらに二つに分類
        maru, batu = 1, 0
        a0, b0 = d[key][0]
        for a, b in d[key][1:]:
            if a0 * a + b0*b == 0:
                batu += 1
            else:
                maru += 1
        buf = pow(2, maru, MOD)
        buf += pow(2, batu, MOD)
        buf -= 1
        buf %= MOD
        ans *= buf

    # print(d)
    print((ans-1) % MOD)

    return


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:
n=int(input())
ablist=[]
slist=[]
zeros=[0,0,0]

for i in range(n):
    a, b = map(int,input().split())
    if a==0:
        if b==0:
            zeros[2]+=1
        else:
            zeros[1]+=1
    else:
        if b==0:
            zeros[0]+=1
        else:
            if a*b>0:
                slist.append([float(a)/float(b), 1, a, b])
            else:
                slist.append([float(b)/float(-a), -1, a, b])

slist=sorted(slist)
#print(slist)

#print(zeros)
zerok=2**(zeros[0]) + 2**(zeros[1]) - 1
zerok%=1000000007
#print(zerok)

mae=[0, 0]
onaji=[1, 0]

answer=1
#print(slist)

rev=0
swit=0
#print(slist)

for sl in slist:
    swit=0
    if sl[0]==mae[0]:
        if sl[1]==mae[1]:
            if rev==0:
                onaji[0]+=1
            else:
                onaji[1]+=1
        else:
            onaji[1]+=1
            rev=1
        
    else:
        if mae!=[0, 0]:
            answer*=(2**onaji[0]+2**onaji[1]-1)
            answer%=1000000007
            onaji=[1, 0]
            rev=0
            swit=1
    
    mae=sl
    #print(answer)

if len(slist)>0:
    answer*=(2**onaji[0]+2**onaji[1]-1)
    answer%=1000000007

#print(answer)

answer*=zerok
answer+=zeros[2]

print((answer-1)%1000000007)

Submission status: Wrong Answer

Solution code:

from collections import Counter
mod = 1000000007

n = int(input())
a_div_b = []
a_0 = 0
b_0 = 0
a_b_0 = 0
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            a_b_0 += 1
            break
        if a == 0:
            a_0 += 1
        if b == 0:
            b_0 += 1
        break
    if a * b < 0:
        a_div_b.append(a/b)
    else:
        a_div_b.append(b/a)

cnt = Counter(a_div_b)
cnt2 = sorted(cnt.items())
lst = []
total = 0
for num, _ in cnt2:
    if num > 0:
        break
    a1 = cnt[num]
    a2 = cnt[-num]
    if a1 * a2 != 0:
        total += a1 + a2
        lst.append([a1, a2])
if a_0 > 0 and b_0 > 0:
    total += a0 + b0
    lst.append([a0, b0])
n -= a_b_0
ans = pow(2, n - total, mod)
for a, b in lst:
    ans = (ans * (pow(2, a, mod) + pow(2, b, mod) - 1)) % mod
ans = (ans - 1 + a_b_0) % mod
    
print(ans)

Submission status: Wrong Answer

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

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 //= 2
    return an

n = int(input())
d = dict()
for i in range(n):
    a,b = map(int,input().split())
    if a < 0 :
        a = -a
        b = -b
    if a == 0:
        g = abs(b)
    elif b == 0:
        g = abs(a)
    else:
        g = math.gcd(abs(a),abs(b))
    if a == 0 and b == 0:
        continue
    else:
        p1 = str(a//g)+" "+str(b//g)
        if p1 in d:
            d[p1] += 1
        else:
            d[p1] = 1

for i in d.keys():
    i0, i1 = map(int,i.split())
    if str(i1)+" "+str(-i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(i1)+" "+str(-i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(i1)+" "+str(-i0)] = 0
    elif str(-i1)+" "+str(i0) in d:
        if d[i] == 0:
            continue
        aaa = (twoxxn(d[str(-i1)+" "+str(i0)],mod)+twoxxn(d[i],mod)-1)%mod
        ans = (ans*aaa)%mod
        d[str(-i1)+" "+str(i0)] = 0
    else:
        ans = (ans*twoxxn(d[i],mod))%mod
ans = (ans-1)%mod

print(max(1,ans))

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    dic = defaultdict(int)
    dic1 = defaultdict(int)
    for _ in range(n):
        a,b = inpm()
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                m = gcd(a,b)
                a //= m
                b //= m
        if a < 0 and b < 0:
            a = -a
            b = -b
        if a < 0 and b > 0:
            a = -a
            b = -b
        index = ' '.join([str(a),str(b)])
        dic[index] += 1
        dic1[index] += 1
    ans = 1
    dic2 = defaultdict(int)
    for e in dic:
        a,b = map(int,e.split())
        if a == 0 or b == 0:
            continue
        flag = 0
        if a > 0 and b > 0:
            rev = ' '.join([str(b),str(-a)])
        else:
            rev = ' '.join([str(-b),str(a)])
        if dic1[rev] > 0 and dic2[rev] == 0:
            dic2[rev] = 1
            dic2[e] = 1
            flag = 1
        if flag:
            continue
        n1 = pow(2,dic[e],mod)
        n2 = pow(2,dic1[rev],mod)
        if n1 == 0:
            ans *= n2
        elif n2 == 0:
            ans *= n1
        else:
            ans *= (n1+n2-1)
        ans %= mod
    num = 0
    num += dic['0 0']+1
    num %= mod
    if dic['1 0'] and dic['0 1']:
        num += (pow(2,dic['1 0'],mod)+pow(2,dic['0 1'],mod)-2)
        num %= mod
    elif dic['1 0']:
        num += pow(2,dic['1 0'],mod)-1
        num %= mod
    elif dic['0 1']:
        num += pow(2,dic['0 1'],mod)-1
        num %= mod
    ans *= num
    ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect


mod=10**20+7

n=int(input())

dp=defaultdict(int)
dm=defaultdict(int)
z=0
ans=0
cp=[]
cm=[]
az=0
bz=0
cz=0
for i in range(n):
    a,b=map(int,input().split())
    if a*b>0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        pp=(abs(b)*pow(abs(a),mod-2,mod))%mod
        if dp[p]==0:
            cp.append([p,pp])
        dp[p]+=1
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        dm[p]+=1
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1

kk=pow(2,az,mod)+pow(2,bz,mod)-1
if kk>0:
    ans=kk
else:
    ans=1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    ans%=mod
    z-=(dp[a]+dm[b])
# print(z)
ans*=pow(2,z,mod)

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd
from collections import Counter
mod = 10**9+7
def f(aai, bbi):
    if (aai == 0)&(bbi==0):
        return 0, 0
    gc = gcd(aai, bbi)
    a, b = aai // gc, bbi // gc
    if a < 0:
        a = -a
        b = -b
    return a, b

n= int(input())
aa = [0] * n
for i in range(n):
    ai, bi = map(int, input().split())
    aa[i] = f(ai, bi)

dic_ = Counter(aa)

cnt = 1
while len(dic_) > 0:
    k, v = dic_.popitem()
    ka , kb = k[0], k[1]
    if kb < 0:
        ka = -ka
        kb = -kb
    t = dic_.get((kb, -ka), 0)
    if t > 0:
        del dic_[(kb, -ka)]
        cnt *= ((2**v) + (2**t) - 1) % mod
    else:
        cnt *= (2**v) % mod
print((cnt+mod-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4000)
import math
N = int(input())
mod = 1000000007
degs = {}
ans = 1
for i in range(N):
    A,B = map(int,input().split())
    if(A!=0):
        ab = B/A
    else:
        ab = "mugen"
    if(ab==0):
        nakawaru = "mugen"
    elif(ab == "mugen"):
        nakawaru = 0
    else:
        nakawaru = -1/ab
    if(ab not in degs.keys()):
        degs[ab] = 1
    else:
        degs[ab] += 1
    if(nakawaru not in degs.keys()):
        ans = ans*2%mod
    else:
        waru = pow(2,degs[nakawaru],mod)
        ans = (ans + ans*pow(waru,mod-2,mod)%mod)%mod
    
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18
SIZE = 3 * 10 ** 5

g1, g2, inv = [1, 1], [1, 1], [0, 1]
for i in range(2, SIZE + 1):
    g1.append((g1[-1] * i) % MOD)
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inv[-1]) % MOD)
    
def comb(n, r):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n - r] % MOD

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

cnt = defaultdict(int)
zero = 0
for a, b in AB:
    if a != 0 and b != 0:
        cnt[b / a] += 1
    else:
        zero += 1
#print(cnt)


answer = 1
rest = N

if zero >= 2:
    answer -= pow(2, zero, MOD) - 1 - zero
    answer %= MOD
rest -= zero

cnt2 = defaultdict(int)
for a, b in AB:
    if a != 0 and b != 0 and b / a > 0:
        if cnt[b / a] and cnt[- a / b] and cnt2[b / a] == 0:
            cnt2[b / a] = 1
            rest -= cnt[b / a] + cnt[- a / b]
            answer *= pow(2, cnt[b / a] + cnt[- a / b], MOD) - (pow(2, cnt[- a / b], MOD) - 1) * (pow(2, cnt[b / a], MOD) - 1) 
            answer %= MOD
answer *= pow(2, rest, MOD)
answer -= 1
answer %= MOD

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
MOD = 10**9+7
AB = []
x = 0
y = 0
d = defaultdict(int)
ch = defaultdict(int)
for _ in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        print(N)
        break
    elif a == 0:
        x += 1
        continue
    elif b == 0:
        y += 1
        continue
    else:
        c = a / b
        d[c] += 1
        AB.append(c)
n = len(AB)
ans = 1
for i in range(n):
    cc = AB[i]
    if ch[cc] != 0:
        continue
    m = d[cc]
    ccc = (-1)/cc
    l = d[ccc]
    ans *= (pow(2,m,MOD)+pow(2,l,MOD)-1)
    ch[cc] = 1
    ch[ccc] = 1
ans *= (pow(2,x,MOD)+pow(2,y,MOD)-1)
ans -= 1
ans = ans % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import collections

n = int(input())
mod = 10 * 6 + 7
c = []
d = []

tan = []
atan = []

for _ in range(n):
    a, b = map(int, input().split())
    if b == 0: tan.append(float('inf'))
    else: tan.append(a / b)
    if a == 0: atan.append(float('inf'))
    else: atan.append(- b / a)

tan = collections.Counter(tan)
atan = collections.Counter(atan)

for key, value in tan.items():
    print(key)
    if abs(key) > 1: continue
    if atan[key] > 0:
        c.append(value)
        d.append(value)

# print(c, d)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from fractions import gcd
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	AB = []
	D = defaultdict(int)
	DJ = defaultdict(int)
	d0x = 0
	dx0 = 0
	for i in range(N):
		A, B = getlist()
		if A == 0 and B == 0:
			pass
		elif A == 0:
			dx0 += 1
		elif B == 0:
			d0x += 1
		else:
			GCD = gcd(A, B)
			a = int(A // GCD)
			b = int(B // GCD)
			if a < 0:
				a = -a
				b = -b
			AB.append([a, b])
			D[a * (10 ** 19) + b] += 1
			DJ[a * (10 ** 19) + b] = 1


	ans = 1

	for a, b in AB:
		a2 = b; b2 = -a
		if a2 < 0:
			a2 = -a2; b2 = -b2
		if DJ[a * (10 ** 19) + b] >= 0 and DJ[a2 * (10 ** 19) + b2] >= 0:
			DJ[a * (10 ** 19) + b] = -1
			DJ[a2 * (10 ** 19) + b2] = -1
			X = D[a * (10 ** 19) + b]
			Y = D[a2 * (10 ** 19) + b2]
			ans *= pow(2, X, con) + pow(2, Y, con) - 1
			ans %= con

	ans *= (pow(2, d0x, con) + pow(2, dx0, con)) - 1
	ans %= con

	if ans == 0:
		print(10 **  + 6)
	else:
		print(ans - 1)

if __name__ == '__main__':
	main()

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:
        col.append((1,0))
        continue
    elif b == 0:
        row.append((1,0))
        continue
    else:
        g = gcd(abs(a), abs(b))
        a //= g
        b //= g

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

    if b > 0:
        col.append((a, b))
    elif 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
import itertools
count = int(input())
com = []
counter = 0
for j in range(count):
    com.append(input().split())
for i in itertools.combinations(com,r=2):
    counter += 1
    if int(i[0][0])*int(i[0][1]) + int(i[1][0])*int(i[1][1]) == 0:
        counter -= 1
print((counter + count)%1000000007)

Submission status: Wrong Answer

Solution code:
from math import gcd
mod = 10**9+7
n = int(input())
dicn = {}
dicp = {}
dicz = {'a': 0, 'b': 0, 'z': 0}
for i in range(n):
  a, b = map(int, input().split())
  if a == 0 and b == 0:
    dicz['z'] += 1
  else:
    g = gcd(a,b)
    a //= g
    b //= g
    if a < 0:
      a *= -1
      b *= -1
    elif a == 0 and b < 0:
      b *= -1
    if a * b > 0:
      if a in dicp:
        if b in dicp[a]:
          dicp[a][b] += 1
        else:
          dicp[a][b] = 1
      else:
        dicp[a] = {b: 1}
    elif a * b < 0:
      if b in dicn:
        if a in dicn[b]:
          dicn[b][a] += 1
        else:
          dicn[b][a] = 1
      else:
        dicn[b] = {a: 1}
    else:
      if a == 0:
        dicz['a'] += 1
      else:
        dicz['b'] += 1

ans = 1

for a in dicp:
  for b in dicp[a]:
    if -a in dicn:
      if b in dicn[-a]:
        ans *= (pow(2, dicp[a][b], mod) + pow(2, dicn[-a][b], mod) - 1)
        dicn[-a][b] = 0
      else:
        ans *= pow(2, dicp[a][b], mod)
    else:
      ans *= pow(2, dicp[a][b], mod)
    ans %= mod

for b in dicn:
  for a in dicn[b]:
    ans *= pow(2, dicn[b][a], mod)
    ans %= mod
    
if dicz['a'] > 0 and dicz['b'] > 0:
  ans *= pow(2,dicz['a'],mod) + pow(2,dicz['b'],mod) - 1
elif dicz['a'] > 0:
  ans *= pow(2,dicz['a'],mod)
elif dicz['b'] > 0:
  ans *= pow(2,dicz['b'],mod)
  
ans += pow(2,dicz['z'],mod) - 1
print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from math import gcd

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

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

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

Submission status: Wrong Answer

Solution code:
import os
from collections import Counter

import math
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

zeros_cnt = 0
A = []
B = []
for a, b in AB:
    if a == 0 or b == 0:
        zeros_cnt += 1
    else:
        if a < 0:
            a = -a
            b = -b
        g = math.gcd(a, b)
        A.append(a // g)
        B.append(b // g)

ab = [(a, b) for a, b in zip(A, B)]
ba = [(b, a) for a, b in zip(A, B)]

counts = Counter(ba)
ans = 1
nandemo = 0
seen = set()
for (a, b), cnt in Counter(ab).items():
    cc = counts[-a, b] + counts[a, -b]
    if cc == 0:
        nandemo += cnt
    else:
        if not ((a, -b) in seen or (-a, b) in seen):
            seen.add((b, a))
            ans *= pow(2, cnt, MOD) + pow(2, cc, MOD) - 1
            ans %= MOD
ans *= zeros_cnt + 1
ans %= MOD
ans *= pow(2, nandemo, MOD)
ans -= 1
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math

mod = 1000000007

N = int(input())
As = []
Ts = [] # <= 0
Ws = [] # > 0
e = 10 ** (-2)

for _ in range(N):
    a, b = map(int, input().split())
    s = (a**2 + b**2) ** (1/2)
    if a != 0:
        w = math.atan(b/a)
        if w > 0:
            Ws.append(w)
        else:
            Ts.append(w + math.pi / 2)
        As.append(w)
    else:
        w = math.pi / 2
        Ws.append(w)
        As.append(w)

Ts.sort()
Ws.sort()
As.sort()
l = 0
c = 0
Cs = []

Lt = len(Ts)
Lw = len(Ws)
it = 0
iw = 0
ct = 0
cw = 0
while l <= math.pi / 2:
    while it < Lt and l - e < Ts[it] and Ts[it] < l + e:
        ct += 1
        it += 1
    while iw < Lw and l - e < Ws[iw] and Ws[iw] < l + e:
        cw += 1
        iw += 1
    Cs.append((2**ct+2**cw-1)%mod)
    ct = 0
    cw = 0
    l += e
Cs.append((2**ct+2**cw-1)%mod)

counter = 1
for c in Cs:
    counter = (counter*c) % mod

print((counter - 1) % mod)

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:
        s = Fraction(ai, bi)
        if Fraction(ai, bi) not in resab:
            resab[s] = 1
        else:
            resab[s] += 1
        b = Fraction(-s.denominator, s.numerator)
        if b not in resba:
            resba[b] = 1
        else:
            resba[b] += 1
    else:
        if ai == 0 and bi == 0:
            res0 += 1
        elif ai == 0:
            res0a += 1
        elif bi == 0:
            res0b += 1

Submission status: Wrong Answer

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

mod = 10**9+7

N = int(input())
AB = []
Empty = 0
for _ in range(N):
    x, y = map(int, input().split())
    if x == 0 and y == 0:
        Empty += 1
    elif y < 0 or (y==0 and x < 0):
        AB.append((math.atan2(-y, -x), -x, -y))
    else:
        AB.append((math.atan2(y, x), x, y))

M = N-Empty
AB.sort()
ind1 = 0
ind2 = 0
ans = 1
while ind1 < M and AB[ind1][1] > 0:
    ind1 += 1
Checked = [False]*M
for i, (t, x, y) in enumerate(AB):
    if x <= 0: break
    if Checked[i]: continue
    just = False
    while ind1 < M:
        update = False
        t1, x1, y1 = AB[ind1]
        ind2 = ind1+1
        while ind2 < M and AB[ind2][1]*y1 == AB[ind2][2]*x1:
            ind2 += 1
        
        if x1*x + y1*y > 0:
            ans = (ans * pow(2, ind2-ind1, mod)) % mod
            ind1 = ind2
        else:
            just = (x1*x + y1*y == 0)
            break
        
    tmp = i
    while tmp < M and not Checked[tmp] and AB[tmp][1]*y == AB[tmp][2]*x:
        Checked[tmp] = True
        tmp += 1
    if just:
        ans = (ans * (pow(2, ind2-ind1, mod) + pow(2, tmp-i, mod) - 1)) % mod
        ind1 = ind2
    else:
        ans = (ans * (pow(2, tmp-i, mod))) % mod

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = {}
r = 0
for i in range(n):
    if a[i][0] == 0 and a[i][1]:
        r += 1
    elif a[i][0] == 0:
        if 0 in d:
            d[0][0] = d[0][0] +1
        else:
            d[0] = [1, 0]
    elif a[i][1] == 1:
        if 0 in d:
            d[0][1] = d[0][1] +1
        else:
            d[0] = [0, 1]
    else:
        if a[i][0] * a[i][1] > 0:
            s = a[i][0] / a[i][1]
            if s in d:
                d[s][0] = d[s][0] +1
            else:
                d[s] = [1, 0]
        else:
            s = -a[i][1] / a[i][0]
            if s in d:
                d[s][1] = d[s][1] +1
            else:
                d[s] = [0, 1]
ans = 1
m = 0
for i in d:
    m += 1
    ans *= 2**d[i][0] + 2**d[i][1] - 1
    if m != 1:
        ans -= 1
    print(ans)
    ans = ans%1000000007
ans += r
#print(d)
print(ans)

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[]
for i in range(n):
  l.append(list(map(int,input().split(" "))))

c=0
for i in range(n):
  for j in range(i+1,n):
    if l[i][0]*l[j][0]+l[i][1]*l[j][1]==0:
      c+=1
      
print(2**n-c)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7

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

p = []
zeroa = 0
zerob = 0
for a, b in AB :
  if a == 0 and b == 0 :
    continue
  elif a == 0 :
    zeroa += 1
    continue
  elif b == 0 :
    zerob += 1
    continue
    
  g = gcd(abs(a), abs(b))
  a //= g
  b //= g
  if a < 0 :
    a *= -1
    b *= -1
  p.append((a, b))

ret = 1
visited = set()
cnt = Counter(p)
for k, v in cnt.items() :
  a, b = k
  c, d = b, -a
  if c < 0 :
    c *= -1
    d *= -1
  if cnt[(c, d)] == 0 :
    ret *= pow(2, v, mod)
  else :
    if not (c, d) in visited :
      u = cnt[(c, d)]
      ret *= (pow(2, u, mod) + pow(2, v, mod) - 1)
      visited.add((a, b))
      visited.add((c, d))
  ret %= mod

ret *= pow(2, zeroa, mod) + pow(2, zerob, mod) - 1
ret %= mod

print((ret - 1) % mod)

Submission status: Wrong Answer

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

mod = 1000000007
eps = 0.0000001

n = int(input())

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

res = 1
used = [False]*n


rest = n

for i in range(n):
    e,idx = ang[i]
    if used[idx]:
        continue
    used[idx] = True
    if e > eps:
        break
    
    cnt = 1
    k = i + 1
    while k < n:
        if abs(e-ang[k][0]) <= eps:
            p = ang[k][1]
            if (not used[p] ) and ab[p][0]*ab[idx][1] == ab[p][1]*ab[idx][0]:
                cnt += 1
                used[p] = True
            k += 1
        else:
            break


    cnt2 = 0

    ok = n
    ng = i+1
    while ok-ng > 1:
        mid = (ok+ng)//2
        if ang[mid][0] >= e+90-eps:
            ok = mid
        else:
            ng = mid

    k = ok
    while k < n:
        if abs(e+90-ang[k][0]) <= eps:
            p = ang[k][1]
            if (not used[p]) and ab[p][0]*ab[idx][0] + ab[p][1]*ab[idx][1] == 0:
                cnt2 += 1
                used[p] = True
            k += 1
        else:
            break

    if cnt2 != 0:
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
        rest -= (cnt+cnt2)

rest = max(rest,0)
res = res*pow(2,rest,mod)%mod - 1
print(res%mod)

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
c = [[]]*n
ans = 0
for i in range(n):
  c[i] = list(map(int, input().split()))

for i in range(1, n):
  aa = list(itertools.combinations(c, i))
  for com in aa:
    for tmp in com:
      if [tmp[1] * -1, tmp[0]] in com:
        break
      if [tmp[1], -1 * tmp[0]] in com:
        break
    else:
      ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

oN = 0
No = 0
AB = []
ABlen = 0
Bad = []
d = {}

for i in range(N):
  A,B = map(int, input().split())
  if A == 0 and B == 0:
    continue
  elif A == 0:
    oN += 1
  elif B == 0:
    No += 1
  else:
    AB.append([A,B])
    ABlen += 1  
    if -B/A in d.values():
      for k, v in d.items():
        if -B/A == v:
          Bad.append([k+1,i+1])
  
    d[i] = A/B


C = 2**(ABlen-len(Bad))


ans = C + C*(2**oN-1) + C*(2**No-1)
print(ans)