Problem Background

Maturity is a bright yet non-dazzling radiance, a mellow and non-cloying sound, a composure that no longer requires observing others' expressions, a magnanimity that finally ceases to plead with the surroundings, a smile indifferent to the hubbub, a calmness that has washed away extremism, a solidity that needs no loud proclamation, and a height that is not steep. The exuberant passion has fermented, the sharp mountain wind has tempered its force, and the turbulent stream has converged into a lake.
—Yu Qiuyu, "Cultural苦旅"

In an accidental dream, Cirno discovered a tree, glowing faintly blue in the endless dark plain.

Here lies $\ \ \ \ \ \ \ \ \$.

Problem Description

Unfortunately, this tree is not yet fully grown, with only a root node $1$.

Cirno knows that the tree will have $n$ nodes, each bearing $a_1, a_2, \ldots, a_n$ fruits, but she cannot determine the shape of the tree.

However, the growth of the tree always follows certain rules.

For node $i$, it will randomly connect to a node in $[i-k, i-1] \cap \mathbb{N}^+$ and become its child node.

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

To harvest all the fruits, after the tree has grown, Cirno will use magic multiple times. Each time, she will select a connected component in the tree and pick one fruit from each node in that component (ensuring that every node in the component has a fruit).

Clearly, Cirno will adopt the optimal strategy to minimize the number of magic uses.

Now, Cirno has obtained $n$, $k$, and the number of fruits $a_i$ that each node will bear. Please help her calculate the mathematical expectation of the minimum number of magic uses. For simplicity, you only need to output the answer modulo $998244353$.

Input Format

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

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

Output Format

Output a single integer, representing the answer.

Sample Input and Output

Sample Input #1

3 2
2 1 3

Sample Output #1

499122180

Sample Input #2

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

Sample Output #2

553073655

Sample Input #3

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

Sample Output #3

180853894

Notes

Sample 1 Explanation:

Possible trees that could grow are as follows (black numbers are node IDs, red numbers are fruit counts):

The optimal strategy is to use magic once on the connected component $\{1, 2, 3\}$ and once on $\{1\}$, and twice on $\{3\}$, totaling four uses.

The optimal strategy is to use magic once on the connected components $\{1, 2, 3\}$, $\{1, 3\}$, and $\{3\}$, totaling three uses.

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

Data Range and Constraints

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

Subtasks (Bundled Testing)

• Subtask1 ($10\%$): $k = 1$.
• Subtask2 ($10\%$): $n \le 10$, $a_i \in \{0, 1\}$.
• Subtask3 ($10\%$): $n \le 10$.
• Subtask4 ($10\%$): $n \le 1000$.
• Subtask5 ($60\%$): No special restrictions.

见题面 Input 部分

见题面 Output 部分