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;
typedef long long ll;
 
const int M = 1000000007;
 
int main()
{
    int n,k; cin>>n>>k;
 
    vector<ll> v(n);
    for(int i=0;i<n;++i) cin>>v[i];
 
    ll prod=1;
 
    sort(v.begin(),v.end());
 
    if(v[n-1]==0 && (k&1))
    {
        prod=0;
    }
    else if(v[n-1]<0 && (k&1))
    {
        for(int i=n-1;i>=n-k;--i) prod=((prod%M)*(v[i]%M))%M;
    }
    else{ 
        int i=0,j=n-1;
        if(v[n-1]>0 and k&1){ 
            prod = (prod*v[j])%M;
            k--;
            j--;
        }
    
    k=(k/2);
    for(int it=0;it<k;++it)
    {
        ll left_prod = v[i]*v[i+1];
        ll right_prod = v[j]*v[j-1];
 
        if(left_prod > right_prod)
        {
            prod = ((prod%M)*(left_prod%M))%M;
            i+=2;
        }
        else{
            prod = ((prod%M)*(right_prod%M))%M;
            j-=2;
        }
    }
    }
    prod = (prod + M)%M;
    cout<<prod;
}