Tarro de colores#13111

Tarro de colores

1,5 segundos
256 megabytes

Bohdana está repintando una valla formada por tablas, numeradas de a de izquierda a derecha. La tabla tiene actualmente el color c_i. Los colores son enteros positivos y varias tablas pueden compartir el mismo color.

La pintura de la valla todavía está fresca, así que Bohdana la repinta con pinceladas. En una pincelada elige dos tablas y con 1 \le l \le r \le n, recoge con un pincel seco el color actual de la tabla y arrastra el pincel hacia la derecha hasta la tabla . Después de la pincelada, todas las tablas l, l+1, \ldots, r tienen el color que tenía la tabla justo antes de la pincelada, y las demás tablas no cambian.

Bohdana puede hacer cualquier cantidad de pinceladas, posiblemente ninguna, una tras otra. ¿Cuántas coloraciones distintas de la valla puede obtener? Dos coloraciones son distintas si al menos una tabla tiene colores diferentes en ellas. La coloración inicial también se cuenta.

Como la respuesta puede ser muy grande, imprímela módulo .

Entrada

La primera línea contiene un único entero (1 \le t \le 5000) — el número de casos de prueba.

Cada caso de prueba consta de dos líneas. La primera línea contiene un entero (1 \le n \le 5000) — el número de tablas. La segunda línea contiene enteros c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9) — los colores de las tablas de izquierda a derecha.

La suma de sobre todos los casos de prueba no excede .

Salida

Para cada caso de prueba imprime un entero — la cantidad de coloraciones distintas que Bohdana puede obtener, módulo .

Ejemplos

Ejemplo 1

Loading
Loading

Nota

En el primer caso de prueba la valla es (1, 2, 3), y las coloraciones posibles son (1, 2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 2) y (1, 1, 1). Por ejemplo, (1, 1, 2) se obtiene con la pincelada l = 2, r = 3, que da (1, 2, 2), seguida de la pincelada l = 1, r = 2. La coloración (1, 3, 2) no se puede obtener. La figura muestra estas dos pinceladas: la flecha sobre la valla es el recorrido del pincel.

En el segundo caso de prueba las coloraciones posibles son (5, 7, 5, 7), (5, 7, 5, 5), (5, 7, 7, 5), (5, 7, 7, 7), (5, 5, 7, 5), (5, 5, 7, 7), (5, 5, 5, 7) y (5, 5, 5, 5). Por ejemplo, (5, 7, 7, 5) se obtiene con la pincelada l = 3, r = 4 seguida de la pincelada l = 2, r = 3.

En el tercer caso de prueba todas las tablas ya tienen el mismo color, y ninguna pincelada cambia nada.