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 ll = long long;
using namespace std;

constexpr ll MOD = 1000000007;
ll f2(vector<ll> v, int K) {
  if (K & 1) sort(v.rbegin(), v.rend());
  else sort(v.begin(), v.end());
  ll res = 1;
  for (int i = 0; i < K; i++) {
    res *= v[i];
    res %= MOD;
  }
  if (res < 0) res += MOD;
  return res;
}

ll f1(vector<ll> v, int K) {
  const int n = v.size();
  vector<ll> p, m;
  for (int i = 0; i < n; i++) {
    if (v[i] >= 0) p.push_back(v[i]);
    else m.push_back(-v[i]);
  }
  sort(p.rbegin(), p.rend());
  sort(m.rbegin(), m.rend());
  int mcnt = 0;
  while (p.size() < K - mcnt) mcnt += 2;
  for (; mcnt + 2 <= m.size() && K - mcnt - 2 >= 0; mcnt += 2) {
    int pcnt = K - mcnt;
    if (p[pcnt-1] * p[pcnt-2] < m[mcnt] * m[mcnt+1]) continue;
    else break;
  }
  ll res = 1;
  for (int i = 0; i < mcnt; i++) {
    res *= m[i];
    res %= MOD;
  }
  for (int i = 0; i < K - mcnt; i++) {
    res *= p[i];
    res %= MOD;
  }
  return res;
}

int main() {
  int N, K; cin >> N >> K;
  vector<ll> v(N);
  for (int i = 0; i < N; i++) cin >> v[i];
  if (*max_element(v.begin(), v.end()) <= 0 || N == K) {
    cout << f2(v, K) << endl;
  } else {
    cout << f1(v, K) << endl;
  }
}
