Problem Statement

Problems F and F2 have the same Problem Statement but different Constraints and Time Limits.

There are $N$ bottles of wine in Takahashi's cellar, arranged in a row from left to right. The tastiness of the $i$-th bottle from the left is $A_i$. Aoki will choose $K$ bottles from these $N$ and steal them. However, Takahashi is careful enough to notice the theft if the following condition is satisfied:

• There exist $D$ consecutive bottles such that two or more of them are stolen.

For every way of stealing bottles without getting noticed by Takahashi, find the total tastiness of the bottles stolen, and then find the sum of all those values. Since the sum can be enormous, print it modulo $998244353$.

Constraints

• $2 \le D \le N \le 10^6$
• $1 \le K \le \left\lceil \frac{N}{D} \right\rceil$ ($\left\lceil x \right\rceil$ represents the smallest integer not less than $x$.)
• $1 \le A_i \lt 998244353$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K D
A_1 A_2 A_3 \dots A_N

Output

Print the sum modulo $998244353$.