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