题目描述

给定一个由 $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$ $a_2$ $\dots$ $a_n$

输出格式

请输出满足条件的数列个数对 $998244353$ 取模后的结果。

样例 1

输入

4 2
3 -1 1 -1

输出

2

样例 2

输入

5 1
2 3 4 5 -1

输出

0

样例 3

输入

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$
• 所有输入均为整数

样例解释 1

$(3,2,1,4)$ 和 $(3,4,1,2)$ 满足条件。

样例解释 2

将 $-1$ 替换后能得到的 $1,2,3,4,5$ 的排列只有 $(2,3,4,5,1)$。但该排列的第 $5$ 项不满足条件，因此答案为 $0$。

样例解释 3

请输出答案对 $998244353$ 取模后的结果。

由 ChatGPT 4.1 翻译