Anti-median (Easy Version)

题意翻译

- 一个排列是好的，当且仅当对于所有正整数 $m$ 都满足所有长度为 $2m+1$ 的子串的**中位数**不在第 $m+1$ 个。 - 给定一个一些数被替换成 $-1$ 的排列，你需要将 $-1$ 填入所有可能的值后，统计好的排列数量。 - 答案对 $10^9+7$ 取模。 - 多测，$\sum n^2\leq 10^6$。

题目描述

This is the easy version of the problem. The only difference between the two versions is the constraint on $ n $ . You can make hacks only if all versions of the problem are solved. Let's call an array $ a $ of odd length $ 2m+1 $ (with $ m \ge 1 $ ) bad, if element $ a_{m+1} $ is equal to the median of this array. In other words, the array is bad if, after sorting it, the element at $ m+1 $ -st position remains the same. Let's call a permutation $ p $ of integers from $ 1 $ to $ n $ anti-median, if every its subarray of odd length $ \ge 3 $ is not bad. You are already given values of some elements of the permutation. Find the number of ways to set unknown values to obtain an anti-median permutation. As this number can be very large, find it modulo $ 10^9+7 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ $ (2 \le n \le 1000) $ — the length of the permutation. The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ , or $ p_i = -1 $ ) — the elements of the permutation. If $ p_i \neq -1 $ , it's given, else it's unknown. It's guaranteed that if for some $ i \neq j $ holds $ p_i \neq -1, p_j \neq -1 $ , then $ p_i \neq p_j $ . It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case, output a single integer — the number of ways to set unknown values to obtain an anti-median permutation, modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

5
2
-1 -1
3
-1 -1 -1
4
1 2 3 4
6
-1 -1 3 4 -1 -1
8
-1 -1 -1 -1 -1 -1 -1 -1

输出样例 #1

2
4
0
1
316

说明

In the first test case, both $ [1, 2] $ and $ [2, 1] $ are anti-median. In the second test case, permutations $ [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2] $ are anti-median. The remaining two permutations, $ [1, 2, 3] $ , $ [3, 2, 1] $ , are bad arrays on their own, as their median, $ 2 $ , is in their middle. In the third test case, $ [1, 2, 3, 4] $ isn't anti-median, as it contains bad subarray $ [1, 2, 3] $ . In the fourth test case, the only anti-median array you can get is $ [5, 6, 3, 4, 1, 2] $ .

**题目大意：**

定义一个长度为奇数 $2m+1$ 的数组（$m \geq 1$）为“坏数组”，如果该数组的第 $m+1$ 个元素等于数组的中位数。换句话说，如果对该数组进行排序后，第 $m+1$ 个位置的元素保持不变，则该数组是“坏数组”。

定义一个从 1 到 $n$ 的整数排列 $p$ 为“反中位数排列”，如果它的每个长度大于等于 3 的奇数长度的子数组都不是“坏数组”。

给你一个排列中某些元素已经确定的值，其余用 $-1$ 代替。求出用所有可能的值填充 $-1$ 后，可以得到多少种“反中位数排列”。由于这个数量可能非常大，因此结果对 $10^9+7$ 取模。

**输入输出数据格式：**

**输入格式：**
- 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。
- 每个测试用例包含：
- 第一行包含一个整数 $n$（$2 \leq n \leq 1000$）——排列的长度。
- 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$ 或 $p_i = -1$）——排列的元素。如果 $p_i \neq -1$，则该值已给出；如果 $p_i = -1$，则该值未知。保证如果对于某些 $i \neq j$ 有 $p_i \neq -1, p_j \neq -1$，那么 $p_i \neq p_j$。
- 保证所有测试用例的 $n^2$ 之和不超过 $10^6$。

**输出格式：**
- 对于每个测试用例，输出一个整数——通过填充未知值来获得“反中位数排列”的方式数量，模 $10^9+7$。**题目大意：** 定义一个长度为奇数 $2m+1$ 的数组（$m \geq 1$）为“坏数组”，如果该数组的第 $m+1$ 个元素等于数组的中位数。换句话说，如果对该数组进行排序后，第 $m+1$ 个位置的元素保持不变，则该数组是“坏数组”。 定义一个从 1 到 $n$ 的整数排列 $p$ 为“反中位数排列”，如果它的每个长度大于等于 3 的奇数长度的子数组都不是“坏数组”。 给你一个排列中某些元素已经确定的值，其余用 $-1$ 代替。求出用所有可能的值填充 $-1$ 后，可以得到多少种“反中位数排列”。由于这个数量可能非常大，因此结果对 $10^9+7$ 取模。 **输入输出数据格式：** **输入格式：** - 第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——测试用例的数量。 - 每个测试用例包含： - 第一行包含一个整数 $n$（$2 \leq n \leq 1000$）——排列的长度。 - 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$ 或 $p_i = -1$）——排列的元素。如果 $p_i \neq -1$，则该值已给出；如果 $p_i = -1$，则该值未知。保证如果对于某些 $i \neq j$ 有 $p_i \neq -1, p_j \neq -1$，那么 $p_i \neq p_j$。 - 保证所有测试用例的 $n^2$ 之和不超过 $10^6$。 **输出格式：** - 对于每个测试用例，输出一个整数——通过填充未知值来获得“反中位数排列”的方式数量，模 $10^9+7$。