题目描述

本题题解已发表至 讨论区

前不久，在繁华的上海，国际大学生程序设计竞赛（ICPC）正在如火如荼地进行。来自全球各地的顶尖大学生们齐聚一堂，他们的目标是在一系列编程挑战中展现自己的智慧与技能。其中一道题差点导致我校ICPC上海酿成悲剧，现在看看你能否回到魂穿赛场快速解决这一道题，让我校参赛队伍前期的悲剧避免，考虑到一些客观因素我们对题目进行简化，题面如下：

给你一个数组其中包含 $n$ 个数字，其中有一个操作叫做：

$k$ 数连乘：

给定你一个数组，你可以选择以下操作至多一次：

选择恰好 $k$ 个数做乘法，在这个操作之后，参与操作的数将会消失，只有最终结果加入数组中。

你的目的是使得数组中最大值最大，但是考虑到这个数可能太大了，所以你只需要输出最大数在对 $998244353$ 取模之后的结果。

输入描述

第一行两个数字 $n, k$ 表示数组长度和一次操作的数量
$(1 \le n \le 2*10^5,1\le k \le n)$

第二行输入 $n$ 个数字，表示从 $a_1$ 到 $a_n$，其中 $(0 \le a_i \le 10^9)$

输出描述

输出一个数表示最后的结果。

示例 1

输入

3 3
2 2 0

输出

2

示例 2

输入

3 2
2 2 0

输出

4