Description

不幸的是，这棵树尚未长成，只有一个根节点 $1$。

Cirno 只能知道这棵树将会有 $n$ 个结点，上面分别有 $a_1,a_2,\ldots,a_n$ 颗果实，却无法知道树的形状。

但是树的生长总是具有某种规律。

对于结点 $i$，它会等概率地从 $[i-k,i-1] \cap N^+$ 中选择一个结点连接，并成为那个节点的子节点。

其中，$k$ 是一个 Cirno 已经测出的常数。

为了摘下所有的果实，在树长成之后，Cirno 会多次使用魔法。其中每次会在树上选一个联通块，并从联通块内每个结点上摘取一个果子（必须保证该联通块内每个结点都有果子）。

显然，Cirno 会采取最佳策略使得使用魔法的次数最少。

现在，Cirno 已经知道了 $n$，$k$ 和每个结点将会长出的果子数 $a_i$，请你帮她计算出她最少使用的魔法次数的数学期望。为了简单起见，你只需要输出答案除以 $998244353$ 的余数。

Input Format

第一行输入两个整数 $n$，$k$，含义如上所述。

第二行输入 $n$ 个整数，表示 $a_1,a_2,\cdots,a_n$。

Output Format

输出一行一个整数，表示答案。

3 2
2 1 3

499122180

10 1
580461319 261515299 384092031 741339597 746815717 566875585 354719606 821499852 330315651 349091676

553073655

10 9
497873025 114058764 159468194 207476408 138162972 678927661 223886159 325207554 470061543 658861685

180853894

Hint

样例 1 解释：

可能长成的树有如下两种（黑色为结点编号，红色为结点上果子数）：

最佳方案是对联通块 $\{1,2,3\}$ 和 $\{1\}$ 各使用一次魔法，$\{3\}$ 使用两次，共四次。

最佳方案对联通块 $\{1,2,3\},\{1,3\}$ 和 $\{3\}$ 各使用一次魔法，共三次。

所以答案为 $\frac{7}{2}\equiv 499122180\pmod{998244353}$

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le k<n\le 10^6$，$0\le a_i<998244353$。

子任务「本题采用捆绑测试」

• Subtask1（$10\%$）: $k=1$。
• Subtask2（$10\%$）: $n \le 10$，$a_i \in \{0,1\}$。
• Subtask3（$10\%$）: $n \le 10$。
• Subtask4（$10\%$）: $n \le 1000$。
• Subtask5（$60\%$）: 无特殊限制。