配点 : $500$ 点

問題文

$N$ 個の整数 $A_1,\ldots,A_N$ が与えられます。

このなかからちょうど $K$ 個の要素を選ぶとき、選んだ要素の積としてありえる最大値を求めてください。

そして、答えを $(10^9+7)$ で割った余りを $0$ 以上 $10^9+6$ 以下の整数として出力してください。

制約

• $1 \leq K \leq N \leq 2\times 10^5$
• $|A_i| \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $\ldots$ $A_N$

出力

答えを $(10^9+7)$ で割った余りを、$0$ 以上 $10^9+6$ 以下の整数として出力せよ。

4 2
1 2 -3 -4

12

要素を $2$ 個選んだときの積としてありえる値は $2,-3,-4,-6,-8,12$ なので、最大値は $12$ です。

4 3
-1 -2 -3 -4

1000000001

要素を $3$ 個選んだときの積としてありえる値は $-24,-12,-8,-6$ なので、最大値は $-6$ です。

これを $(10^9+7)$ で割った余りである $1000000001$ を出力します。

2 1
-1 1000000000

1000000000

要素を $1$ 個選んだときの積としてありえる値は $-1,1000000000$ なので、最大値は $1000000000$ です。

10 10
1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1

999983200

答えを $(10^9+7)$ で割った余りを出力してください。