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>
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define fre freopen("C:\\in.txt", "r", stdin)
#define _for(i,a,b) for(int i=a; i< b; i++)
#define _rep(i,a,b) for(int i=a; i<=b; i++)
#define lowbit(a) ((a)&-(a))
#define inf 0x3f3f3f3f
#define endl "\n"
using namespace std;
typedef long long ll;
template <class T>
void read(T &x)
{
    char c; bool op=0;
    while(c=getchar(), c<'0'||c>'9') if(c=='-') op=1;
    x=c-'0';
    while(c=getchar(), c>='0'&&c<='9') x=x*10+c-'0';
    if(op) x=-x;
}

const int mod=1e9+7;

int main()
{
    int n, k;
    read(n), read(k);
    vector<ll> a(n);
    for(auto &val: a) read(val);
    sort(a.begin(), a.end());
    ll ans=1; int ok=0;
    if(k%2) ans*=a[--n], k--;
    if(ans<0) ok=1;
    int l=0, r=n-1;
    while(k){
        ll x=a[r]*a[r-1], y=a[l]*a[l+1];
        if(ok || x>y)
            ans=x%mod*ans%mod, r-=2;
        else ans=y%mod*ans%mod, l+=2;
        //cout<<l<<" "<<r<<" "<<ans<<endl;
        k-=2;
    }
    printf("%lld\n", (ans+mod)%mod);
    return 0;
}
