Alex tiene un arreglo ~a~ de ~n~ enteros donde cada entero aparece a lo más dos veces en el arreglo.

Vamos a definir ~p~ como una permutación de ~a~. Alex piensa que una permutación ~p~ es buena si no existe un ~i \; (1 \leq i < n)~ tal que ~p_i - p_{i + 1} = 0~.

Alex quiere saber cuantas permutaciones buenas del arreglo ~a~ existen. Dos permutaciones ~p~ y ~q~ son distintas si y solo si existe un ~i \; (1 \leq i \leq n)~ tal que ~p_i \neq q_i~. Como la respuesta puede ser muy grande imprímala modulo ~10^9 + 7~.

Entrada

La primera línea contiene el entero ~q \; (1 \leq q \leq 100)~ que denota la cantidad de casos de prueba.

Cada caso de prueba tiene el siguiente formato:

La primera línea contiene el entero ~n \; (1 \leq n \leq 2000)~.

La segunda línea contiene ~n~ enteros ~a_1, a_2, \ldots, a_n \; (1 \leq a_i \leq 10^9)~ separados por un espacio entre sí.

El ~40\%~ de los juegos de datos cumplen que:

• ~1 \leq q \leq 100~
• ~1 \leq n \leq 1000~
• La suma de ~n~ en todos los casos de prueba (del juego de datos correspondiente) no excede ~10^4~.

Salida

Imprima ~q~ enteros, uno por línea, denotando la cantidad de permutaciones buenas del arreglo ~a~ modulo ~10^9 + 7~, del ~i~-ésimo caso.

Entrada de ejemplo

3
3
1 1 2
2
1 2
4
1 2 2 1

Salida de ejemplo

1
2
2

Explicación del ejemplo

En cada caso las permutaciones son las siguientes:

• ~a = [1, 2, 1]~. La única permutación buena es:

• ~a=[1, 2]~. Hay dos permutaciones buenas:

• ~a=[1, 2, 2, 1]~. Hay dos permutaciones buenas: