20613번 - Permutation 다국어

Chiaki has a permutation $p_1,p_2,\dots,p_n$ of integers $1,2,\dots,n$ with some unknown positions. She would like to know the number of ways to fill the unknown positions such that the resulting permutation contains a subsequence of length at least $3$ that is an arithmetic progression.

As the number may be very large, you are only asked to calculate it modulo $10^9 + 7$.

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $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$), where $p_i=0$ means that $p_i$ is unknown, and all non-zero elements are distinct.

It is guaranteed that the sum of $n$ in all test cases does not exceed $50$.

For each test case, output an integer denoting the answer.