순열

치아키는 1부터 $n$까지의 정수로 이루어진 순열 $p_1,p_2,\dots,p_n$을 가지고 있지만, 일부 위치의 값은 알려져 있지 않다. 그녀는 빈 위치를 채웠을 때 결과 순열이 길이 $3$ 이상인 등차수열 부분수열을 포함하는 경우의 수를 알고 싶어 한다.

경우의 수가 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다.

첫 줄에 순열의 길이 $n$ ($1 \le n \le 50$)이 주어진다.

둘째 줄에 정수 $p_1,p_2,\dots,p_n$ ($0 \le p_i \le n$)이 주어진다. $p_i = 0$이면 $i$번째 위치의 값이 알려져 있지 않다는 뜻이다. 0이 아닌 값은 모두 서로 다르다.

모든 테스트 케이스의 $n$의 합은 $50$을 넘지 않는다.

각 테스트 케이스마다 답을 한 줄에 출력한다.