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;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false);

//  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);

    int n, k, answ = 1, mod = 1000000007;
    cin >> n >> k;

    int a[n], l = 0, r = n-1;
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a+n);

    if(a[n-1] == 0 && k%2) {
        cout << 0;
        return 0;
    }
    else if(a[n-1] < 0 && k%2) {
        while(k)
            answ = ((answ%mod) * (a[r]%mod))%mod, k--, r--;
        cout << mod+answ;
        return 0;
    }
    else if(k%2)
        k--, answ = a[r], r--;

    while(k) {
        k -= 2;
        int p1 = a[l] * a[l+1], p2 = a[r] * a[r-1];
        if(p1 > p2)
            l += 2, answ = ((answ%mod) * (p1%mod))%mod;
        else
            r -= 2, answ = ((answ%mod) * (p2%mod))%mod;
    }

    cout << (answ>=0?answ:mod+answ);

    return 0;
}
