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 ll long long
using namespace std;
ll a[200009],b[200009];
ll mod = 1e9 + 7;
int main(){
    ll n, k;
    vector<ll> P, N;
    cin >> n >> k;
    for(ll i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] < 0) N.push_back(-a[i]);
        else P.push_back(a[i]);
    }
    if(k == n){
        ll ans = 1;
        for(int i = 1;i  <= n; i++){
            ans = ans *a[i] % mod;
        }
        cout << (ans + mod )% mod<<endl;
        return 0;
    }
    sort(N.rbegin(), N.rend());
    sort(P.rbegin(), P.rend());
    if(P.size() == 0 && k % 2 == 1 ){
        ll ans = 1;
        for(ll i = N.size()-k; i < N.size(); i++)
            ans = ans * (-N[i]) % mod;
        cout << (mod + ans) % mod << endl;
        return 0;
    }
    vector<ll> v;
    ll ans = 1;
    //N, (P+n-1)
    for(ll i =0 ; i+1 < N.size(); i+=2)
        v.push_back(N[i] * N[i+1]);
    for(ll i = k % 2; i+1 < P.size(); i+=2)
        v.push_back(P[i] * P[i+1]);
    if(k % 2) ans = P[0];
    sort(v.rbegin(), v.rend());
    for(ll i = 0; i < k/2; i++)
        ans = ans * (v[i]%mod) % mod;
    cout << ans << endl;





}
