P6834 [Cnoi2020] Dream Origin

> Maturity is a bright yet not dazzling glow, a mellow yet not harsh sound, a calmness that no longer needs to read other people’s faces, a broad-mindedness that finally stops explaining and begging to the surroundings, a smile that ignores the noise, a plainness washed clean of extremes, a solidness that needs no publicity, and a height that is not steep. Passion has finished fermenting, the sharp mountain wind has eased its force, and the rushing stream has gathered into a lake. — Yu Qiuyu, *Cultural Journeys* In an accidental dream, Cirno discovered a tree. On an endless dim plain, it emitted a faint blue glow. Here lies $\ \ \ \ \ \ \ \ \ \ $.

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$.

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 one line with one integer, denoting the answer.

## 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