CF1761F1 Anti-median (Easy Version)

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

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