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<stdio.h>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<algorithm>
#include<math.h>
#define pans (((long long)pow(10,9))+(long long)7)
#define rep(i,n) for(int i = 0;i < (n);++i)
using namespace std;

int main(){
    long long n,k;
    long long ans = 1;
    cin >> n >> k;
    int s = 0,e = n-1;
    long long t;
    bool f = false;
    vector<long long> A(n);
    rep(i,n){
        cin >> t;
        A[i] = t%pans;
    }
    sort(A.rbegin(),A.rend());
    if(k%2 != 0){
        if(A[s] < 0) f = true;
        ans *= A[s];
        s++;
    }
    rep(i,int(k/2)){
        if(k == 1)break;
        if(A[s]*A[s+1] > A[e]*A[e-1] || f == true){
            ans *= (A[s]*A[s+1])%pans;
            s += 2;
        }else{
            ans *= (A[e]*A[e-1])%pans;
            e -= 2;
        }
        ans %= pans;
    }
    if(ans < 0)ans += pans;
    printf("%lld",ans);
}