Matcom Online Grader

Fito es un enamorado de la navidad. Por eso en esta ocasión ha decidido comenzar los preparativos desde mucho antes. Su primera tarea es decorar adecuadamente la casa. Buscando en su sótano ha encontrado una cadena de luces de navidad que piensa estaría perfecta en la entrada de su casa. La cadena de luces consiste en un cable, un tomacorriente y $N$ sockets conectados en serie. Fito tiene además un paquete de $N$ bombillos de $K$ colores distintos que puede poner en los sockets. Para que se enciendan las luces todos los bombillos debe ser ubicados en la cadena. La única regla a cumplir es que no debe haber dos bombillos consecutivos del mismo color. Se quiere saber de cuántas formas distintas puede Fito poner los bombillos.

La entrada empieza con un entero $T$ $(1 \leq T \leq 7)$ que indica la cantidad de casos a evaluar. Cada caso empieza con el entero $K$ $(1 \leq K \leq 200)$ en una línea y luego sigue otra línea con $K$ enteros separados por un espacio, cada uno representando la cantidad de bombillos de un color distinto. La cantidad total de bombillos $N$ es a lo sumo $200$.

Por cada caso se debe imprimir la cantidad de formas de poner los bombillos sin que haya dos juntos del mismo color. Como este número puede ser muy grande se debe devolver el resto de su división por $1,000,000,007$.