A12349 | Vasya and Array

Vasya has got an array consisting of $n$ integers, and two integers $k$ and $len$ in addition. All numbers in the array are either between $1$ and $k$ (inclusive), or equal to $-1$ . The array is good if there is no segment of $len$ consecutive equal numbers.

Vasya will replace each $-1$ with some number from $1$ to $k$ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $998244353$ .

The first line contains three integers $n, k$ and $len$ ( $1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n$ ).

The second line contains $n$ numbers — the array. Each number is either $-1$ or between $1$ and $k$ (inclusive).

Print one integer — the number of ways to replace each $-1$ with some number from $1$ to $k$ (inclusive) so the array is good. The answer may be large, so print it modulo $998244353$ .