Rainfall Wonderfulness

We are given a windowsill with n levels (numbered from 1 at the top to n at the bottom). Level i initially has (a_i) units of rainwater. At the next moment, the water on each level i is redistributed as follows:

For level (i), its (a_i) units of water is partitioned into nonnegative integers among the available targets: it may remain on level (i) or drip down to any of the levels (i+1, i+2, \dots, \min{i+k, n}). In other words, for level (i) one chooses nonnegative integers (b_{i,i+1}, b_{i,i+2}, \dots, b_{i,\min{i+k,n}}) so that (s_i = b_{i,i+1}+\cdots+b_{i,\min{i+k,n}}) is at most (a_i). The water that remains on level (i) is automatically (a_i - s_i).

After all levels make their choices, the final water amount on level (i) becomes [ a'i = \Bigl(a_i - \sum{j=i+1}^{\min{i+k,n}} b_{i,j}\Bigr) + \sum_{j=\max(1,i-k)}^{i-1} b_{j,i}, ] for (i=1,2,\dots,n) (note that for level 1 there is no incoming water from above). The overall "wondrousness" of the rain distribution is defined as [ W = \prod_{i=1}^n a'_i. ]

However, two "next moments" are considered essentially different if and only if there exists some pair (i < j) such that the amount of water dripping from level (i) to level (j) is different in the two configurations. That is, differences in the water that remain (on the same level) are ignored if the downward dripped amounts are identical.

Your task is: Given (n), (k) and the array (a_1,a_2,\dots,a_n), compute the sum of the wondrousness (W) over all essentially different next moments modulo (P=998244353).

Input Format:

• The first line contains two integers (n) and (k).
• The second line contains (n) integers: (a_1,a_2,\dots,a_n).

Output Format:

• Print a single integer: the sum of all (W) modulo (998244353).

Note: Two configurations are essentially different if there exists some pair (i < j) such that the chosen value of (b_{i,j}) differs.

Remark: You may assume that (n) and the values (a_i) are small enough to allow an exhaustive search (for example, (n \le 10) and small (a_i)).

inputFormat

The first line contains two integers \(n\) and \(k\). The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\).

outputFormat

Output a single integer representing the sum of the wondrousness over all essentially different next moments modulo \(998244353\).

sample

2 1
1 1

1