Diga cuántos ciclos simples distintos existen en un grafo completo no dirigido de ~n (3 \leq n \leq 2000)~ nodos, como la respuesta puede ser demasiado grande imprímala módulo ~10^9+7~.

Un grafo completo no dirigido es un grafo que por cada par de nodos distintos, existe una arista entre ellos.

Un ciclo simple es una secuencia de nodos ~v_{0}, v_{1}, ... , v_{k-1}~, con ~k \geq 3~, de que cumpla las siguientes condiciones:

• Todos los nodos del ciclo son distintos
• Los nodos ~v_{i}~ y ~v_{(i+1) mod (k)}~ están conectados por una arista, dicha arista forma parte del ciclo
• Todas las aristas que forman parte del ciclo son distintas

Dos ciclos ~a~ y ~b~ se consideran distintos si alguna de las siguientes condiciones se cumple:

• Existe un nodo que se encuentra en ~a~ y no en ~b~, o existe un nodo que se encuentra en ~b~ y no en ~a~.
• Existe una arista que se encuentra en ~a~ y no en ~b~, o existe una arista que se encuentra en ~b~ y no en ~a~.

Constantes

~1 \leq T \leq 1000~, la cantidad de casos a procesar

~1 \leq n \leq 2000~, la cantidad de nodos del grafo en cada caso.

Puntuación

• Subtarea 1, ~T \leq 6, n \leq 8~ (30 puntos).
• Subtarea 2, sin restricciones adicionales (70 puntos).

Ejemplo de entrada

4
3
4
5
2000

Ejemplo de salida

1
7
37
320019990