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
from itertools import groupby, accumulate, product, permutations, combinations
from math import gcd
def reduction(x,y):
    g = gcd(x,y)
    return abs(x)//g,abs(y)//g

def solve():
    mod = 10**9+7
    dplus = defaultdict(lambda: 0)
    dminus = defaultdict(lambda: 0)
    N = int(input())
    xzero = 0
    yzero = 0
    xyzero = 0
    for i in range(N):
        x,y = map(int, input().split())
        if x==0:
            if y==0:
                xyzero += 1
            else:
                xzero += 1
        elif y==0:
            yzero += 1
        elif x*y>0:
            dplus[reduction(x,y)] += 1
        else:
            dminus[reduction(-y,x)] += 1
    pattern = 1
    other = N
    pattern = pow(2,xzero,mod)+pow(2,yzero,mod)-1
    other = N-xzero-yzero-xyzero
    for k,v in dplus.items():
        pattern *= pow(2,dminus[k],mod)+pow(2,v,mod)-1
        other -= dminus[k]+v
    ans = pattern * pow(2,other,mod) - 1
    ans += pow(2,xyzero,mod)-1
    ans %= mod
    return ans
print(solve())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    d = defaultdict(int)
    d2 = defaultdict(int)
    d3 = defaultdict(int)
    aa = 0
    for a, b in ab:
        if a == b == 0:
            aa += 1
            continue
        if a == 0:
            d[0] += 1
            d3[0] = 1
        elif b == 0:
            d2[0] += 1
            d3[0] = 1
        else:
            if a * b > 0:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d[(a , b)] += 1
                d3[(a , b)] = 1
            else:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d2[(abs(b), abs(a))] += 1
                d3[(abs(b), abs(a))] = 1
    ans = 1
    for k in d3.keys():
        ans *= (2 ** d[k] + 2 ** d2[k] - 1)
        ans %= mod
    ans -= 1
    print(ans % mod)
    return


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

Submission status: Wrong Answer

Solution code:
n = int(input())

abl = [map(int, input().split()) for _ in range(n)]

from collections import defaultdict
dic = defaultdict(int)

# a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

a0 = 0
b0 = 0
for a,b in abl:
    if a == 0 and b == 0:
        continue
    elif a == 0:
        a0 += 1
        continue
    elif b == 0:
        b0 += 1
        continue
    gc = abs(gcd(a,b))
    if a < 0:
        a, b = -a // gc, -b // gc
    else:
        a, b = a // gc, b // gc
    dic[(a,b)] += 1
MOD = 1000000007
ans = 1
used = defaultdict(int)
for (a,b) in dic:
    if b > 0:
        target = (b, -a)
    else:
        target = (-b, a)
    if target in dic:
        if used[target] == 0:
            ans *= pow(2, dic[(a,b)], MOD) + pow(2, dic[target], MOD) - 1
            used[(a,b)] = 1
    else:
        ans *= (dic[(a,b)] + 1)
    ans %= 1000000007

ans *= pow(2, a0, MOD) + pow(2, b0, MOD) - 1
ans %= 1000000007
print(ans - 1)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
mod = 1000000007

def solve():
    input = sys.stdin.readline
    N = int(input())
    F = [[int(i) for i in input().split()] for _ in range(N)]
    D = dict()
    for x, y in F:
        if x == 0 and y == 0: tan = "NG"
        elif x == 0: tan = "Inf"
        elif y == 0: tan = 0
        else: tan = y / x

        if tan in D: D[tan] += 1
        else: D[tan] = 1

    ans = 1
    used = set()
    for key in D:
        if key not in used and key != "NG":
            this = D[key]
            used |= {key}
            if key == "Inf":
                op = (0 if 0 not in D else D[0])
                used |= {0}
            elif key == 0: 
                op = (0 if "Inf" not in D else D["Inf"])
                used |= {"Inf"}
            else: 
                op = (0 if -1 / key not in D else D[-1 / key])
                used |= {-1 / key}
            select = (pow(2, this, mod) + pow(2, op, mod) - 1) % mod
            ans *= select
            ans %= mod
    if "NG" in D: ans += D["NG"]
    ans = (ans - 1 + mod) % mod
    #print(D)
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

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**9+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
        # ans+=dm[pp]
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        pp=(abs(b)*pow(abs(a),mod-2,mod))%mod
        # cm.append(p)
        dm[p]+=1
        # ans+=dp[pp]
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
ans+=pow(2,az,mod)+pow(2,bz,mod)+cz-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:
import collections
n=int(input())
A=[]
AA=[]
B=[]
C=[]
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:
      continue
    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
