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
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (ll &e : a)
        cin >> e;
    sort(a.begin(), a.end());
    ll p = 1;
    if (a[n - 1] == 0 && (k & 1))
        p = 0;
    else if (a[n - 1] <= 0 && (k & 1))
        for (ll i = n - 1; i >= n - k; i--)
            p = p * a[i] % M;
    else
    {

        ll i = 0, j = n - 1;
        if (k & 1)
        {
            p = p * a[j] % M;
            j--;
            k--;
        }
        k >>= 1;
        for (ll itr = 0; itr < k; itr++)
        {
            ll lp = a[i] * a[i + 1];
            ll rp = a[j] * a[j - 1];
            if (lp > rp)
            {
                lp %= M;
                p = p * lp % M;
                i += 2;
            }
            else
            {
                rp %= M;
                p = p * rp % M;
                j -= 2;
            }
        }
    }
    cout << (p + 99 * M) % M;
}