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 rep(i, n) for (i = 0; i < n; i++)
#define int long long
using namespace std;

int mod = 1000000007;
int n, k;
int a[200000];
vector<int> sei;
vector<int> fu;

signed main() {
  int i;

  cin >> n >> k;
  rep(i, n) {
    cin >> a[i];
    if (a[i] >= 0)
      sei.push_back(a[i]);
    else
      fu.push_back(-a[i]);
  }

  if ((sei.size() == 0 && k % 2 == 1) || (n == k && fu.size() % 2 == 1)) {
    sort(fu.begin(), fu.end());
    int ans = 1;
    rep(i, min((int)fu.size(), k)) {
      ans *= fu[i];
      ans %= mod;
    }
    rep(i, max(0LL, k - (int)fu.size())) {
      ans *= sei[i];
      ans %= mod;
    }
    cout << (mod - ans) % mod << endl;
    return 0;
  }

  sort(sei.begin(), sei.end(), greater<int>());
  sort(fu.begin(), fu.end(), greater<int>());

  int ans = 1;
  if (k % 2 == 1) {
    ans *= sei[0];
  }

  vector<int> vec;
  for (i = k % 2; i + 1 < sei.size(); i += 2) {
    vec.push_back(sei[i] * sei[i + 1]);
  }
  for (i = 0; i + 1 < fu.size(); i += 2) {
    vec.push_back(fu[i] * fu[i + 1]);
  }
  sort(vec.begin(), vec.end(), greater<int>());

  rep(i, k / 2) {
    int res = vec[i] % mod;
    ans *= res;
    ans %= mod;
  }
  cout << ans << endl;
  return 0;
}
