CF2154F1 Bombing (Easy Version)

这是本题的简单版本。不同版本的区别在于本版本中 $n \leq 3000$。只有当你解决了所有版本的问题后，才可以进行 hack。 如果一个排列 $b$ 是排列 $a$ 的一次 “riffle shuffle”，需要满足 $|a| = |b|$，并且存在一个 $k$，$1 \leq k < |a|$，使得 $a_1,a_2,\ldots,a_k$ 和 $a_{k+1},a_{k+2},\ldots,a_{|a|}$ 都是 $b$ 的子序列。 例如，$[\color{red}{1}, \color{blue}{4}, \color{blue}{5}, \color{red}{2}, \color{red}{3}, \color{blue}{6}]$ 是 $[\color{red}{1}, \color{red}{2}, \color{red}{3}, \color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ 的一次 riffle shuffle，因为我们可以选 $k = 3$，且 $[\color{red}{1}, \color{red}{2}, \color{red}{3}]$ 和 $[\color{blue}{4}, \color{blue}{5}, \color{blue}{6}]$ 都是子序列。 给定一个长度为 $n$ 的排列 $p$，其中有些位置被替换为 $-1$。请你计算有多少种方式将每个 $-1$ 替换为一个整数，使得 $p$ 变成 $[1,2,\ldots,n]$（即升序排列）的一个 riffle shuffle。 由于方案数可能非常大，请你输出其对 $998\,244\,353$ 取模的结果。 $^*$ 一个长度为 $n$ 的排列是由 $1$ 到 $n$ 的 $n$ 个互不相同的整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是（$2$ 出现了两次），$[1,3,4]$ 也不是（$n=3$，但出现了 $4$）。 $^\dagger$ 如果一个序列 $c$ 能通过从另一个序列 $d$ 删除若干（可以为零或全部）元素而得到，那么称 $c$ 是 $d$ 的子序列。

每个测试用例包含多组数据。第一行为测试用例个数 $t$（$1 \leq t \leq 100$）。下接每组测试数据。 每组测试数据第一行为排列的长度 $n$（$2 \leq n \leq 3000$）。 第二行为 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$ 或 $p_i = -1$）——排列 $p$ 的元素。所有非 $-1$ 的 $p_i$ 两两不相同。 所有测试用例中 $n$ 的总和不超过 $3000$。

对于每个测试用例，输出一个整数，表示将 $p$ 填补为 $[1,2,\ldots,n]$ 的一次 riffle shuffle 的方案数，对 $998\,244\,353$ 取模。

第三个测试用例可能的排列如下： - $[\color{red}1, \color{blue}3, \color{blue}4, \color{red}2, \color{blue}5]$， - $[\color{red}1, \color{blue}4, \color{blue}5, \color{red}2, \color{red}3]$， - $[\color{blue}3, \color{red}1, \color{blue}4, \color{red}2, \color{blue}5]$， - $[\color{blue}3, \color{blue}4, \color{red}1, \color{red}2, \color{blue}5]$， - $[\color{blue}4, \color{red}1, \color{blue}5, \color{red}2, \color{red}3]$， - $[\color{blue}4, \color{blue}5, \color{red}1, \color{red}2, \color{red}3]$。 由 ChatGPT 5 翻译