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 defaultdict
import bisect
N=int(input())
L = [list(map(int,input().split())) for _ in range(N)]

MOD=10**9+7

L_non_zero=[[a,b] for a,b in L if a*b!=0]
L_zero=[[a,b] for a,b in L if a*b==0]

L_zero=0
D_AB=defaultdict(int)
D_BA=defaultdict(int)

for a,b in L:
    if a*b==0:
        L_zero+=1
    else:
        D_AB[a/b]+=1
        D_BA[b/a]+=1


ans=1
used_key=set()
for key,val in D_AB.items():
    if key in used_key:
        continue
    else:
        used_key.add(-1/key)
    val_other=D_BA[-key]

    if val_other==0:
        ans*=pow(2,val,MOD)
    else:
        ans*=((pow(2,val,MOD)-1)+(pow(2,val_other,MOD)-1)+1)
if L_zero>0:
    ans*=(L_zero+1)
print((ans-1+MOD)%MOD)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import Counter
MOD = pow(10,9)+7
N = int(input())
count_zero = [0,0,0]
A = []
B = []
C = []
D = []
for i in range(N):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        count_zero[0] += 1
    elif a == 0:
        count_zero[1] += 1
    elif b == 0:
        count_zero[2] += 1
    elif a > 0 and b > 0:
        A.append([a,b])
    elif a > 0 and b < 0:
        B.append([a,b])
    elif a < 0 and b > 0:
        C.append([a,b])
    else:
        D.append([a,b])

A = Counter([str(a[0])+","+str(a[1]) for a in A]).items()
B.sort()
C.sort()
NA,NB,NC,ND = len(A),len(B),len(C),len(D)

ans = count_zero[0]

ans1 = count_zero[1] + count_zero[2]

ans2 = 1
for a in A:
    cnt = 0
    x,c = a
    x = list(map(int,x.split(",")))
    x = [x[1],-x[0]]
    b = bisect_left(B,x)
    for i in range(b,NB):
        if x == B[i]:
            cnt += 1
        else:
            break
    x = [-x[0],-x[1]]
    c = bisect_left(C,x)
    for i in range(c,NC):
        if x == C[i]:
            cnt += 1
        else:
            break
    k = pow(2,c+cnt,MOD) - (pow(2,c,MOD)-1) * (pow(2,cnt,MOD)-1)
    ans2 = (ans2*k)%MOD
print((ans+ans1*ans2*pow(2,NC,MOD))%MOD)

Submission status: Wrong Answer

Solution code:
N = int(input())
AB = []
A0 = 0
B0 = 0
A0B0 = 0
for i in range(N):
    Atmp,Btmp = list(map(int,input().split()))
    if (Atmp!=0)and(Btmp!=0):
        AB.append(Atmp/Btmp)
    elif (Atmp==0)and(Btmp==0):
        A0B0 += 1
    elif (Atmp==0)and(Btmp!=0):
        A0 += 1
    elif (Atmp!=0)and(Btmp==0):
        B0 += 1

N += -1*A0B0

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
import math
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])

kaburi.append([A0,B0])
forsum.append(A0+B0)

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 math
MOD = 1000000007
N = int(input())
d_p = dict()
d_m = dict()
for n in range(N):
    a,b = map(int,input().split())

    if a==0 and b==0:
        d_m['00'] = 1
        continue
    if a==0:
        n_sign = 0
    elif b==0:
        n_sign = 1
    
    else:    
        n_sign = ((a<0) + (b<0))%2
        a = abs(a)
        b = abs(b)
        # gcd = math.gcd(a,b)
        # a//=gcd
        # b//=gcd
        

        #print(n_sign,a,b)
    # print(n_sign,a,b)


    if n_sign==1:
        s =str(b/a)
        d_m[s] = d_m.get(s,0) + 1
    elif n_sign==0:
        s =str(a/b)
        d_p[s] = d_p.get(s,0) + 1      
    


ans = 1
for k,v in d_m.items():
    if k in d_p:
        ans *= (2**v + 2**d_p[k] - 1)
        
        d_p.pop(k)
    else:
        ans *= 2**v
    ans %= MOD

