E. 绽放
时间限制：每个测试点 4 秒
内存限制：512 兆字节

---

题目描述

给定一个长度为 $n$ 的排列 $a$，其中一些元素缺失，用 $-1$ 表示。

定义一个排列的值为它的所有非空子段的 $\operatorname{mex}$ 之和。

求将 $a$ 中缺失的元素用合法值填充后，能得到的所有有效排列的值的总和，结果对 $10^9+7$ 取模。

---

注：

• 长度为 $n$ 的排列是指由 $0$ 到 $n-1$ 的 $n$ 个整数组成的数组，每个整数恰好出现一次。例如 $[1,2,0,4,3]$ 是一个排列，但 $[0,1,1]$ 不是（$1$ 出现两次），$[0,2,3]$ 也不是（$n=3$ 却有 $3$）。
• $\operatorname{mex}(c)$ 表示集合 $c$ 中未出现的最小非负整数。
• 子段是指原序列中连续的一段（通过删除开头和结尾若干元素得到）。

---

输入格式

每个测试文件包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。

接下来每个测试用例：

• 第一行包含一个整数 $n$（$1 \le n \le 5000$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i < n$）。

数据保证 $a$ 中不为 $-1$ 的元素互不相同。
所有测试用例的 $n$ 之和不超过 $5000$。

---

输出格式

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

---

示例

输入

5
2
0 -1
2
-1 -1
3
2 0 1
3
-1 2 -1
5
-1 0 -1 2 -1

输出

3
6
7
10
104

---

样例解释

第一个测试用例：唯一有效排列是 $[0,1]$，它的值为：

$$\operatorname{mex}([0]) + \operatorname{mex}([1]) + \operatorname{mex}([0,1]) = 1 + 0 + 2 = 3 $$

答案为 $3$。

第二个测试用例：有两个有效排列 $[0,1]$ 和 $[1,0]$，它们的值均为 $3$，答案为 $3+3=6$。

第四个测试用例：有两个有效排列 $[0,2,1]$ 和 $[1,2,0]$，它们的值均为 $5$，答案为 $5+5=10$。

其中 $[0,2,1]$ 的值计算如下：

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