a=(a*(2**len(B)+2**len(C)-1)-1)%mod
print(a)

Submission status: Wrong Answer

Solution code:
import math
import itertools

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

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

# pattern = 0
# for r in range(math.ceil(N / 2)):
#     pattern += Cmb(N, r+1)

# bad_pattern = 0
# for A, B in itertools.combinations(iwashi_list, 2):
#     if A[0]*A[1] + B[0]*B[1] == 0:
#         print('Bad', A, B)
#         bad_pattern += 1

pattern = 0
for r in range(math.ceil(N)):
    # イワシを r 匹取り出す
    hoge = 0
    for iwashis in itertools.combinations(iwashi_list, r+1):
        # if r == 1:
        #     import ipdb; ipdb.set_trace()
        # 仲が悪いイワシのペアがないかチェックする
        hoge += 1
        for A, B in itertools.combinations(iwashis, 2):
            # 仲が悪いイワシなら break
            if A[0]*A[1] + B[0]*B[1] == 0:
                break
        # 仲が悪いイワシの組み合わせじゃないので，パターンに追加
        else:
            pattern += 1
    # print(hoge)

print(pattern)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from math import gcd
mod = 10**9+7
n = int(input())
dic = defaultdict(lambda:[[0,0],[0,0]])
zero = [0,0]
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 or b == 0:
        if a == 0 and b == 0:
            continue
        else:
            if a == 0:
                zero[0] += 1
            else:
                zero[1] += 1
        continue
    minus = False
    rev = False
    if a * b < 0:
        minus = True
    a,b = abs(a),abs(b)
    g = gcd(a,b)
    a,b = a//g,b//g
    if a > b:
        a,b = b,a
        rev = True
    if minus:
        if rev:
            dic[(a,b)][0][1] += 1
        else:
            dic[(a,b)][0][0] += 1
    else:
        if rev:
            dic[(a,b)][1][1] += 1
        else:
            dic[(a,b)][1][0] += 1
ans = 1
for y in dic.keys():
    x = dic[y]
    if y == (1,1):
        ans *= 2**sum(x[0])+2**sum(x[1])-1
    else:
        ans *= 2**x[0][1]+2**x[1][0]-1
        ans *= 2**x[0][0]+2**x[1][1]-1
        ans %= mod
