Dans ce problème, nous nous intéressons aux permutations de $n$ éléments. Chaque permutation est une suite de $n$ nombres naturels distincts allant de $1$ à $n$ inclus. La composition d'une permutation $a_1, a_2, \dots, a_n$ avec une permutation $b_1, b_2, \dots, b_n$ est la permutation $a_{b_1}, a_{b_2}, \dots, a_{b_n}$. Une inversion dans une permutation $p_1, p_2, \dots, p_n$ est définie comme toute paire d'indices $(i, j)$ telle que $i < j$ et $p_i > p_j$.
Bajtek est un grand fan de permutations à $n$ éléments. Il les aime tellement qu'il en a même $k$ favorites. Il a décidé de noter sur une feuille toutes les permutations qu'il est possible d'obtenir en composant ses permutations favorites (dans n'importe quel ordre et en utilisant éventuellement certaines d'entre elles plusieurs fois), tout en veillant scrupuleusement à ne jamais écrire deux fois la même permutation.
Sans surprise, il a rapidement manqué de papier. Bajtek s'est alors posé la question suivante : s'il écrivait toutes les permutations atteignables, quel serait le nombre moyen d'inversions parmi elles ?
Aidez-le et écrivez un programme qui calcule cette valeur. Plus précisément, votre tâche est de fournir la valeur recherchée modulo $10^9 + 7$ (plus de détails dans la section Sortie).
Entrée
La première ligne de l'entrée contient deux entiers $n$ et $k$ ($1 \le n, k \le 3000$), représentant respectivement la longueur des permutations et le nombre de permutations favorites de Bajtek.
Les $k$ lignes suivantes contiennent ces permutations. La $i$-ième ligne contient une suite de $n$ entiers distincts $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$), correspondant à la $i$-ième permutation favorite de Bajtek.
Sortie
La seule ligne de sortie doit contenir un entier égal au nombre moyen d'inversions parmi toutes les permutations que Bajtek pourrait écrire, donné modulo $1\,000\,000\,007$.
Formellement, soit le résultat égal à $\frac{p}{q}$, où $q \neq 0$ et $\text{PGCD}(p, q) = 1$. Vous devez alors afficher l'entier $p \cdot q^{-1} \pmod{1\,000\,000\,007}$, où $q^{-1}$ est l'unique entier de l'ensemble $\{1, 2, \dots, 1\,000\,000\,006\}$ tel que $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$.
On peut démontrer que pour tous les tests respectant les conditions du problème, le résultat est un nombre rationnel dont le dénominateur, sous forme irréductible, n'est pas divisible par $1\,000\,000\,007$.
Exemples
Entrée 1
3 1 2 3 1
Sortie 1
333333337
Entrée 2
5 2 2 1 3 4 5 2 3 4 5 1
Sortie 2
5
Remarque
Dans le premier exemple, Bajtek écrirait la permutation $\{1, 2, 3\}$, ayant zéro inversion, $\{2, 3, 1\}$, ayant deux inversions, et $\{3, 1, 2\}$, ayant également deux inversions. Le nombre moyen d'inversions est donc $\frac{4}{3}$. Comme $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$, nous avons $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$.
Dans le second exemple, Bajtek écrirait toutes les permutations de 5 éléments. Il est facile de montrer qu'elles ont en moyenne exactement 5 inversions.