Il y a $N$ feuilles de papier, numérotées par des entiers séquentiels de $1$ à $N$. Chaque feuille contient $K$ entiers, de sorte que la $i$-ième feuille contient les entiers $v_{i,1}, v_{i,2}, \dots, v_{i,K}$.

Ensuite, nous choisissons un entier sur chaque feuille pour créer la séquence $a_i$, où le $i$-ième entier est choisi sur la $i$-ième feuille de papier. Il existe $K^N$ façons de former une telle séquence. Combien d'entre elles sont non décroissantes ? Une séquence est non décroissante si $a_i \le a_{i+1}$ pour tout $1 \le i \le N - 1$.

La réponse peut être très grande, veuillez donc l'afficher modulo $10^9 + 7$.

Entrée

La première ligne de l'entrée contient deux entiers $N$ et $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). La $i$-ième des $N$ lignes suivantes contient $K$ entiers $v_{i,1}, v_{i,2}, \dots, v_{i,K}$ ($1 \le v_{i,1} < v_{i,2} < \dots < v_{i,K} \le 10^9$).

Sortie

Affichez le nombre de séquences non décroissantes, modulo $10^9 + 7$.

Exemples

Entrée 1

2 2
2 4
1 5

Sortie 1

2

Entrée 2

2 3
4 5 6
1 2 3

Sortie 2

0