题目描述

小k有 $N$ 个整数 $A_1,\ldots,A_N$ 。

他想从这N个数中选出 $K$ 个。求所选元素的最大乘积，并输出最大乘积模 $(10^9+7)$ 的结果作为答案，请你帮帮他。

输入格式

$N$ $K$

$A_1$ $\ldots$ $A_N$

输出格式

输出最大乘积。

4 2
1 2 -3 -4

12

数据规模与约定

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