AT_abc173_e [ABC173E] Multiplication 4

[problemUrl]: https://atcoder.jp/contests/abc173/tasks/abc173_e $ N $ 個の整数 $ A_1,\ldots,A_N $ が与えられます。 このなかからちょうど $ K $ 個の要素を選ぶとき、選んだ要素の積としてありえる最大値を求めてください。 そして、答えを $ (10^9+7) $ で割った余りを $ 0 $ 以上 $ 10^9+6 $ 以下の整数として出力してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ A_1 $ $ \ldots $ $ A_N $

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

### 制約 - $ 1\ \leq\ K\ \leq\ N\ \leq\ 2\times\ 10^5 $ - $ |A_i|\ \leq\ 10^9 $ ### Sample Explanation 1 要素を $ 2 $ 個選んだときの積としてありえる値は $ 2,-3,-4,-6,-8,12 $ なので、最大値は $ 12 $ です。 ### Sample Explanation 2 要素を $ 3 $ 個選んだときの積としてありえる値は $ -24,-12,-8,-6 $ なので、最大値は $ -6 $ です。 これを $ (10^9+7) $ で割った余りである $ 1000000001 $ を出力します。 ### Sample Explanation 3 要素を $ 1 $ 個選んだときの積としてありえる値は $ -1,1000000000 $ なので、最大値は $ 1000000000 $ です。 ### Sample Explanation 4 答えを $ (10^9+7) $ で割った余りを出力してください。