CF2084E Blossom

给定一个长度为 $n$ 的排列 $a$ $^{\text{∗}}$，其中部分元素缺失（用 $-1$ 表示）。 定义一个排列的值为其所有非空子段 $^{\text{‡}}$ 的 MEX $^{\text{†}}$ 之和。 求所有可能通过填充 $a$ 中缺失元素形成的有效排列的值的总和，结果对 $10^9 + 7$ 取模。 $^{\text{∗}}$ 长度为 $n$ 的排列是指由 $0$ 到 $n - 1$ 的 $n$ 个不同整数按任意顺序组成的数组。例如，$[1,2,0,4,3]$ 是一个排列，但 $[0,1,1]$ 不是排列（因为 $1$ 在数组中出现了两次），$[0,2,3]$ 也不是排列（因为 $n=3$ 但数组中包含 $3$）。 $^{\text{†}}$ 整数集合 $c = \{c_1, c_2, \ldots, c_k\}$ 的最小排除值（MEX）定义为不包含在 $c$ 中的最小非负整数 $x$。 $^{\text{‡}}$ 序列 $a$ 是序列 $b$ 的子段，当且仅当 $a$ 可以通过从 $b$ 的开头和结尾删除若干（可能为零或全部）元素得到。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i < n$）。 保证 $a$ 中非 $-1$ 的元素互不相同。 保证所有测试用例的 $n$ 之和不超过 $5000$。

对于每个测试用例，输出一个整数——所有可能有效排列的值的总和对 $10^9 + 7$ 取模的结果。

- 在第一个测试用例中，唯一有效的排列是 $[0, 1]$，其值为 $3$，因为： $$ \operatorname{mex}([0]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 1]) = 1 + 0 + 2 = 3 $$ 因此答案为 $3$。 - 在第二个测试用例中，有两个有效排列：$[0, 1]$ 和 $[1, 0]$。$[0, 1]$ 和 $[1, 0]$ 的值均为 $3$，因此答案为 $3 + 3 = 6$。 - 在第四个测试用例中，有两个有效排列：$[0, 2, 1]$ 和 $[1, 2, 0]$。$[0, 2, 1]$ 的值为 $5$，因为： $$ \operatorname{mex}([0]) + \operatorname{mex}([2]) + \operatorname{mex}([1]) + \operatorname{mex}([0, 2]) + \operatorname{mex}([2, 1]) + \operatorname{mex}([0, 2, 1]) = 1 + 0 + 0 + 1 + 0 + 3 = 5 $$ $[1, 2, 0]$ 的值也为 $5$，因为： $$ \operatorname{mex}([1]) + \operatorname{mex}([2]) + \operatorname{mex}([0]) + \operatorname{mex}([1, 2]) + \operatorname{mex}([2, 0]) + \operatorname{mex}([1, 2, 0]) = 0 + 0 + 1 + 0 + 1 + 3 = 5 $$ 因此答案为 $5 + 5 = 10$。 翻译由 DeepSeek V3 完成