cats 的凸包计算

Problem Description

定义一个排列 $p_1,p_2,\cdots,p_n$ 的面积为：将排列中的每个数 $p_i$ 看做二维坐标平面上的一个点 $(i,p_i)$，这 $n$ 个点的凸包的面积。 现在 cats 有一个长为 $n$ 的数组 $a_1,a_2,\cdots,a_n$，其中每个数均为一个 $1$ 到 $n$ 之间的正整数或 $-1$。你需要求出将所有 $-1$ 替换成 $1$ 到 $n$ 之间的正整数后，形成的所有排列的面积之和对 $10^9+7$ 取模的结果。 可以证明答案一定可以被表示为一个有理数 $\frac{x}{y}$。其中 $x$ 与 $y$ 互质。你需要输出 $x \cdot y^{-1} \bmod (10^9+7)$。可以证明 $(10^9+7) \nmid y$。 注1：一个长为 $n$ 的数组 $p_1,p_2,\cdots p_n$ 是一个排列，当且仅当 $1$ 到 $n$ 之间的每一个正整数都在 $p_1,p_2,\cdots p_n$ 中出现且仅出现一次。 注2：$n$ 个点 $(x_1,y_1),(x_2,y_2),\cdots,(x_n,y_n)$ 的凸包为：所有满足存在 $n$ 个范围在 $[0,1]$ 之间的实数 $w_1,w_2,\cdots,w_n$ ，使得 $\sum_{i=1}^n w_i =1$，$\sum_{i=1}^n w_i\cdot x_i =x$，$\sum_{i=1}^n w_i\cdot y_i =y$ 的点 $(x,y)$ 在二维坐标平面上组成的图形。

Input

第一行包含一个整数 $T$ $(1\leq T \leq 1000)$，表示一共有 $T$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$ $(1\leq n\leq 50)$，表示数组 $a$ 的长度。 每组测试数据的第二行包含 $n$ 个整数 $a_1,a_2,\cdots a_n$ $(-1\leq a_i\leq n,a_i\neq 0)$，表示数组 $a$。 保证对于任意的 $1\leq i< j\leq n$，若 $a_i$ 和 $a_j$ 均不为 $-1$，则 $a_i \neq a_j$。 保证所有测试数据的 $n^3$ 之和不超过 $5\cdot 10^5$。

Output

对于每组测试数据，输出一个整数，表示形成的所有排列的面积之和对 $10^9+7$ 取模的结果。

Sample Input

5
3
1 2 3
4
2 -1 -1 3
4
1 2 -1 3
1
1
7
-1 -1 -1 -1 -1 -1 -1

Sample Output

0
9
500000006
0
99546

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）