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] $ .