解法
マイナスの個数に気を付けて貪欲にとる． 最初は 0 は除外して考えると楽． 今回は，0 を正に含めば大丈夫．
\(K\)個の積を 0 以上にできるかで場合分け． 0 以上に出来るときは abs が大きくなる様にとればよいし， 出来ないときは abs が小さくなる様にとればよい． 0 以上に出来るかどうかは，マイナスから2個ずつ選ぶ貪欲法で判定できる． 2個ずつペアにしていき，残った物を 0 以上から選べ場良い．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,k;
cin >> n >> k;
vll a(n); rep(i,n) { cin >> a[i]; }
vll ap, am;
rep(i,n){
if(a[i] >= 0) ap.push_back(a[i]);
else am.push_back(a[i]);
}
bool ok = false; // true iff (a から丁度 k個選んで，積を 0以上に出来る)
if(ap.size() > 0){
if(n == k) ok = (am.size()%2==0);
else ok = true;
}else {
ok = (k%2==0);
}
mint ans = 1;
ll x = min(k/2*2, (ll)am.size()/2*2); // 積を 0以上にできるかの判定は，マイナスから 2個ずつ貪欲にとれば良い．
assert(ok == (ap.size() >= k-x));
if(ok){
sort(all(ap));
sort(am.rbegin(), am.rend()); // sort(all(am), greater<ll>());
if(k%2) {
ans *= ap.back();
ap.pop_back(); // do not forget ... [*]
k--;
}
vll v;
rep(_,2){
while(ap.size() >= 2){
ll x = 1;
rep(_,2){
x *= ap.back();
ap.pop_back();
}
v.push_back(x);
}
swap(ap,am);
}
sort(all(v), greater<ll>());
rep(i,k/2){
ans *= v[i];
}
}else{
sort(all(a), [&](ll x, ll y){
return abs(x) < abs(y);
});
rep(i,k){
ans *= a[i];
}
}
cout << ans.val() << endl;
return 0;
}
// [*] を入れ忘れた場合の反例
// 5 5
// 1 2 3 -4 -5
