101734: [AtCoder]ABC173 E - Multiplication 4

Problem Statement

Given are $N$ integers $A_1,\ldots,A_N$.

We will choose exactly $K$ of these elements. Find the maximum possible product of the chosen elements.

Then, print the maximum product modulo $(10^9+7)$, using an integer between $0$ and $10^9+6$ (inclusive).

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print the maximum product modulo $(10^9+7)$, using an integer between $0$ and $10^9+6$ (inclusive).

Sample Input 1

4 2
1 2 -3 -4

Sample Output 1

12

The possible products of the two chosen elements are $2$, $-3$, $-4$, $-6$, $-8$, and $12$, so the maximum product is $12$.

Sample Input 2

4 3
-1 -2 -3 -4

Sample Output 2

1000000001

The possible products of the three chosen elements are $-24$, $-12$, $-8$, and $-6$, so the maximum product is $-6$.

We print this value modulo $(10^9+7)$, that is, $1000000001$.

Sample Input 3

2 1
-1 1000000000

Sample Output 3

1000000000

The possible products of the one chosen element are $-1$ and $1000000000$, so the maximum product is $1000000000$.

Sample Input 4

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

Sample Output 4

999983200

Be sure to print the product modulo $(10^9+7)$.