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:
class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD

    def combination2(self, k, r):
        """kCrを求める O(r) kが大きいが、r <= nを満たしているときに使用"""
        if k < r:
            return 0
        res = 1
        for l in range(r):
            res *= (k - l)
            res %= self.MOD
        return (res * self.inv_fact[r]) % self.MOD


def compress(string):
    string.append(-2)
    n = len(string)
    begin, end, cnt = 0, 1, 1
    ans = []
    while end < n:
        if string[begin] == string[end]:
            end, cnt = end + 1, cnt + 1
        else:
            ans.append((string[begin], cnt))
            begin, end, cnt = end, end + 1, 1
    return ans

  
from collections import defaultdict


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
MOD = 10 ** 9 + 7
comb = Combination(10 ** 6, MOD)
res1 = []
res2 = []
ind = []
cnt_00 = 0
cnt_a0 = 0
cnt_b0 = 0
for i in range(n):
    a, b = info[i]
    if a == 0 and b == 0:
        cnt_00 += 1
        continue
    if a == 0:
        cnt_a0 += 1
        continue
    if b == 0:
        cnt_b0 += 1
        continue
    res1.append(a / b)
    res2.append(- b / a)
    ind.append(i)

memo_r = defaultdict(int)
memo_l = defaultdict(int)

for i in range(len(res1)):
    l, r = res1[i], res2[i]
    memo_r[r] += 1
    memo_l[l] += 1

ans = 1
used = set()
for r in memo_r:
    if r in used:
        continue
    cnt_r = memo_r[r]
    cnt_l = 0
    if r in memo_l:
        cnt_l += memo_l[r]
    if r == -1.0 or r == 1.0:
        tmp = cnt_l + cnt_r + 1
    else:
        tmp = (pow(2, cnt_l, MOD) - 1) + (pow(2, cnt_r, MOD) - 1) + 1
    ans *= tmp
    used.add(-1 / r)

ans = ans + ans * cnt_a0 + ans * cnt_b0  + cnt_b0 * cnt_a0 * ans
print((ans - 1) % MOD)

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()
        m = gcd(a,b)
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                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
    if dic['0 0']:
        ans *= (dic['0 0']+1)
        ans %= mod
    if dic['1 0'] and dic['0 1']:
        ans *= (pow(2,dic['1 0'],mod)+pow(2,dic['0 1'],mod)-1)
        ans %= mod
    elif dic['1 0']:
        ans *= pow(2,dic['1 0'],mod)
        ans %= mod
    elif dic['0 1']:
        ans *= pow(2,dic['0 1'],mod)
        ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD=1000000007
import sys 
input=sys.stdin.readline 
from collections import defaultdict 
d=defaultdict(int)

def main():
    n=int(input())
    Az=0
    Bz=0
    
    hoka=0
    cntA=cntB=0;cntH=0
    for i in range(n):
        a,b=map(int,input().split())
        if a==0:
            if b==0:
                continue 
            else:
                
                Az+=1
                cntA+=cntH+cntA+1
                
                cntA%=MOD
                continue
        if b==0:
            if a==0:
                continue 
            else:
                Bz+=1
                cntB+=cntB+cntH+1
                cntB%=MOD
                continue
        else:
            
            d[-a/b]+=1
            use=d[b/a]
            cntH+=pow(2,hoka-use,MOD)
            cntH%=MOD
            hoka+=1

    print((cntA+cntB+cntH)%MOD)
    #print(cntA,cntB,cntH)
    #print(d)
    
main()

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 1000000007

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


