수학과 철학 청년 애호가 대회

3015년 2월 37일, 수학과 철학을 사랑하는 청년들의 대회가 개막했다. 각 나라에서 수학자 한 명과 철학자 한 명이 참가했다. 두 시간 뒤 참가자 전원이 모이는 회의가 열리는데, 주최 측은 아직 자리 배치를 정하지 못했다. 회의장에는 $2n$개의 의자가 일렬로 놓여 있다. 의자는 세 종류다. 1번 의자에는 수학자만 앉을 수 있고, 2번 의자에는 철학자만 앉을 수 있으며, 3번 의자에는 참가자 누구나 앉을 수 있다.

첫 줄에 테스트의 개수를 나타내는 자연수 $t$가 주어진다. 각 테스트는 두 줄로 설명된다. 첫 줄에는 나라의 수 $n$이 주어진다. 둘째 줄에는 1부터 3까지의 자연수가 $2n$개 주어지며, $i$번째 수는 $i$번째 의자의 종류를 나타낸다. 모든 테스트에 걸친 $n$의 합은 100을 넘지 않는다.

각 테스트마다 참가자를 앉히는 방법의 수를 $10^9 + 7$로 나눈 나머지를 출력한다.