题目描述

高桥君的仓库里有 $N$ 瓶葡萄酒，按左右方向排成一列。从左边数第 $i$ 瓶葡萄酒的美味度为 $A_i$。
青木君现在要从这 $N$ 瓶葡萄酒中，恰好选出 $K$ 瓶进行偷窃。但是，高桥君非常警觉，如果满足以下条件，他就会发现被偷了：

• 存在连续排列的 $D$ 瓶葡萄酒，其中被偷走的有 $2$ 瓶或以上。

请你求出所有不会被高桥君发现的偷窃方案中，偷走的葡萄酒美味度之和的总和。
由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入格式

输入以如下格式从标准输入给出：

$N$ $K$ $D$ $A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

输出答案对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

4 2 2
1 4 2 3

输出 #1

14

输入输出样例 #2

输入 #2

5 2 3
1 5 7 7 3

输出 #2

20

输入输出样例 #3

输入 #3

18 4 4
107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467

输出 #3

228955567

说明/提示

约束条件

• $2 \leq D \leq N \leq 10^6$
• $1 \leq K \leq \left\lceil \frac{N}{D} \right\rceil$（$\left\lceil x \right\rceil$ 表示不小于 $x$ 的最小整数）
• $1 \leq A_i < 998244353$
• 输入中的所有值均为整数

样例解释 1

偷窃方案及其美味度之和如下：

• 偷第 $1$ 瓶和第 $3$ 瓶：美味度之和为 $1 + 2 = 3$
• 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 3 = 4$
• 偷第 $2$ 瓶和第 $4$ 瓶：美味度之和为 $4 + 3 = 7$
  因此答案为 $3 + 4 + 7 = 14$。

样例解释 2

偷窃方案及其美味度之和如下：

• 偷第 $1$ 瓶和第 $4$ 瓶：美味度之和为 $1 + 7 = 8$
• 偷第 $1$ 瓶和第 $5$ 瓶：美味度之和为 $1 + 3 = 4$
• 偷第 $2$ 瓶和第 $5$ 瓶：美味度之和为 $5 + 3 = 8$