[Cnoi2020]梦原

题目背景

> 成熟是一种明亮而不刺眼的光辉,一种圆润而不腻耳的音响,一种不再需要对别人察言观色的从容,一种终于停止向周围申述求告的大气,一种不理会哄闹的微笑,一种洗刷了偏激的淡漠,一种无须声张的厚实,一种并不陡峭的高度。勃郁的豪情发过了酵,尖利的山风收住了劲,湍急的溪流汇成了湖。 ——余秋雨《文化苦旅》 在一个偶然的梦境中,Cirno 发现了一棵树,在一望无际的昏暗平原上,发出了淡淡的蓝色荧光。 Here lies $\ \ \ \ \ \ \ \ \ $.

题目描述

不幸的是,这棵树尚未长成,只有一个根节点 $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$ 的余数。

输入输出格式

输入格式


第一行输入两个整数 $n$,$k$,含义如上所述。 第二行输入 $n$ 个整数,表示 $a_1,a_2,\cdots,a_n$。

输出格式


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

输入输出样例

输入样例 #1

3 2
2 1 3

输出样例 #1

499122180

输入样例 #2

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

输出样例 #2

553073655

输入样例 #3

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

输出样例 #3

180853894

说明

## 样例 1 解释: 可能长成的树有如下两种(黑色为结点编号,红色为结点上果子数): ![](https://cdn.luogu.com.cn/upload/image_hosting/9vpdxwme.png) 最佳方案是对联通块 $\{1,2,3\}$ 和 $\{1\}$ 各使用一次魔法,$\{3\}$ 使用两次,共四次。 ![](https://cdn.luogu.com.cn/upload/image_hosting/nnbwq0af.png) 最佳方案对联通块 $\{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\%$): 无特殊限制。