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 int mod=1e9+7;
int N, K;

bool cmp(long long x, long long y){
    return abs(x)<abs(y);
}

int main(){
    scanf("%d%d", &N, &K);
    vector<long long> A(N);
    int pn=0, nn=0;
    for (int i=0; i<N; i++){
        scanf("%lld", &A[i]);
        if (A[i]<0) nn++;
        else pn++;
    }
    long long ans=1;
    if (pn==0&&K%2){
        sort(A.begin(), A.end(), cmp);
        for (int i=0; i<K; i++) ans=ans*A[i]%mod;
    }
    else {
        sort(A.begin(), A.end(), greater<long long>());
        // for (int i=0; i<N; i++) printf("%lld ", A[i]);
        int l=0, r=N-1;
        while (K){
            if (K%2){
                ans=ans*A[l]%mod;
                l++;
                K--;
            }
            else {
                if (A[l]*A[l+1]>=A[r]*A[r-1]){
                    ans=(ans*A[l]%mod*A[l+1]%mod);
                    l+=2, K-=2;
                }
                else{
                    ans=(ans*A[r]%mod*A[r-1]%mod);
                    r-=2, K-=2;
                }
            }
        }
    }
    ans=(ans%mod+mod)%mod;
    printf("%lld\n", ans);
    return 0;
}