题目描述

给定$N$个整数$A_1,\\ldots,A_N$。

我们将从中选择恰好$K$个元素。找出所选元素的最大可能乘积。

然后，使用介于$0$到$10^9+6$之间（包括边界）的整数打印模$(10^9+7)$的最大乘积。

约束条件

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

输入

输入以以下格式从标准输入给出：

$N$ $K$
$A_1$ $\\ldots$ $A_N$

输出

使用介于$0$到$10^9+6$之间（包括边界）的整数打印模$(10^9+7)$的最大乘积。

示例输入1

4 2
1 2 -3 -4

示例输出1

12

所选择的两个元素可能的乘积为$2$，$-3$，$-4$，$-6$，$-8$和$12$，因此最大乘积是$12$。

示例输入2

4 3
-1 -2 -3 -4

示例输出2

1000000001

所选择的三个元素可能的乘积为$-24$，$-12$，$-8$和$-6$，因此最大乘积是$-6$。

我们打印该值对$(10^9+7)$取模，即$1000000001$。

示例输入3

2 1
-1 1000000000

示例输出3

1000000000

所选择的一个元素可能的乘积为$-1$和$1000000000$，因此最大乘积是$1000000000$。

示例输入4

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

示例输出4

999983200

请确保打印出的乘积对$(10^9+7)$取模。