ans *= 2**zero[0]+2**zero[1]-1
ans %= mod
print(ans-1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from math import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    d=defaultdict(lambda:[0,0])
    for _ in range(N):
        a,b=map(int,input().split())
        g=gcd(a,b)
        if g!=0:
            a//=g
            b//=g
        if a<0:
            a*=-1
            b*=-1
        if a*b>0:
            d[(a,b)][0]+=1
        elif a*b<0:
            d[(-b,a)][1]+=1
        else:
            d[(0,0)][0]+=1
    l=[]
    zero=0
    other=0
    for k,a in d.items():
        if k==(0,0):
            zero=a[0]
        else:
            if a[0] and a[1]:
                l.append((a[0],a[1]))
            else:
                other+=sum(a)
    ans=pow(2,other,MOD)*(zero+1)
    ans%=MOD
    dp=[[0]*2 for _ in range(len(l)+1)]
    dp[0][0]=1
    for i in range(len(l)):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        dp[i+1][1]=(dp[i][0]+dp[i][1])*(pow(2,l[i][0],MOD)+pow(2,l[i][1],MOD)-2)
        dp[i+1][0]%=MOD
        dp[i+1][1]%=MOD
    ans*=sum(dp[-1])
    ans-=1
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    from sys import stdin
    from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import numpy as np
    import math
    # import random
    input = stdin.readline

    p = 1000000007

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

        K = 1
        while n > 1:
            if n % 2 != 0:
                K *= x
            x *= x
            x = x%p
            n //= 2

        return (K * x)%p

    n = int(input())
    ab_0 = 0
    a_0 = 0
    b_0 = 0
    a_div_b_dict = defaultdict(int)
    for _ in range(n):
        a, b = map(int, input().split())
        if a == 0 and b == 0:
            ab_0 += 1
            continue
        if a == 0:
            a_0 += 1
            continue
        if b == 0:
            b_0 += 1
            continue
        if a*b > 0:
            front = ''
        else:
            front = '-'
        ab_gcd = math.gcd(a, b)
        a = str(abs(a//ab_gcd))
        b = str(abs(b//ab_gcd))
        a_div_b_dict[front+a.zfill(6)+b.zfill(6)] += 1
    # print(a_div_b_dict)
    visited = set()
    ans = 1
    for_loop = dict(a_div_b_dict)
    for key, value in for_loop.items():
        # print(visited)
        if key in visited:
            continue
        if key[0] == '-':
            front = key[1:7]
            back = key[7:]
            inverse = back + front
            visited.add(inverse)
            num = pow_k(2, value) + pow_k(2, a_div_b_dict[inverse])-1
            ans = (ans*num)%p
        else:
            front = key[:6]
            back = key[6:]
            inverse = '-' + back + front
            visited.add(inverse)
            num = pow_k(2, value) + pow_k(2, a_div_b_dict[inverse])-1
            ans = (ans*num)%p
    ans *= (pow_k(2, a_0) + pow_k(2, b_0)-1)
    ans += ab_0
    print((ans-1)%p)


"""            visited.add(key)
            num = pow_k(2, value) + pow_k(2, a_div_b_dict[key])-1
"""

Submission status: Wrong Answer

Solution code:
import math
from collections import Counter

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

iwashi = []
for _ in range(n):
    a, b = map(int, input().split())
    rad = round(math.degrees(math.atan2(a, b)), 20)
    if rad - 180 == 0:
        rad = 0
    if rad < 0:
        rad += 180
    iwashi.append([a, b, rad])
    c[rad] += 1
    cc[rad] += 1


l = []

for r in cc.keys():
    if 0 <= r < 90:
        ra = c[r]
        rb = c[r+90]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r] -= 10**9
        c[r+90] -= 10**9
    else:
        ra = c[r-90]
        rb = c[r]
        if ra >= 0 and rb >= 0:
            l.append([ra, rb])
        c[r-90] -= 10**9
        c[r] -= 10**9

ans = 1

for a, b in l:
    ans *= pow(2, a, mod)-1 + pow(2, b, mod)-1 + 1

ans = (ans-1) % mod

print(ans)

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *
def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1/f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def solve():
    n = getN()
    iwashis = []
    zz = 0
    fr = defaultdict(int)
    for i in range(n):
        iw = getList()
        if iw[0] == 0 and iw[1] == 0:
            zz += 1
            continue
        if iw[0] != 0:
            # fr[Fraction(iw[1], iw[0])] += 1
            fr[iw[1]/iw[0]] += 1
        else:
            fr["INF"] += 1

    used = defaultdict(int)
    ans = 1
    for k, v in fr.items():
        if k in used:
            continue
        if k == "INF":
            if 0 in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[0], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[0] += 1
        elif k != 0:
            if - inverse(k) in fr:
                ans *= pow(2, v, MOD) + pow(2, fr[- inverse(k)], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used[- inverse(k)] += 1
        elif k == 0:
            if "INF" in fr:
                ans *= pow(2, v, MOD) + pow(2, fr["INF"], MOD) - 1
                ans %= MOD
            else:
                ans *= pow(2, v, MOD)
                ans %= MOD
            used["INF"] += 1
        # print(k, v, ans, -inverse(k))
    # print(fr)
    print((ans-1+zz) % MOD)
    # print(Fraction(0, ???1) == 0)

def main():
    n = getN()
    for _ in range(n):
        solve()
if __name__ == "__main__":
    solve()

"""
12
3 2
3 2
-1 1
2 -1
-3 -9
-8 12
7 7
8 1
8 2
8 4
0 0
0 0
"""

Submission status: Wrong Answer

Solution code:
N = int(input())
import numpy as np
ab=np.array([])
for i in range(N):
	A,B=map(float, input().split())
	ab=np.append(ab,[A,B])

a_all=ab[1::2]
b_all=ab[::2]
seki_all=a_all*b_all
a=a_all[seki_all!=0]
b=b_all[seki_all!=0]
frac_np=a/b

import collections
frac=frac_np.tolist()

fr_p=[i for i in frac if i>0]
fr_n=[-1.0/i for i in frac if i<0]
factors=set(fr_p+fr_n)
count_p=collections.Counter(fr_p)
count_n=collections.Counter(fr_n)

gamma=1
for i in factors:
	gamma*=(2**count_p[i]+2**count_n[i]-1)

print(gamma-1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
arr = set()
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        ct[a/b] += 1
        arr.add((a, b))
ans = pow(2, Allzero, MOD)
ans %= MOD
ans *= pow(2, Azero, MOD) + pow(2, Bzero, MOD) - 1
ans %= MOD
visited = set()
for (a, b) in arr:
    v = a/b
    if v in visited:
        continue
    inv = -b/a
    visited.add(v)
    visited.add(inv)
    tmp = pow(2, ct[v], MOD) + pow(2, ct[inv], MOD) - 1
    ans *= tmp
    ans %= MOD
print(ans-1)

Submission status: Wrong Answer

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

iw=[]
for i in range(n):
    ab=list(map(int, input().split( )))
    iw.append(ab)

for i in range(n):
    ai,bi=iw[i]
    if ai and bi:##互いに素にする
        g=gcd(ai,bi)
        iw[i][0]//=g;iw[i][1]//=g
    else:#どちらか0なら残りを1か0にする
        if ai:#biがゼロでaiが非ゼロ
            iw[i][0]=1
        elif bi:#aiがゼロでbiが非ゼロ
            iw[i][1]=1
    if bi<0:#biは正に設定
        iw[i][0]*=-1;iw[i][1]*=-1
    if bi==0 and ai<0:#biがゼロならaiは正かゼロ
        iw[i][0]*=-1
iw = [tuple(iwi) for iwi in iw]
C=Counter(iw)
ans=1
mod=10**9+7
#print(C)
#ai bi=0,0は別に処理が要る
tmp=0
if (0,0) in C:
    tmp= C.pop((0,0))
for ai,bi in C:
    if ai==0 and C[(ai,bi)]>0:##ai==0
        if (bi,ai) in C and C[(bi,ai)]>0:
            ans*=(pow(2,C[(bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    elif bi==0 and C[(ai,bi)]>0:##bi==0
        if ai<0:##?
            ai*=-1
        if (bi,ai) in C and C[(bi,ai)]>0:
            ans*=(pow(2,C[(bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    elif ai>0 and C[(ai,bi)]>0:#ai>0
        if (-bi,ai) in C and C[(-bi,ai)]>0:
            ans*=(pow(2,C[(-bi,ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(-bi,ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    elif C[(ai,bi)]>0:#ai<0
        if (bi,-ai) in C and C[(bi,-ai)]>0:
            ans*=(pow(2,C[(bi,-ai)],mod)+pow(2,C[(ai,bi)],mod)-1)
            ans%=mod
            C[(bi,-ai)]=-1
        else:
            ans*= pow(2,C[(ai,bi)],mod)
            ans%=mod
    
    #print((ai,bi),C[(ai,bi)],ans)
print((ans+tmp-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from math import gcd
from collections import defaultdict


n = readint()

mod = 1000000007

d = defaultdict(int)

for i in range(n):
    a,b = readints()
    g = gcd(a,b)
    if g!=0:
        a//=g
        b//=g
    if a<0:
        a*=-1
        b*=-1
    d[(a,b)]+=1

ans = 1
k = tuple(d.keys())
for x in k:
    if x[1]>=0:
        ans *= pow(2,d[x],mod)+pow(2,d[(x[1],-x[0])],mod)-1
    else:
        if d[(-x[1],x[0])]==0:
            ans *= pow(2, d[x], mod)
    ans %= mod

print(ans-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ab = LIR(n)
    d = defaultdict(int)
    d2 = defaultdict(int)
    d3 = defaultdict(int)
    aa = 0
    for a, b in ab:
        if a == b == 0:
            aa += 1
            continue
        if a == 0:
            d[0] += 1
            d3[0] = 1
        elif b == 0:
            d2[0] += 1
            d3[0] = 1
        else:
            if a * b > 0:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d[(a , b)] += 1
                d3[(a , b)] = 1
            else:
                x = math.gcd(a, b)
                a //= x
                b //= x
                d2[(abs(b), abs(a))] += 1
                d3[(abs(b), abs(a))] = 1
    ans = 1
    for k in d3.keys():
        ans *= (2 ** d[k] + 2 ** d2[k] - 1)
        ans %= mod
    ans -= 1
    ans += aa
    print(ans % mod)
    return


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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]
mod = 10**9+7
def p2(x):
  return pow(2,x,mod)
dc = defaultdict(int)
st = set()
from math import gcd
n00 = 0
n0x = 0
nx0 = 0
nxy = 0
ls = []
for i in range(n):
  if a[i][0] == a[i][1] == 0:
    n00 += 1
  elif a[i][0] == 0:
    n0x += 1
  elif a[i][1] == 0:
    nx0 += 1
  else:
    nxy += 1
    if a[i][0] < 0 and a[i][1] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    elif a[i][0] < 0:
      a[i][0] *= -1
      a[i][1] *= -1
    ls.append(a[i])
if len(ls) == 0:
  print((p2(n0x)+p2(nx0)-1+n00-1)%mod)
  exit()
def part(x,y):
  g = gcd(x,y)
  return (x//g,y//g)
for i in range(nxy):
  p = part(*ls[i])
  st.add(p)
  dc[p] += 1
banned = []
for i,j in dc:
  if i*j > 0 and (j,-i) in st:
    banned.append((dc[(i,j)],dc[(j,-i)]))
sm = sum([banned[i][0]+banned[i][1] for i in range(len(banned))])
ans = p2(n-sm)
for i,j in banned:
  ans = (ans*(p2(i)+p2(j)-1))%mod
k = p2(n0x)+p2(nx0)-1
ans *= k
ans += n00-1
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import math
mod=1000000007
n=int(input())
dic=defaultdict(int)
x=[]
zerozero,azero,bzero=0,0,0
two=[1]

for i in range(n):
    two.append(two[-1]*2%mod)

for _ in range(n):
        
    a,b=map(int,input().split())
    if a==0 and b==0: zerozero+=1
    elif a==0: azero+=1
    elif b==0: bzero+=1
    else:
        k=math.gcd(a,b)
        a//=k;b//=k
        if a<0: a*=-1;b*=-1
        dic[(a,b)]+=1
        if a*b>0: dic[(b,-a)]+=0
        else: dic[(-b,a)]+=0

for (a,b) in dic:
    if a*b>0:
        x.append([ dic[(a,b)], dic[(b,-a)] ])
x.append([azero,bzero])
ans=1
for [p,q] in x:
    ans*=(two[p]+two[q]-1)
    ans%=mod
print(ans+zerozero-1)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction
from collections import defaultdict

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from fractions import Fraction

N = int(input())

dict_F = {}
count_0 = 0

def insert(A,B,s): # A>=0, B>0, s=0or1
  if Fraction(A,B) not in dict_F.keys():
    dict_F[Fraction(A,B)] = [0,0]
  dict_F[Fraction(A,B)][s] += 1

def power2(A):
  result = 1
  for _ in range(A):
    result = (2*result)%mod
  return result

for _ in range(N):
  A,B = map(int, input().split())
  if A==0 and B==0:
    count_0 += 1
  elif A>=0 and B>0:
    insert(A,B,0)
  elif A>0 and B<=0:
    insert(-B,A,1)
  elif A<=0 and B<0:
    insert(-A,-B,0)
  elif A<0 and B>=0:
    insert(B,-A,1)

mod = 1000000007
answer = 1
#for A,B in dict_F.values():
#  answer = (answer*(power2(A)+power2(B)-1))%mod
answer = (answer+count_0-1)%mod
print(answer)

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**9+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
        # ans+=dm[pp]
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        pp=(abs(b)*pow(abs(a),mod-2,mod))%mod
        # cm.append(p)
        dm[p]+=1
        # ans+=dp[pp]
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
ans+=pow(2,az,mod)+pow(2,bz,mod)+cz-1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    z-=(dp[a]+dm[b])
# print(z)
ans*=pow(2,z,mod)


print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import math
MOD = 1000000007
N = int(input())
A = []
d = {}
for i in range(N):
	a,b = map(int,input().split())
	g = math.gcd(a,b)
	if a < 0:
		a *= -1
		b *= -1
	if a == 0 and b < 0:
		b *= -1
	if g != 0:
		a = a // g
		b = b // g
	if (a,b) in d:
		d[(a,b)] += 1
	else:
		d[(a,b)] = 1

ans_sp = 0
if (0,0) in d:
	ans_sp += d[(0,0)]

def pow(n, k):
	ret = 1
	while k > 0:
		if k % 2 == 1:
			ret = ret * n % MOD
		n = n * n % MOD
		k = k // 2
	return ret

ans = 1
for k in d:
	a,b = k[0], k[1]
	if a == 0 and b == 0:
		continue
	v = d[k]
	x,y = b,-a
	if x < 0:
		x *= -1
		y *= -1
	if (x,y) in d:
		if  b > y:
			continue
		tmp = (pow(2,v) + pow(2,d[(x,y)])) - 1 % MOD
		ans = (ans * tmp) % MOD
	else:
		ans = (ans * pow(2,v)) % MOD
print(ans_sp + ans - 1)

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**9+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
        # ans+=dm[pp]
    elif a*b<0:
        p=(abs(a)*pow(abs(b),mod-2,mod))%mod
        pp=(abs(b)*pow(abs(a),mod-2,mod))%mod
        # cm.append(p)
        dm[p]+=1
        # ans+=dp[pp]
    elif a==b==0:
        cz+=1
    elif a==0:
        az+=1
    elif b==0:
        bz+=1
ans+=pow(2,az,mod)+pow(2,bz,mod)+cz-1
z=n-(az+bz+cz)
for a,b in cp:
    ans*=pow(2,dp[a],mod)+pow(2,dm[b],mod)-1
    z-=(dp[a]+dm[b])
print(z)
ans*=pow(2,z,mod)


print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from math import gcd
MOD = 10 ** 9 + 7
N = int(input())
ct = Counter()
Azero = 0
Bzero = 0
Allzero = 0
arr = set()
for _ in range(N):
    a, b = map(int, input().split())
    if a == b == 0:
        Allzero += 1
    elif a == 0:
        Azero += 1
    elif b == 0:
        Bzero += 1
    else:
        ct[a/b] += 1
        arr.add((a, b))
ans = 1 + Allzero
ans *= 1 + Azero + Bzero
visited = set()
for (a, b) in arr:
    v = a/b
    if v in visited:
        continue
    inv = -b/a
    visited.add(v)
    visited.add(inv)
    tmp = 1 + (pow(2, ct[v], MOD)-1) + (pow(2, ct[inv], MOD)-1)
    ans *= tmp
    ans %= MOD
print(ans-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
zeros = 0
m = {}

mod = 10**9 + 7

def pmod(a, x) :
	if x == 0 :
		return 1
	sq = pmod(a,x//2)
	sq = (sq * sq) % mod
	if x%2 == 0 :
		return sq
	return (sq * a) % mod

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

for _ in range(n):
	a,b = map(int, input().split())
	if a == 0 and b == 0:
		zeros += 1
		continue
	d = gcd(abs(a), abs(b))
	a, b = a/d, b/d;
	if a < 0 :
		a, b = -a, -b
	if a == 0 and b < 0 :
		b = -b
	if (a,b) in m :
		m[(a,b)] += 1;
	else :
		m[(a,b)] = 1

ans = 1
for u in m:
	ile = m[u]
	a, b = u[0], u[1]
	m[u] = 0
	ile2 = 0
	inv = (b, -a)
	if (b < 0) :
		inv = (-b, a)
	if b == 0 and a > 0 :
		inv = (0, 1)
	if inv in m:
		ile2 = m[inv]
		m[inv] = 0
	ans = (ans * (pmod(2, ile) + pmod(2, ile2) - 1)) % mod;

print ( (ans + zeros - 1+mod) % mod)

Submission status: Wrong Answer

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

N = Int()
mod = 1000000007
ans = 1
import math

from collections import defaultdict
XX = defaultdict(list)
YY = defaultdict(list)

for i in range(N):
    A,B = Ints()
    if A!=0 and B!=0:
        GCD = math.gcd(A,B)
        A //=GCD
        B //=GCD
        if A<0 and B<0:
            A *= -1
            B *= -1
        elif A>0 and B<0:
            A *= -1
            B *= -1
        XX[(A,B)].append(i)
        
        B *= -1
        if A<0 and B<0:
            A *= -1
            B *= -1
        elif A<0 and B>0:
            A *= -1
            B *= -1
        YY[(B,A)].append(i)
        
    elif A==0 and B!=0:
        XX[(0,1)].append(i)
        YY[(1,0)].append(i)
    elif A!=0 and B==0:
        XX[(1,0)].append(i)
        YY[(0,1)].append(i)


D = {}

for key in XX:
    if not key in D:
        l = len(XX[key])
        m = len(YY[key])
        ans *= (pow(2,l,mod)+pow(2,m,mod)-1)
        ans %= mod
        D[key] = 1
        
        a,b = key
        if a==0 and b==1:
            D[(1,0)] = 1
        elif a==1 and b==0:
            D[(0,1)] = 1
        else:
            b *= -1
            if a < 0:
                b*=-1
                a*=-1
            D[(b,a)] = 1
    
ans -= 1
ans %= mod
print(ans)