题目描述

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

题目大意

给你两个数 $N,K$，从 $N$ 个数中选出 $K$ 个使得乘积最大。输出乘积在数学意义上对 $10^9+7$ 取模的值。

4 2
1 2 -3 -4

12

4 3
-1 -2 -3 -4

1000000001

2 1
-1 1000000000

1000000000

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

999983200

提示

制約

• $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)$ で割った余りを出力してください。