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-----
4 2
1 2 -3 -4

-----Sample Output-----
12

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

见题面

见题面