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