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).

Examples

Input

4 2
1 2 -3 -4


Output

12


Input

4 3
-1 -2 -3 -4


Output

1000000001


Input

2 1
-1 1000000000


Output

1000000000


Input

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


Output

999983200
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<long long> v;
const long long mod = 1e9 + 7;

int main() {
    int n, k, pos = 0;
    bool zeros = false;
    scanf("%d %d", &n, &k);
    for (int i = 0; i != n; i++) {
        long long j;
        scanf("%lld", &j);
        pos += j > 0;
        zeros |= !j;
        v.push_back(j);
    }
    sort(v.begin(), v.end());
    long long ans = 1;
    long long l = 0, r = n - 1;
    if (k & 1)ans = v[r--], k--;
    while (k) {
        long long lf = v[l] * v[l + 1], rt = v[r] * v[r - 1], c = ans > 0 ? 1 : -1;
        if (lf * c > rt * c) {
            l += 2;
            ans = ans * (lf % mod) % mod;
        } else {
            r -= 2;
            ans = ans * (rt % mod) % mod;
        }
        k -= 2;
    }
    printf("%lld", (ans + mod) % mod);
    return 0;
}