Anti-median (Easy Version)
Contest: Pinely Round 1 (Div. 1 + Div. 2)
Difficulty rating: 3100
Tags: dp, math

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

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
2
4
0
1
316

Editorial:
Let's analyze the structure of anti-median permutations.
First, if for any $$$2 \le i \le n-1$$$ holds $$$a_{i-1}>a_i>a_{i+1}$$$, or $$$a_{i-1}<a_i<a_{i+1}$$$, then segment $$$p[i-1:i+1]$$$ is bad. So, the signs between adjacent elements are alternating. So, consider two cases: all elements on even positions are local maximums, and on odd local minimums, and vice versa.
Let's find the answer for the first case (for the second, you can find the answer similarly). Consider a segment of length $$$5$$$, $$$[p_{i-2}, p_{i-1}, p_i, p_{i+1}, p_{i+2}]$$$. Consider the case when $$$i$$$ is even first. Then $$$p_i>p_{i-1}, p_{i+1}$$$. For $$$p_i$$$ to not be median, it has to be larger than one of $$$p_{i-2}, p_{i+2}$$$. So, when we consider only even elements, each element (except the first and last one) has at least one adjacent element smaller than it. It's easy to see that this implies that elements at even positions are first increasing and then decreasing.
Similarly, we can see that elements at odd positions are first decreasing, then increasing. It's not hard to see that these conditions are sufficient. Indeed, suppose that:
• All elements on even positions are local maximums, and all elements on odd positions are local minimums
• Elements at even positions are first increasing and then decreasing.
• Elements at odd positions are first decreasing, then increasing.
Then, consider any segment of odd length. Denote it by $$$b_1, b_2, \ldots, b_{2m+1}$$$, and wlog $$$b_{m+1}$$$ is local maximum. If we look at local maximums, at least one of the following two conditions has to hold: all local maximums to the right of $$$b_{m+1}$$$ are smaller than it, or all local maximums to the left of $$$b_{m+1}$$$ are smaller than it. Wlog first case. Then all elements to the right of $$$b_{m+1}$$$ are smaller than it, and $$$b_m$$$ is also smaller than it, so $$$b_{m+1}$$$ can't be a median.
Now, let's put all elements on the circle in the following order: first, all even elements from left to right, then all odd elements from right to left.
In this circle, the elements on both paths between $$$n$$$ and $$$1$$$ are decreasing. It follows that for any $$$k$$$, numbers from $$$k$$$ to $$$n$$$ form a segment (in this cyclic arrangement).
Then, we can write a $$$dp$$$ of the form: $$$dp[l][r]$$$: how many ways are there to arrange the largest $$$(r-l+1+n)\bmod n$$$ elements so that they end up in the positions from $$$l$$$-th to $$$r$$$-th in this cyclic arrangement. All the transitions and checks are done in $$$O(1)$$$, and there are $$$O(n^2)$$$ states, so we are done.