시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

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.

예제 입력 1

2
3
0 0 0
7
1 0 3 0 0 6 0

예제 출력 1

2
21