問題文

$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$ 以下の整数として出力せよ。

入力例 1

4 2
1 2 -3 -4

出力例 1

12

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

入力例 2

4 3
-1 -2 -3 -4

出力例 2

1000000001

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

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

入力例 3

2 1
-1 1000000000

出力例 3

1000000000

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

入力例 4

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

出力例 4

999983200

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