def f(v, k, L, K, A):
    p = v[0]
    t = -1 / k
    if t in K:
        return t

    i = bisect.bisect_right(L, t)
    if i != len(L):
        q = K[L[i]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i]

    if i + 1 < len(L):
        q = K[L[i + 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i + 1]
    
    if i > 0:
        q = K[L[i - 1]][0]
        if A[p][0] * A[q][0] + A[p][1] * A[q][1] == 0:
            return L[i - 1]

    return t


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

    K = {}
    zero = 0
    for i, a in enumerate(A):
        if a == [0, 0]:
            zero += 1
            continue

        if a[0] == 0:
            r = 10 ** 20
        else:
            r = a[1] / a[0]
        K.setdefault(r, []).append(i)

    L = sorted(list(K.keys()))    

    S = set()
    res = 1
    for k, v in K.items():
        if k in S:
            continue
        S.add(k)

        if k == 0:
            t = 10 ** 20
        elif k == 10 ** 20:
            t = 0
        else:
            t = f(v, k, L, K, A)

        if t in K:
            S.add(t)
            v2 = K[t]
            res *= (pow(2, len(v), mod) + pow(2, len(v2), mod) - 1)
            res %= mod
        else:
            res *= 2
            res %= mod

    if zero > 0:
        res += zero

    print((res - 1) % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

mod = 1000000007

from fractions import gcd

ratios = []
for a, b in ab:
    if a != 0 and b != 0:
        g = gcd(a, b)
        ratios.append((a // g, b // g))
    elif a == 0 and b == 0:
        ratios.append((0, 0))
    elif a == 0:
        ratios.append((0, 1))
    else:
        ratios.append((1, 0))


from collections import Counter, defaultdict
c = Counter(ratios)
seen = Counter()

targets = []
for key in c:
    x, y = key
    xx = c[key]
    yy = seen[(-y, x)] + seen[(y, -x)]
    if xx != 0 and yy != 0:
        targets.append((xx, yy))
    seen[key] = c[key]

n_frees = 0
for i, (x, y) in enumerate(ratios):
    n_bads = c[(-y, x)] + c[(y, -x)]
    if n_bads == 0:
        n_frees += 1

ans = (2 ** n_frees) % mod

for x, y in targets:
    tmp = (2 ** x) + (2 ** y) - 1
    # print(tmp)
    tmp %= mod
    ans *= tmp

print(ans  - 1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    d=dict()
    m=10**18+100
    for i in range(N):
        A, B = map(int, input().split())
        if A==0 and B==0:
            d[-m]=d.get(-m,0)+1
        elif B==0:
            d[m]=d.get(m,0)+1
        elif A==0:
            d[0]=d.get(0,0)+1
        else:
            sa=sb=1
            if A<0:
                sa=-1
                A*=-1
            if B<0:
                sb=-1
                B*=-1

            g=math.gcd(A,B)
            A=A//g
            B=B//g
            if sa==-1 and sb==-1:
                t=(A,B)
            elif sb==-1:
                t=(-A,B)
            else:
                t=(sa*A,sb*B)
            d[t]=d.get(t,0)+1
    
        
    #print(d)
    ks=set(d.keys())
    alis=[]
    tot=1
    for i, k in enumerate(ks):
        if d[k]==-1.0:
            continue
        if k==-m:
            continue
        if k==m:
            ik=0
        elif k==0.0:    
            ik=m
        elif k[0]<0:
            ik=(k[1],-k[0])
        else:
            ik=(-k[1],k[0])
        print(ik)
        if ik in ks:
            d1,d2=d[k],d[ik]
            tot=(tot*((pow(2,d1,mod)-1)+(pow(2,d2,mod)-1)+1)%mod)%mod
            d[ik]=-1

        else:
            tot=(tot*pow(2,d[k],mod))%mod

    tot-=1
    tot+=d.get(-m,0)%mod
    tot%=mod
    
    print(tot)




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)%1000000007)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
info = []
for i in range(N):
	a, b = rl()
	info.append((a, b))

import collections

h = collections.defaultdict(int)
for a, b in info:
	if a == 0 and b == 0:
		continue
	elif a == 0:
		h[0] += 1
	elif b == 0:
		h[float('inf')] += 1
	else:
		h[a/b] += 1
ans = 1
visited = {}
for r, c in h.items():
	if r in visited:
		continue
	rr = None
	if r == 0:
		rr = float('inf')
	elif r == float('inf'):
		rr = 0
	else:
		rr = -1/r
	if rr in h:
		cnt = pow(2, c, mod)-1 + pow(2, h[rr], mod)-1 + 1
		ans = (ans * cnt) % mod
		visited[rr] = 1
	else:
		ans = (ans * 2) % mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
N = int(input())
K = [tuple(map(int, input().split())) for _ in range(N)]
count = 0
for i in range(N):
    for j in range(i, N):
        if (K[i][0] * K[j][0]) + (K[i][1] * K[j][1]) == 0:
            break
        else:
            count += 1

print(count)

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
        else:
            if x > 0: x=1
            if y > 0: y=1
            if x < 0: x=-1
            if y < 0: y=-1
        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;
        else:
            if px > 0: px = 1
            if px < 0: px = -1
            if py > 0: py = 1
            if py < 0: py = -1
        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:
from collections import defaultdict
from math import atan2

N = int(input())
MOD = 1000000007

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

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

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

ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
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(2**degs[nakawaru],mod-2,mod)%mod)%mod
    
print(ans-1)

Submission status: Wrong Answer

Solution code:
def main():
    from math import gcd
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*n]
    adb = dict()
    ans = 0
    mod = 10**9+7
    for a, b in ab:
        if a == b == 0:
            ans += 1
            continue
        if b != 0:
            g = gcd(a, b)
            a = a//g
            b = b//g
            if b < 0:
                a *= -1
                b *= -1
            if a == 0:
                b = 1
            adb[(a, b)] = adb.get((a, b), 0)+1
        else:
            adb[None] = adb.get(None, 0)+1
    ans2 = 1
    for i, j in adb.items():
        if i is None:
            k = (0, 1)
        elif i == (1, 0):
            k = None
        else:
            if i[0] < 0:
                k = (i[1], -i[0])
            else:
                k = (-i[1], i[0])
        if k not in adb:
            ans2 = ans2*pow(2, j, mod) % mod
        else:
            if i is None:
                continue
            if i[0] >= 0:
                ans2 = ans2*(pow(2, j, mod)+pow(2, adb[k], mod)-1) % mod
    ans2 = (ans2-1) % mod
    print((ans+ans2) % mod)


main()

Submission status: Wrong Answer

Solution code:
import bisect,sys
input = sys.stdin.readline
n=int(input())
ans=[0]*n
ans[0]=2
ans[-1]=1
mod=10**9+7
l=[0]*n
d={}
for i in range(n):
  a,b=map(float,input().split())
  if b==0:
    l[i]=0
  else:
    l[i]=a/b
l.sort()
z=bisect.bisect_right(l,0)
for i in range(1,z):
  ans[i]=(ans[i-1]*2)%mod
for i in range(z,n) :
  x=l[i]
  le=bisect.bisect_left(l,-1/x)
  r=bisect.bisect_right(l,-1/x)
  if le==r:
    ans[i]=(ans[i-1]*2)%mod
  else:
    z=bisect.bisect_left(l,x)   
    if i==z:
      ans[i]=ans[i-1]+2**(i-(r-le))
    else:
      ans[i]=ans[i-1]+ans[z]//2
print((ans[-1]-1)%mod)

Submission status: Wrong Answer

Solution code:
import collections

def getGreatestCommonDivisor(x, y):
    if x < y:
        x, y = y, x
    if y == 0:
        return x
    return getGreatestCommonDivisor(y, x % y)


N = int(input())
fishes = []
for _ in range(N):
    fishes.append([int(s) for s in input().split()])

# fishes = [
#           (3, 2),
# (3, 2),
# (-1 ,1),
# (2 ,-1),
# (-3 ,-9),
# (-8 ,12),
# (7 ,7),
# (8, 1),
# (8 ,2),
# (8, 4),
# ]

# fishes = [
#           (3, 0),
#           (0, 0),
# ]


slopeCount = collections.defaultdict(int)
for x, y in fishes:
    gcl = getGreatestCommonDivisor(abs(x), abs(y))
    if gcl != 0:
        x //= gcl
        y //= gcl
    if x < 0:
        x = -x
        y = -y
    slopeCount[(x, y)] += 1

# print(slopeCount)

reversedPairs = dict()
independentCount = 0
zeroCount = 0
for slope, count in slopeCount.items():
    x, y = slope
    rx, ry = (y, -x) if y >= 0 else (-y, x)
    if (x, y) == (0, 0):
        zeroCount += count
        continue
    if (x, y) in reversedPairs or (rx, ry) in reversedPairs:
        continue
    if (rx, ry) not in slopeCount:
        independentCount += count
        continue
    reversedPairs[(x, y)] = (count, slopeCount[(rx, ry)])
    

# print(reversedPairs, independentCount)

M = 1000000007
def subsetNum(count):
    r = 1
    for _ in range(count):
        r *= 2
        r %= M
    return r

result = subsetNum(independentCount)
for c1, c2 in reversedPairs.values():
    result *= (subsetNum(c1) - 1 + subsetNum(c2) - 1 + 1)
    result %= M
if zeroCount > 0:
    result += zeroCount
result -= 1
result %= M
print(result)

Submission status: Wrong Answer

Solution code:
import math
N=int(input())
A=[0]*N
B=[0]*N
x=0
y=0
plus={}
ans=1
for i in range(N):
  a,b=map(int,input().split())
  A[i]=a
  B[i]=b
  if(a==0 and b!=0):
    x+=1
  elif(a!=0 and b==0):
    y+=1
  elif(a!=0 and b!=0):
    c=math.gcd(a**2-b**2,a*b)
    d=(a**2-b**2)//c
    e=(a*b)//c
    if(e<0):
      d*=-1
      e*=-1
    #print(d)
    #print(e)
    if((d,e) in plus):
      plus[(d,e)]+=1
    else:
      plus[(d,e)]=1
#print(plus)
#print(x)
#print(y)
for z in plus.values():
  ans*=(z+1)
ans*=(2**x+2**y-1)
print(ans-1)

Submission status: Wrong Answer

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

zerozero = 0
somezero = 0
zerosome = 0
plus = []
minus = []
for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zerozero += 1
    elif a == 0:
        zerosome += 1
    elif b == 0:
        somezero += 1
    elif (a > 0 and b > 0) or (a < 0 and b < 0):
        plus.append(a/b)
    else:
        minus.append(-b/a)
plus.sort()
minus.sort()

ans = pow(2, zerozero, mod)
ans *= pow(2, zerosome, mod) + pow(2, somezero, mod) - 1

i = 0
j = 0
while i < len(plus) and j < len(minus):
    ni = plus[i]
    nj = minus[j]
    if plus[i] < minus[j]:
        i += 1
        ans *= 2
        ans %= mod
        continue
    elif minus[j] < plus[i]:
        j += 1
        ans *= 2
        ans %= mod
        continue

    nump = 0
    numm = 0
    while i < len(plus) and plus[i] == ni:
        i += 1
        nump += 1
    while j < len(minus) and minus[j] == nj:
        j += 1
        numm += 1
    ans *= pow(2, nump, mod) + pow(2, numm, mod) - 1
    ans %= mod

ans *= pow(2, len(plus) - i, mod)
ans *= pow(2, len(minus) - j, mod)

print(ans - 1)

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)

    nisyuni = abtheta*2

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

        # 90度の関係にあるもの
        while end <= N+i:
            ai, bi = nisyuni[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 = nisyuni[end]

        if end2 == None:
            end2 = end

        # 270度の関係にあるもの
        while end2 <= N+i:
            ai, bi = nisyuni[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 = nisyuni[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:
from fractions import Fraction
n=int(input())

zero=0
plus=[]
minus=[]

for i in range(n):
    a,b=map(int,input().split())
    if(a*b>0):
        plus.append(Fraction(a,b))
    elif(a*b<0):
        minus.append(Fraction(-b,a))
    else:
        if(a==0 and b==0):
            zero+=1
        elif(a==0):
            plus.append(Fraction(0,1))
        else:
            minus.append(Fraction(0,1))

plus.sort()
minus.sort()

kazu=n-zero

pl=len(plus)
ml=len(minus)
#print(kazu)
#print(plus)
#print(minus)

kyoutu=list(set(plus) & set(minus))
kyoutu.sort()


tyohuku=[[0,0]for i in range(len(kyoutu))]

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,pl):
        #print(plus[j])
        
        if(plus[j]==kyoutu[i]):
            tyohuku[i][0]+=1
        elif(plus[j]>kyoutu[i]):
            break
        start+=1

gen=0
start=0
for i in range(len(kyoutu)):
    #print("check",kyoutu[i],start)
    gen=start
    for j in range(gen,ml):
        #print(minus[j])
        
        if(minus[j]==kyoutu[i]):
            tyohuku[i][1]+=1
        elif(minus[j]>kyoutu[i]):
            break
        start+=1

#print(tyohuku)

oks=[0]*len(kyoutu)

ruijo=[]

sosu=1000000007
temp=1
for i in range(n+1):
    ruijo.append(temp)
    temp*=2
    temp%=sosu

#print(ruijo)

nokori=kazu

for i in range(len(kyoutu)):
    nokori-=tyohuku[i][0]+tyohuku[i][1]
    oks[i]=ruijo[tyohuku[i][0]]+ruijo[tyohuku[i][1]]-1
    oks[i]%=sosu

ans=ruijo[nokori]

for o in oks:
    ans*=o
    ans%=sosu

ans-=1
ans%=sosu
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
l1 = []
l2 = []
s = 0
for _ in range(n):
    a,b = map(int,input().split())
    l1.append(a)
    l2.append(b)
for i in range(n):
        s += 1
for k in range(n):
    for j in range(n):
        if k<j and (int(l1[k])*int(l1[j]) + int(l2[k])*int(l2[j]) != 0):
                    s += 1
print(s%1000000007)

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()
        m = gcd(a,b)
        if a != 0 and b == 0:
            a = 1
        elif a == 0 and b != 0:
            b = 1
        else:
            if not (a==0 and b==0):
                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 = 1
    if dic['0 0']:
        ans *= (dic['0 0']+1)
        ans %= mod
    if dic['1 0'] and dic['0 1']:
        num *= (pow(2,dic['1 0'],mod)+pow(2,dic['0 1'],mod)-1)
        num %= mod
    elif dic['1 0']:
        num *= pow(2,dic['1 0'],mod)
        num %= mod
    elif dic['0 1']:
        num *= pow(2,dic['0 1'],mod)
        num %= mod
    if num != 0:
        ans *= num
        ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import itertools

n = int(input())
c = [[]]*n
ans = n
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:
      print(tmp)
      if [tmp[1] * -1, tmp[0]] in com:
        break
      if [tmp[1], -1 * tmp[0]] in com:
        break
    else:
      ans+=len(com)
      break

print(ans)