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 <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;

int main(void) {
    long long N, K;
    cin >> N >> K;
    vector< long long > A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    long long ans = 1LL;
    sort(A.begin(), A.end());
    reverse(A.begin(), A.end());
    bool minus = false;
    if (A[0] < 0LL && K % 2 == 1) {
        minus = true;
    }
    if (minus || K == N) {
        for (int i = 0; i < K; i++) {
            ans = (ans * A[i]) % MOD;
        }
        if (ans < 0LL) {
            ans += MOD;
        }
        printf("%lld\n", ans);
        return 0;
    }

    int i = 0, j = 0;
    while (true) {
        if (i + j == K - 1 || A[i] * A[i + 1] > A[N - 1 - j] * A[N - 2 - j]) {
            ans = (A[i] * ans) % MOD;
            i += 1;
        } else {
            ans = (((A[N - 1 - j] * A[N - 2 - j]) % MOD) * ans) % MOD;
            j += 2;
        }
        if (i + j >= K) {
            break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}
