Description

Unfortunately, this tree has not grown up yet, and it only has a root node $1$.

Cirno only knows that this tree will have $n$ nodes, with $a_1,a_2,\ldots,a_n$ fruits on them respectively, but she cannot know the shape of the tree.

However, the growth of the tree always follows some pattern.

For node $i$, it will choose a node uniformly at random from $[i-k,i-1] \cap N^+$ to connect to, and become a child of that node.

Here, $k$ is a constant that Cirno has already measured.

To pick all the fruits, after the tree has grown, Cirno will use magic multiple times. Each time, she chooses a connected subgraph (a connected component) on the tree, and picks one fruit from every node in that connected component (it must be guaranteed that every node in the connected component has at least one fruit).

Obviously, Cirno will use the best strategy to minimize the number of times she uses magic.

Now, Cirno already knows $n$, $k$, and the number of fruits $a_i$ that will grow on each node. Please help her compute the expected value of the minimum number of magic uses. For simplicity, you only need to output the remainder of the answer modulo $998244353$.

Input Format

The first line contains two integers $n$ and $k$, as described above.

The second line contains $n$ integers, denoting $a_1,a_2,\cdots,a_n$.

Output Format

Output one line with one integer, denoting the answer.

3 2
2 1 3

499122180

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

553073655

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

180853894

Hint

Explanation of Sample 1.

There are two possible trees as follows (black is the node index, red is the number of fruits on the node):

The best plan is to use magic once on connected component $\{1,2,3\}$ and once on $\{1\}$, and use it twice on $\{3\}$, for a total of $4$ times.

The best plan is to use magic once on each of the connected components $\{1,2,3\}$, $\{1,3\}$, and $\{3\}$, for a total of $3$ times.

So the answer is $\frac{7}{2}\equiv 499122180\pmod{998244353}$.

Constraints and Notes

For $100\%$ of the testdata, it is guaranteed that $1\le k<n\le 10^6$ and $0\le a_i<998244353$.

Subtasks (This problem uses bundled tests.)

• Subtask 1 ($10\%$): $k=1$.
• Subtask 2 ($10\%$): $n \le 10$, $a_i \in \{0,1\}$.
• Subtask 3 ($10\%$): $n \le 10$.
• Subtask 4 ($10\%$): $n \le 1000$.
• Subtask 5 ($60\%$): No additional constraints.

Translated by ChatGPT 5