Problem Background

  “You claim this isn't my true strength, so why can't a single accidental wrong note ruin my fate?!”

  Tian Yi didn't notice that the person she was crying out to was just as close, holding an umbrella, only a dozen steps behind her.

  Qingming "What have you seen in the abyss of weakness"

Problem Description

Raindrops fall onto the window sills, one level after another.

There are a total of $n$ window sills, numbered from top to bottom, with the highest level numbered as $1$ and the lowest level numbered as $n$. Suppose at a certain moment, the $i$-th window sill has $a_i$ units of rainwater. Due to some peculiar physical reasons, the rainwater on the $i$-th level will drip to the $i+1, i+2, \dots, \min\{i+k, n\}$ levels in the "next moment," or it may stay on the $i$-th level, but the volume of rainwater in each direction should be a non-negative integer, and the sum should be $a_i$.

Let $a_i'$ be the amount of rainwater on the $i$-th window sill in the "next moment," then the peculiarity of the rainwater at this time is defined as $\prod_{i=1}^n a_i'$. Now, the sorrowful person wants to know the sum of the peculiarities of all distinct "next moments" modulo the prime number $P=998244353$.

Two "next moments" are considered distinct if and only if there exist two levels $i < j$ such that the volume of rainwater dripping from the $i$-th to the $j$-th window sill is different.

Input Format

The first line contains two positive integers $n, k$, representing the number of window sills and the constant that limits the distance rain can fall, respectively.

The second line contains $n$ non-negative integers $a_1, a_2, a_3, \cdots, a_n$, where $a_i$ represents the volume of rainwater on the $i$-th window sill at this moment.

Output Format

Output a single integer, which is the sum of the peculiarities of all distinct "next moments" modulo $P$.

Sample Input and Output

Input Sample #1

3 0
2 2 2

Output Sample #1

8

Input Sample #2

3 1
2 2 2

Output Sample #2

30

Input Sample #3

5 3
2 3 4 4 3

Output Sample #3

275200

Notes

Sample #1 Explanation

It is easy to find that there is only one distinct "next moment," where no rainwater drips from one window sill to another.

Thus, the final $a'=\{2,2,2\}$, with a value of $8$.

Sample #2 Explanation

Let $c_k$ represent the volume of rainwater dripping from the $k$-th to the $k+1$-th window sill, clearly $c_3=0$.

Enumerating all valid dripping scenarios:

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

Thus, the sum of the values for all distinct "next moments" is $8+6+0+6+6+4+0+0+0=30$.

Data Range and Constraints

This problem uses Subtask scoring.

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

For different subtasks, the following constraints apply:

见题面 Input 部分

见题面 Output 部分