Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Fito está estudiando Biología y un profesor le ha planteado un problema bien interesante. El  profesor está trabajando para la  NASA y  ellos han encontrado fragmentos de ADN marciano!! Este ADN es muy diferente al nuestro, tienen una forma de una  matriz de $3 \times N$ con  $N$ diferentes tipos de bases nitrogenadas (el ADN de la tierra solo tiene cuatro, Adenina, Timina, Citosina y Guanina). Cada celda de esta matriz de ADN marciano solo puede tener una base nitrogenada y tiene que ser diferente  a todas las que se encuentran en la misma fila y columna. El problema consiste en que las muestras que se lograron traer a la tierra están contaminadas ya que la tercera fila de las muestras se perdió. El profesor desea saber dada una muestra de este ADN marciano (que ha perdido la última fila) cu á ntas  muestras reales diferentes pudiera haber.

Input

La primera línea de la entrada contiene un entero $T$ $(1 \le T \le 10)$ que denota la cantidad de casos de prueba de la entrada. La primera línea de cada caso de prueba es un entero $N$ $(3 \le N \le 1000)$. La próxima línea contiene $N$ enteros diferentes $A_1, A_2, A_3,..., A_N$ representando las bases nitrogenadas de la primera fila. La próxima línea contiene $N$ enteros diferentes $B_1, B_2, B_3,..., B_N$ representando las bases nitrogenadas de la segunda fila. Se tiene además que $A_i \ne B_i$ para $1 \le i \le N$.

Output

Por cada caso de prueba debes imprimir la cantidad de formas en las que se puede rellenar la tercera fila de la muestra de ADN. La respuesta debe darla módulo $1000000007 (10^9 + 7)$.

Sample test(s)

Hints

Hint
Para el primer caso las formas posibles de rellenar la tercera fila son {1, 3, 4, 2} y {4, 2, 3, 1}. En el segundo caso las formas posibles son {3, 1, 4, 2}, {3, 2, 4, 1}, {4, 1, 3, 2} y {4, 2, 3, 1}.