for k,v in d_p.items():
    ans *= 2**v
    ans %= MOD
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 = {}

a_zero_cnt = 0
b_zero_cnt = 0
ab_zero_cnt = 0

for i in range(n):
    a, b = map(int, input().split()) 
    if a==0 and b!=0:
        a_zero_cnt += 1
    elif  a!=0 and b==0:
        b_zero_cnt += 1
    elif a == 0 and b == 0:
        ab_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:
        done_list.add(comp_pair1)
        pair_cnt.append((v,a_b_d[comp_pair1]))
    elif comp_pair2 in a_b_d:
        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

zero_m = max(pow_k(2,a_zero_cnt) + pow_k(2,b_zero_cnt) + ab_zero_cnt, 1)
ans *= zero_m
ans -= 1
print(ans%MOD)

Submission status: Wrong Answer

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

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

for a, b in pos:
    if b != 0:
        g = gcd(a, b)
    else:
        g = a
    d[(a // g, b // g)][0] += 1
for a, b in neg:
    a, b = -b, a
    if b != 0:
        g = gcd(a, b)
    else:
        g = a
    d[(a // g, b // g)][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
ans %= MOD
print(ans)
pass

Submission status: Wrong Answer

Solution code:
import math
import sys
input = sys.stdin.readline
n = int(input())
x = [[0,0] for _ in range(n)]
h = 36000
c = 0
y = [[] for _ in range(h)]
mod = 10**9+7
c1 = 0
c2 = 0
for i in range(n):
  ai,bi = map(int,input().split())
  if ai == 0 and bi == 0:
    c += 1
  elif ai == 0:
    c1 += 1
  elif bi == 0:
    c2 += 1
  else:
    j = int((math.degrees(math.atan2(ai, bi))+180)*100)%36000
    flag = True
    for ca in y[j]:
      if ai*ca[0][1] == bi*ca[0][0]:
        x[ca[1]][0] += 1
        flag = False
        break
    for ca in y[(j+18000)%h]:
      if ai*ca[0][1] == bi*ca[0][0]:
        x[ca[1]][0] += 1
        flag = False
        break
    for ca in y[(j+9000)%h]:
      if ai*ca[0][0]+bi*ca[0][1] == 0:
        x[ca[1]][1] += 1
        flag = False
        break
    for ca in y[(j-9000)%h]:
      if ai*ca[0][0]+bi*ca[0][1] == 0:
        x[ca[1]][1] += 1
        flag = False
        break
    if flag:
      y[j].append([(ai,bi),i])
      x[i][0] = 1
ans = 1
ans =(2**c1 + 2**c2 -1)%mod
for xi in x:
  if xi[0] == 0:
    if xi[1] != 0:
      ans = (ans*2**(xi[1]))%mod
  else:
    if xi[1] == 0:
      ans = (ans*2**(xi[0]))%mod
    else:
      ans = (ans*(2**(xi[0])+2**(xi[1])-1))%mod
ans = (ans+c-1)%mod
print(ans)

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]))
        cur = (0,0)
        gg = math.gcd(abs(A[i]), abs(B[i]))
        if (A[i] > 0 and B[i] >= 0) or (A[i] < 0 and B[i] <= 0):
            normalRad = (A[i]//gg,B[i]//gg)
            if normalRad[1] < 0:
                normalRad = (-normalRad[0], -normalRad[1])
            if normalRad in fishRads:
                cur = fishRads[normalRad]
            fishRads[normalRad] = (cur[0]+1,cur[1])
        else:
            rotRad = (-B[i] // gg, A[i] // gg)
            if rotRad[1] < 0:
                rotRad = (-rotRad[0],-rotRad[1])
            if rotRad in fishRads:
                cur = fishRads[rotRad]
            fishRads[rotRad] = (cur[0], cur[1]+1)
    current = 1
    # print(fishRads)
    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:
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
    if num != 0:
        ans *= num
        ans %= mod
    print(ans-1)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(4000)
import math
N = int(input())
mod = 10**9+7
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:
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:
        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 + cnt_00
print((ans - 1) % MOD)

Submission status: Wrong Answer

Solution code:
import numpy as np
N=int(input())
a=[]
i=0
for i in range(N):
    A,B=input().split()
    A=int(A)
    B=int(B)
    c=[A,B]
    a.append(c)
j=0
d=[]
sumA=0
for j in range(0,N):
    k=j+1
    l=N-j-1
    S=0
    m=np.array(a[j])
    if l>0:
        for k in range(j+1,N):
            n=np.array(a[k])
            product=np.dot(m,n)
            if product==0:
                o=0
                l=l-1
                if j>=1:
                    for o in range(0,j):
                        p=np.array(a[o])
                        pro=np.dot(n,p)
                        e=d[o]
                        if pro>0:
                            S=S+(2**(N-o-e-3))
                        if pro<0:
                            S=S+(2**(N-o-e-3))
                        o+=1
            k+=1
    sumA=sumA+(2**l)-S
    d.append(l)
    j+=1
sumA=sumA%1000000007
print(sumA)

Submission status: Wrong Answer

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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
mod = 1000000007

adivb = [-float('inf') if ab[i][1] == 0 else ab[i][0] / ab[i][1]
         for i in range(n)]
bdiva = [-float('inf') if ab[i][0] == 0 else -ab[i][1] / ab[i][0]
         for i in range(n)]

adb, bda = Counter(adivb), Counter(bdiva)
cntadb, cnt = defaultdict(int), 0
for i in adb:
    if (i in bda) and (i >= 0):
        cntadb[i] += bda[i] + adb[i] +1
        cnt += bda[i] + adb[i]
ans = 1
for i in cntadb:
    ans *= cntadb[i]
print(ans*2**(n-cnt)-1)

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)
ret %= mod

print((ret - 1) % mod)

Submission status: Wrong Answer

Solution code:
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
N=int(input())
A=[0]
L={}

for i in range(N):
    B=list(map(int, input().split()))
    A.append(B)
    key=A[i+1][0]*A[i+1][1]
    val=L.get(key,0)
    if val!=0:
      x=L[key]
      x+=1
      L[key]=x
    else:
      L[key]=1

n=0
all=0

for i in range(1,N):
  all+=comb(N,i)%1000000007

for k in L:
  key2=k
  key3=-1*k
  if L.get(key3,0)!=0:
    n+=(L.get(key2)*L.get(key3))/2%1000000007
  
print(int((all-n)%1000000007))

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
if ans == 0:
    print(1)
    exit()
ans = (ans-1)%mod

print(ans)

Submission status: Wrong Answer

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

mod = 10**9 + 7
N = int(input())
cnt = {}
a_zero_cnt = 0
b_zero_cnt = 0
for _ in range(N):
    A, B = map(int, input().split())
    if A == B == 0:
        continue
    if A == 0:
        a_zero_cnt += 1
        continue
    if B == 0:
        b_zero_cnt += 1
        continue
    neg = False
    if A < 0:
        neg ^= True
        A *= -1
    if B < 0:
        neg ^= True
        B *= -1
    g = gcd(A, B)
    sign = -1 if neg else 1
    A //= g
    B //= g
    frac = (-sign * A, B)
    if frac not in cnt:
        cnt[frac] = 0
    cnt[frac] += 1
ans = 1
used = set()
for frac, c in cnt.items():
    if frac in used:
        continue
    A, B = frac
    sign = 1
    if A < 0:
        A *= -1
        sign = -1
    bad = (B * -sign, A)
    if bad in cnt:
        b = cnt[bad]
        ans = ans * (pow(2, c, mod) + pow(2, b, mod) - 1) % mod
        used.add(bad)
    else:
        ans = ans * 2 % mod
ans = ans * pow(2, a_zero_cnt, mod) % mod
ans = ans * pow(2, b_zero_cnt, mod) % mod
print((ans - 1) % mod)

Submission status: Wrong Answer

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

mod=10**9+7
n=int(input())
fact=[1]
revfact=[1]
for i in range(1,2*10**5+1):
  fact.append((fact[-1]*i)%mod)
  revfact.append(pow(fact[-1],mod-2,mod))
dic={}
cnt=0
for _ in range(n):
  a,b=map(int,input().split())
  if a!=0 and b!=0:
    g=gcd(abs(a),abs(b))
    if a*b>0:
      if (a//g,b//g) not in dic:
        dic[(a//g,b//g)]=1
      else:
        dic[(a//g,b//g)]+=1
    else:
      if (-abs(a)//g,abs(b)//g) not in dic:
        dic[(-abs(a)//g,abs(b)//g)]=1
      else:
        dic[(-abs(a)//g,abs(b)//g)]=1
  else:
    if a==0 and b==0:
      cnt+=1
    elif a==0:
      if (1,0) not in dic:
        dic[(1,0)]=1
      else:
        dic[(1,0)]+=1
    elif b==0:
      if (0,1) not in dic:
        dic[(0,1)]=1
      else:
        dic[(0,1)]+=1
ans=1
s=set()
for a,b in dic.keys():
  if (a,b) in s:
    continue
  s.add((a,b))
  if a>0:
    if (-b,a) in dic:
      s.add((-b,a))
      cnt1=dic[(a,b)]
      cnt2=dic[(-b,a)]
      tmp=1
      for i in range(1,cnt1+1):
        tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
      for i in range(1,cnt2+1):
        tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
      ans*=tmp
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
  elif a<0:
    if (b,-a) in dic:
      s.add((b,-a))
      cnt1=dic[(a,b)]
      cnt2=dic[(b,-a)]
      tmp=1
      for i in range(1,cnt1+1):
        tmp+=(fact[cnt1]*revfact[i]*revfact[cnt1-i])%mod
      for i in range(1,cnt2+1):
        tmp+=(fact[cnt2]*revfact[i]*revfact[cnt2-i])%mod
      ans*=tmp
      ans%=mod
    else:
      ans*=pow(2,dic[(a,b)])
      ans%=mod
print(ans+cnt-1)

Submission status: Wrong Answer

Solution code:
import math
import itertools

n = int(input())

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

    key = (0, 0)
    if a * b < 0:
        key = (abs(b), abs(a))
    else:
        key = (abs(a), abs(b))

    if key not in vectors:
        vectors[key] = [i]
    else:
        vectors[key].append(i)

mod = 1000000007
# total = (pow(2, len(vectors)) - 1) % mod

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

total = 1
for vec in vectors.values():

    comb = (combinations_count(len(vec), 2) if len(vec) >= 2 else 0)
    total *= (2+comb) % mod

print(total- 1)

Submission status: Wrong Answer

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

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

def main():
    mod=10**9
    N=I()
    from math import gcd
    d={}
    for i in range(N):
        a,b=MI()
        if (a,b)!=(0,0):
            g=gcd(abs(a),abs(b))
            a=a//g
            b=b//g
        if (a,b) in d:
            d[(a,b)]+=1
        else:
            d[(a,b)]=1
        
    ans=1
    L=[]
    for k in d.keys():
        L.append((k,d[k]))

    L2=[0,0,0,0]

    for i in range(len(L)):
        k=L[i][0]
        v=d[k]
        d[k]=0
        temp=pow(2,v)
        a,b=k
        if a*b!=0:
            if (-b,a) in d:
                v2=d[(-b,a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(-b,a)]=0
            if (b,-a) in d:
                v2=d[(b,-a)]
                if v2!=0:
                    temp+=pow(2,v2)-1
                    d[(b,-a)]=0
            ans=(ans*temp)%mod
                    
        if (a,b)==(0,1):
            L2[0]=v
        elif (a,b)==(0,-1):
            L2[1]=v
        elif (a,b)==(1,0):
            L2[2]=v
        elif (a,b)==(-1,0):
            L2[3]=v
        
        
    temp2=0
    for i in range(2):
        if L2[i]!=0:
            temp2+=L2[i]
    
            
    temp3=0
    for i in range(2,4):
        if L2[i]!=0:
            temp3+=L2[i]
            
    temp=(pow(2,temp2)-1)+(pow(2,temp3)-1)
        
    ans=(ans*(temp+1))%mod
        
    if (0,0) in d:
        #他の選び方と共存しない
        v=d[(0,0)]
        ans=(ans+v+1)%mod

    ans=(ans-1)%mod
    print(ans)
        
        
            
            
    #せんぶ０の組みをひく
        
    

main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def func(b, w):
    return ((pow(2, b, MOD) + pow(2, w, MOD)) % MOD + MOD - 1) % MOD 

def solve(N: int, A: "List[int]", B: "List[int]"):
    from fractions import Fraction
    from collections import Counter
    C = [Fraction(a, b) for a, b in zip(A, B) if 0 not in (a, b)]
    D = [-Fraction(b, a) for a, b in zip(A, B) if 0 not in (a, b)]
    E = Counter(C)
    F = Counter(D)
    G = []
    used = set()
    for e, f in zip(E, F):
        if e in used or f in used:
            continue
        G.append((e, E[e], F[e]))
        used.add(e)
        used.add(f)
    ans = 1
    #print(G)
    for e, b, w in G:
        # print(b, w, func(b, w))
        ans = (ans * func(b, w)) % MOD
    H = sum(1 if 0 in (a, b) else 0 for a, b in zip(A, B))
    #print(ans)
    ans = (ans * func(H, 0)) % MOD
    return (ans-1+MOD)%MOD
        

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(solve(N, A, B))

def test():
    import doctest
    doctest.testmod()

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

Submission status: Wrong Answer

Solution code:

import math
def heikatu(A,B):
    if A % abs(B) ==0:
        return (A//abs(B),B//abs(B))
    if abs(B) % A == 0:
        return (1,B//A)
    
    c = 2
    while c <=math.sqrt(max(A,abs(B))):
        while A % c ==0 and B% c ==0:
            A //=c
            B//=c
        c+=1

    return (A,B)


def pow_r(x, n,mod=10**9+7):
    """
    O(log n)
    """
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r((x ** 2)%1000000007 , n // 2) % mod
    else:  # standard case ② n is odd
        return (x * pow_r((x ** 2)%1000000007, (n - 1) // 2) % mod) % mod



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

    kp = dict()
    km = dict()
    zero = [0,0]
    zerozero = 0
    for i in range(N):
        A,B = map(int,input().split())

        if A == 0 and B == 0:
            zerozero+=1
            continue

        if A == 0:
            zero[0]+=1
            continue
        if B == 0:
            zero[1]+=1
            continue

        if A <0:
            A *= -1
            B *= -1
        xx = heikatu(A,B)



        if B < 0:
            if not xx in km:
                km[xx]=0
            km[xx]+=1
        else:
            if not xx in kp:
                kp[xx]=0
            kp[xx]+=1

    tx = dict()
    if zero != [0,0]:
        zero.sort()
        tx[tuple(zero)] = 1

    for key in kp:
        A,B = key
        cou = kp[key]    
        if (B,-A) in km:
            tmp = (cou,km[(B,-A)])
            km.pop((B,-A))
        else:
            tmp = ((cou,0))
        
        tmp = tuple(sorted(tmp))
        if not tmp in tx:
            tx[tmp] = 0
        tx[tmp]+=1

    for key in km:
        if not (km[key],0) in tx:
            tx[(km[key],0)]=0    
        tx[(km[key],0)]+=1

    ans = 1
    mod = 1000000007

    for a,b in tx:
        xxx = 0
        if a != 0:
            xxx=(xxx+pow_r(2,a)) %mod
        if b != 0:
            xxx=(xxx+pow_r(2,b)) %mod
        if a !=0 and b!=0:
            xxx-=1
        xxx = pow_r(xxx,tx[(a,b)]) 
        ans = (ans*xxx) % mod


    ans = (ans+mod-1) % mod 

    print(ans)       


        




resolve()