Expected Minimum Magic Uses

Cirno has a tree that is still growing. Initially, the tree only has a root node labeled \(1\). She knows that eventually the tree will consist of \(n\) nodes, and node \(i\) will have \(a_i\) fruits. However, the shape of the tree is not known in advance.

The tree grows as follows. For each node \(i\) (for \(2\le i\le n\)), it will choose a parent uniformly at random among the nodes in the set \(\{i-k, i-k+1, \ldots, i-1\}\) that are positive (i.e. in \(\mathbb{N}^+\)). The edge from the chosen node to \(i\) is then added, making \(i\) a child of that parent.

After the tree has grown, Cirno uses magic several times to pick all the fruits. In each use of magic, she selects a connected component (with respect to the tree structure) and picks one fruit from every node in that component. The condition is that every node in the chosen component must have at least one fruit at the moment of picking. Cirno will adopt an optimal strategy so that the total number of times she uses magic is minimized.

It can be shown that the minimum number of magic uses required is given by

[ M = a_1+\sum_{i=2}^{n} \max\Bigl{0,,a_i-a_{p(i)}\Bigr}, ]

where \(p(i)\) is the parent of node \(i\). Since the parent of each node \(i\) is chosen uniformly at random in the range \([i-k,i-1]\), the expected minimum number of magic uses is

[ E = a_1+\sum_{i=2}^{n} \frac{1}{d_i} \sum_{j=\max(1,i-k)}^{i-1} \max{0,,a_i-a_j}, ]

where \(d_i=\min\{k,i-1\}\) is the number of possible parents for node \(i\). Since the answer is a rational number, you are required to output \(E\) modulo \(998244353\). More precisely, if the answer is a rational number \(\frac{P}{Q}\) where \(Q\) is coprime with \(998244353\), then you should output \(P\cdot Q^{-1}\) modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(k\) \((1\le k<n)\).

The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\) \((0\le a_i\le 10^9)\) representing the number of fruits on each node.

outputFormat

Output a single integer denoting the expected minimum number of magic uses modulo \(998244353\).

sample

3 2
3 5 2

5