乘法 4

题目描述

给定 $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$ 以下的整数输出。

样例

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)$ 的余数。

数据范围

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