P8807 - [ARC120F2] Wine Thief

Problem

P8807[ARC120F2] Wine Thief

Limits : Time Limit : - MS Memory Limit : 524288 KB

Judgment Tips : 10s,512MB

Description

\(N\) 瓶酒排成一行， \(i\) 瓶价值 \(A_i\) 。小偷要偷恰好 \(K\) 瓶，任意连续 \(D\) 瓶至多偷 \(1\) 瓶，求所有偷取方案的价值总和的总和 \(\bmod 998\;244\;353\) 。

Input Format

第一行 \(N,K,D\) 。

第二行 \(A_1,\cdots,A_N\) 。

Output Format

一个整数答案。

Sample Input 1

4 2 2
1 4 2 3

Sample Output 1

Sample Input 2

5 2 3
1 5 7 7 3

Sample Output 2

Sample Input 3

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

Sample Output 3

228955567

Hint

样例1解释

偷第 \(1,3\) 瓶，价值总和为 \(3\)
偷第 \(1,4\) 瓶，价值总和为 \(4\)
偷第 \(2,4\) 瓶，价值总和为 \(7\)

样例2解释

偷第 \(1,4\) 瓶，价值总和为 \(8\)
偷第 \(1,5\) 瓶，价值总和为 \(4\)
偷第 \(2,5\) 瓶，价值总和为 \(8\)

数据范围

\(2\leq D\leq N\leq 10^6\)
\(K\leq \lceil \frac ND\rceil\)
\(1\leq A_i\lt 998\;244\;353\)