Hay $N$ hojas de papel, enumeradas con enteros secuenciales del 1 al $N$. Cada hoja tiene $K$ enteros escritos en ella, por lo que la $i$-ésima hoja contiene los enteros $v_{i,1}, v_{i,2}, \dots, v_{i,K}$.

Luego, elegimos un entero de cada hoja y creamos la secuencia $a_i$, donde el $i$-ésimo entero se elige de la $i$-ésima hoja de papel. Hay $K^N$ formas de crear dicha secuencia. ¿Cuántas de ellas son no decrecientes? Una secuencia es no decreciente si $a_i \le a_{i+1}$ para todo $1 \le i \le N - 1$.

La respuesta puede ser muy grande, así que imprímela módulo $10^9 + 7$.

Entrada

La primera línea de la entrada contiene dos enteros $N$ y $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). La $i$-ésima de las siguientes $N$ líneas contiene $K$ enteros $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$).

Salida

Imprime el número de secuencias no decrecientes, módulo $10^9 + 7$.

Ejemplos

Entrada 1

2 2
2 4
1 5

Salida 1

2

Entrada 2

2 3
4 5 6
1 2 3

Salida 2

0