E - 乘法4

分数 : $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$，$-3$，$-4$，$-6$，$-8$，和 $12$，所以最大乘积是 $12$。

4 3
-1 -2 -3 -4

1000000001

三个选定元素的可能乘积是 $-24$，$-12$，$-8$，和 $-6$，所以最大乘积是 $-6$。

我们输出该值模 $(10^9+7)$，也就是 $1000000001$。

2 1
-1 1000000000

1000000000

一个选定元素的可能乘积是 $-1$ 和 $1000000000$，所以最大乘积是 $1000000000$。

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

999983200

确保打印结果模 $(10^9+7)$。