题目描述

$1,\dots,\ n$ と $-1$ からなる数列 $a_1,\dots,a_n$ と整数 $d$ が与えられます。 以下の条件を満たす数列 $p_1,\dots,p_n$ はいくつありますか？ 答えを $998244353$ で割ったあまりを出力してください。

• $p_1,\dots,p_n$ は $1,\dots,\ n$ の順列
• $i=1,\dots,n$ について、 $a_i\neq\ -1$ ならば $a_i=p_i$ （つまり、$a_1,\dots,a_n$ の $-1$ の項を適切に置き換えることで $p_1,\dots,p_n$ に書き換えできる）
• $i=1,\dots,n$ について、 $|p_i\ -\ i|\le\ d$

输入格式

入力は以下の形式で標準入力から与えられる。

$n$ $d$ $a_1$ $\dots$ $a_n$

输出格式

条件を満たす数列の数を $998244353$ で割ったあまりを出力せよ。

题目大意

给定一个长度为 $n$ 的数字序列 $A$，由 $1$ 到 $n$ 之间的整数和 $-1$ 组成。还有一个整数 $d$。

现在要对这个序列进行变换，将 $A$ 中所有为 $-1$ 的 $a_i$ 替换成一个数字，使得得到的序列 $P$，满足：

• $\forall a_i \ne -1,p_i = a_i$。
• $P$ 是 $1$ 到 $n$ 的一个排列。
• $\forall |p_i-i| \leq d$

试问有多少种这样的排列 $P$。答案对 $998244353$ 取膜。

4 2
3 -1 1 -1

2

5 1
2 3 4 5 -1

0

16 5
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

794673086

提示

制約

• $1\ \le\ d\ \le\ 5$
• $d\ <\ n\ \le\ 500$
• $1\le\ a_i\ \le\ n$ または $a_i=-1$
• $a_i\neq\ -1$ ならば $|a_i-i|\le\ d$
• $i\neq\ j$ かつ $a_i,\ a_j\ \neq\ -1$ ならば $a_i\neq\ a_j$
• 入力はすべて整数

Sample Explanation 1

$(3,2,1,4)$ と $(3,4,1,2)$ が条件を満たします。

Sample Explanation 2

$-1$ を置き換えて得られる $1,2,3,4,5$ の順列は $(2,3,4,5,1)$ のみです。 この順列は、$5$ 項目が条件を満たさないため、答えは $0$ です。

Sample Explanation 3

$998244353$ で割ったあまりを出力してください。