Permutation

Time limit3sMemory limit256 MB

Summary

Count the ways to fill the unknown positions of a partial permutation so the result has an arithmetic progression subsequence of length 3 or more, modulo 10^9+7.

Level: Hard8 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

Chiaki has a permutation $p_1,p_2,\dots,p_n$ of the integers $1,2,\dots,n$ , but some of its positions are unknown. She wants to know how many ways there are to fill the unknown positions so that the resulting permutation contains a subsequence of length at least $3$ that is an arithmetic progression.

Since the number may be very large, print it modulo $10^9 + 7$ .

Input

The first line contains $T$ , the number of test cases. Each test case has two lines.

The first line contains $n$ ( $1 \le n \le 50$ ), the length of the permutation.

The second line contains $n$ integers $p_1,p_2,\dots,p_n$ ( $0 \le p_i \le n$ ). $p_i = 0$ means that position $i$ is unknown. All nonzero values are distinct.

The sum of $n$ over all test cases does not exceed $50$ .

Output

For each test case, print the answer on its own line.

Examples1

Example 1
Input
```
2
3
0 0 0
7
1 0 3 0 0 6 0
```
Expected output
```
2
21
```