{"raw_statement":[{"iden":"problem statement","content":"**Problems F and F2 have the same Problem Statement but different Constraints and Time Limits.**\nThere are $N$ bottles of wine in Takahashi's cellar, arranged in a row from left to right.  \nThe tastiness of the $i$\\-th bottle from the left is $A_i$.  \nAoki 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:\n\n*   There exist $D$ consecutive bottles such that two or more of them are stolen.\n\nFor 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.  \nSince the sum can be enormous, print it modulo $998244353$."},{"iden":"constraints","content":"*   $2 \\le D \\le N \\le 10^6$\n*   $1 \\le K \\le \\left\\lceil \\frac{N}{D} \\right\\rceil$ ($\\left\\lceil x \\right\\rceil$ represents the smallest integer not less than $x$.)\n*   $1 \\le A_i \\lt 998244353$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$ $D$\n$A_1$ $A_2$ $A_3$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"4 2 2\n1 4 2 3"},{"iden":"sample output 1","content":"14\n\nThe possible ways to steal bottles and the total tastiness for each of them are as follows:\n\n*   Steal the $1$\\-st and $3$\\-rd bottles from the left, for the total tastiness of $1 + 2 = 3$.\n*   Steal the $1$\\-st and $4$\\-th bottles from the left, for the total tastiness of $1 + 3 = 4$.\n*   Steal the $2$\\-nd and $4$\\-th bottles from the left, for the total tastiness of $4 + 3 = 7$.\n\nThus, the answer is $3 + 4 + 7 = 14$."},{"iden":"sample input 2","content":"5 2 3\n1 5 7 7 3"},{"iden":"sample output 2","content":"20\n\nThe possible ways to steal bottles and the total tastiness for each of them are as follows:\n\n*   Steal the $1$\\-st and $4$\\-th bottles from the left, for the total tastiness of $1 + 7 = 8$.\n*   Steal the $1$\\-st and $5$\\-th bottles from the left, for the total tastiness of $1 + 3 = 4$.\n*   Steal the $2$\\-nd and $5$\\-th bottles from the left, for the total tastiness of $5 + 3 = 8$."},{"iden":"sample input 3","content":"18 4 4\n107367523 266126484 149762920 57456082 857431610 400422663 768881284 494753774 152155823 740238343 871191740 450057094 208762450 787961742 90197530 77329823 193815114 707323467"},{"iden":"sample output 3","content":"228955567"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}