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 a[200001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a+n);
    long long ans = 1;
    if(k%2 == 1){
        if(a[n-1] == 0){
            printf("0\n");
            return 0;
        }
        else if(a[n-1] < 0){
            long long ans = 1;
            for(int i=n-1;i>=n-k;i--) ans = ans*1ll*(a[i]+mod)%mod;
            printf("%lld\n", ans);
            return 0;
        }
        else{
            ans = ans*1ll*a[n-1]%mod;
            k--;
            n--;
        }
    }
    int l = 0, r = n-1;
    while(k > 0){
        if(a[l]*1ll*a[l+1] > a[r]*1ll*a[r-1]){
            ans = ans*1ll*(a[l]+mod)%mod;
            ans = ans*1ll*(a[l+1]+mod)%mod;
            l+=2;
        }
        else{
            ans = ans*1ll*(a[r]+mod)%mod;
            ans = ans*1ll*(a[r-1]+mod)%mod;   
            r-=2;
        }
        k-=2;
    }
    printf("%lld\n", ans);
}