配点 : $600$ 点

問題文

$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$

制約

• $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$
• 入力はすべて整数

入力

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

$n$ $d$

$a_1$ $\dots$ $a_n$

出力

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

4 2
3 -1 1 -1

2

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

5 1
2 3 4 5 -1

0

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

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

794673086

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