缓坡（adif）

题目描述

Y 同学要铺一条长度为 $n$ 的缓坡，第 $i$ 段的高度为 $b_i$。每段高度必须是 $1$ 到 $m$ 之间的整数，并且相邻两段高度差不能超过 $d$：

现在给出数组 $a$。若 $a_i=0$，表示第 $i$ 段高度尚未确定；若 $a_i>0$，则必须令 $b_i=a_i$。请计算有多少种合法的缓坡方案，答案对 $998244353$ 取模。

输入格式

第一行包含三个整数 $n,m,d$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数，表示合法方案数。

样例

样例输入 #1

5 4 1
0 2 0 0 3

样例输出 #1

18

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le 5000$，$0\le d<m$，$0\le a_i\le m$。