El arreglo sombra

Entrada

La primera línea contiene un único entero $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — la cantidad de casos de prueba.

La primera línea de cada caso de prueba contiene un único entero $n$ ( $1 \leq n \leq 1 0^{6}$ 1 \le n \le 10^6) — la longitud del arreglo.

La segunda línea de cada caso de prueba contiene $n$ enteros $h_{1}, h_{2}, \dots, h_{n}$ h_1, h_2, \dots, h_n ( $1 \leq h_{i} \leq 1 0^{9}$ 1 \le h_i \le 10^9) — los elementos del arreglo sombra $h$ .

Se garantiza que la suma de $n$ sobre todos los casos de prueba no excede $1 0^{6}$ 10^6.

Salida

Para cada caso de prueba, muestra un único entero — la cantidad de arreglos originales $a$ válidos módulo $1 0^{9} + 7$ 10^9 + 7.

Ejemplos

Ejemplo 1

Loading

Nota

En el primer caso de prueba, $h = [2, 2, 2]$ h = [2, 2, 2]. Existen exactamente $2$ arreglos originales $a$ válidos que producen este arreglo sombra:

$a = [2, 1, 2]$ a = [2, 1, 2]
$a = [2, 2, 2]$ a = [2, 2, 2]

Puntuación

Subtarea $1$ ( $40$ puntos): $\sum n \leq 8$ \sum n \le 8 y $h_{i} \leq 8$ h_i \le 8.
Subtarea $2$ ( $160$ puntos): $\sum n \leq 1000$ \sum n \le 1000 y $h_{i} \leq 100$ h_i \le 100.
Subtarea $3$ ( $200$ puntos): Sin restricciones adicionales.