Background

  "       ，       "

  "You keep saying this is not my true strength, so why can't one accidental wrong note ruin my fate?!"

  Tianyi did not notice that the person she was crying out to in her heart, like her, was holding an umbrella, only a dozen steps behind her.

  Qingming "In the abyss called weakness, what have you actually seen?"

Problem Description

Raindrops hit the window ledges, falling down step by step.

There are $n$ window ledges in total, numbered from top to bottom. The highest ledge is numbered $1$, and the lowest ledge is numbered $n$. Suppose that at some instant, there are $a_i$ units of rainwater on ledge $i$. Due to some magical physical reasons, the rainwater on ledge $i$ will, in the "next instant", drip to ledges $i+1,i+2,\dots,\min\{i+k,n\}$, or it may stay on ledge $i$. For each possible destination, the amount of water (in units of volume) must be a non-negative integer, and the total must be $a_i$.

Let $a_i'$ be the amount of rainwater on ledge $i$ in the "next instant". Then the magic value of the rainwater at that time is defined as $\prod_{i=1}^n a_i'$. Now, the sad person wants to know: among all essentially different "next instants", what is the sum of the magic values modulo the prime $P=998244353$?

Two "next instants" are essentially different if and only if there exist two ledges with indices $i<j$ such that the amount of water dripping from ledge $i$ to ledge $j$ is different.

Input Format

The first line contains two positive integers $n,k$, representing the number of window ledges and the constant that limits the dripping distance.

The second line contains $n$ non-negative integers $a_1,a_2,a_3,\cdots,a_n$, where $a_i$ is the volume of rainwater on ledge $i$ at the current instant.

Output Format

Output one integer in one line, representing the sum of the magic values over all essentially different "next instants", taken modulo $P$.

3 0
2 2 2

8

3 1
2 2 2

30

5 3
2 3 4 4 3

275200

Hint

Sample #1 Explanation.

It is easy to see that there is only one essentially different "next instant": no ledge drips any water to other ledges.

So finally $a'=\{2,2,2\}$, and the value is $8$.

Sample #2 Explanation.

Let $c_k$ denote the volume of rain dripping from ledge $k$ to ledge $k+1$. Clearly, $c_3=0$.

Enumerate all valid dripping situations:

• $c=\{0,0,0\},b=\{2,2,2\}$, value $8$;
• $c=\{0,1,0\},b=\{2,1,3\}$, value $6$;
• $c=\{0,2,0\},b=\{2,0,4\}$, value $0$;
• $c=\{1,0,0\},b=\{1,3,2\}$, value $6$;
• $c=\{1,1,0\},b=\{1,2,3\}$, value $6$;
• $c=\{1,2,0\},b=\{1,1,4\}$, value $4$;
• $c_1=2$. In this case, $b_1=0$ must hold, and the values of the three plans in this case are all $0$.

Therefore, the total sum of values over all essentially different "next instants" is $8+6+0+6+6+4+0+0+0=30$.

Constraints

This problem uses Subtask-based scoring.

For $100\%$ of the testdata, $0\le k<n\le 32$, and $0\le a_i<P$.

For different subtasks, the constraints are as follows:

Translated by ChatGPT 5