Introversion

당신은 Taste Of Pacific Cuisine(TOPC)이라는 식당을 운영합니다. 이번 주말에 많은 손님을 맞는 큰 연회가 열립니다. 주방장은 $n$가지 종류의 요리를 만들었습니다. 모든 손님이 각 종류를 맛볼 수 있도록, 종류마다 두 접시씩 준비하려고 합니다. 연회에 나오는 요리는 모두 $2n$접시입니다.

테이블은 매우 길어서 $2n$접시가 한 줄에 정확히 들어갑니다. 모든 요리를 한 번에 한 줄로 차려 놓을 예정입니다. 같은 종류의 요리 두 접시는 서로 인접하면 안 됩니다. 그래야 돌아다니기 싫어하는 내향적인 손님도 가까이에서 고를 수 있습니다.

이미 테이블에 놓인 요리가 있습니다. 같은 종류의 두 접시가 인접하지 않도록 남은 요리를 놓는 방법의 수를 세어 주세요. 이를 intro version이라고 부릅니다. 경우의 수가 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력합니다.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스는 정수 $n$으로 시작합니다. 다음 줄에는 공백으로 구분된 $2n$개의 정수 $x_1, x_2, \cdots, x_{2n}$이 주어집니다. $x_i=0$이면 테이블의 $i$번째 자리는 비어 있습니다. 그렇지 않으면 $x_i$는 1부터 $n$까지의 정수이며 요리의 종류를 나타냅니다. 각 종류 $k \in \{1,2,\dots,n\}$은 입력에 최대 두 번 나타난다는 것이 보장됩니다. 한 종류가 두 번 나타나면 두 위치는 인접하지 않습니다.

각 테스트 케이스에 대해, 남은 요리를 모두 놓는 유효한 방법의 수를 $10^9+7$로 나눈 나머지로 출력합니다.

$1 \le T \le 20$

$2 \le n \le 100$

$0 \le x_i \le n$