En este problema trabajaremos con permutaciones de $n$ elementos. Cada permutación es una secuencia de $n$ números naturales distintos del $1$ al $n$ inclusive. La composición de una permutación $a_1, a_2, \dots, a_n$ con una permutación $b_1, b_2, \dots, b_n$ es la permutación $a_{b_1}, a_{b_2}, \dots, a_{b_n}$. Una inversión en una permutación $p_1, p_2, \dots, p_n$ es cualquier par de índices $(i, j)$ tal que $i < j$ y $p_i > p_j$.

Bajtek es un gran fanático de las permutaciones de $n$ elementos. Le gustan tanto que tiene $k$ permutaciones favoritas. Decidió comenzar a escribir en una hoja todas las permutaciones que se pueden obtener componiendo sus permutaciones favoritas (en cualquier orden y posiblemente usando algunas de ellas varias veces), asegurándose meticulosamente de no escribir ninguna permutación más de una vez.

No fue una sorpresa que se quedara sin papel bastante rápido. Entonces, a Bajtek le surgió la siguiente pregunta: si escribiera todas las permutaciones alcanzables, ¿cuántas inversiones tendrían en promedio?

Ayúdalo y escribe un programa que calcule este valor. Más precisamente, tu tarea es proporcionar el valor buscado módulo $10^9 + 7$ (más detalles en la sección Salida).

Entrada

La primera línea de la entrada contiene dos números enteros $n$ y $k$ ($1 \le n, k \le 3000$), que representan la longitud de las permutaciones y el número de permutaciones favoritas de Bajtek, respectivamente.

En las siguientes $k$ líneas se encuentran dichas permutaciones. La $i$-ésima de estas líneas contiene una secuencia de $n$ números enteros distintos $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$), que corresponde a la $i$-ésima permutación favorita de Bajtek.

Salida

La única línea de salida debe contener un número entero igual al número promedio de inversiones entre todas las permutaciones que Bajtek podría escribir, dado módulo $1\,000\,000\,007$.

Formalmente, sea el resultado igual a $\frac{p}{q}$, donde $q \neq 0$ y $\text{mcd}(p, q) = 1$. Entonces, se debe imprimir un número $p \cdot q^{-1} \pmod{1\,000\,000\,007}$, donde $q^{-1}$ es el único número del conjunto $1, 2, \dots, 1\,000\,000\,006$ tal que $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$.

Se puede demostrar que para todos los casos de prueba que cumplen las condiciones del problema, el resultado es un número racional cuyo denominador en forma irreducible no es divisible por $1\,000\,000\,007$.

Ejemplos

Entrada 1

3 1
2 3 1

Salida 1

333333337

Entrada 2

5 2
2 1 3 4 5
2 3 4 5 1

Salida 2

5

Nota

En el primer caso de prueba, Bajtek escribiría la permutación $\{1, 2, 3\}$, que tiene cero inversiones, $\{2, 3, 1\}$, que tiene dos inversiones, y $\{3, 1, 2\}$, que también tiene dos inversiones. Por lo tanto, el número promedio de inversiones es $\frac{4}{3}$. Dado que $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$, tenemos $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$.

En el segundo caso de prueba, Bajtek escribiría todas las permutaciones de $5$ elementos. Es fácil demostrar que, en promedio, tienen exactamente $5$ inversiones.