Mamy $N$ kartek papieru, ponumerowanych kolejnymi liczbami całkowitymi od $1$ do $N$. Na każdej kartce zapisano $K$ liczb całkowitych, zatem $i$-ta kartka zawiera liczby $v_{i,1}, v_{i,2}, \dots, v_{i,K}$.

Następnie wybieramy po jednej liczbie z każdej kartki i tworzymy ciąg $a_i$, gdzie $i$-ta liczba jest wybrana z $i$-tej kartki papieru. Istnieje $K^N$ sposobów na utworzenie takiego ciągu. Ile z nich jest niemalejących? Ciąg jest niemalejący, jeśli $a_i \le a_{i+1}$ dla wszystkich $1 \le i \le N - 1$.

Wynik może być bardzo duży, dlatego należy wypisać go modulo $10^9 + 7$.

Wejście

Pierwsza linia wejścia zawiera dwie liczby całkowite $N$ oraz $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). Każda z kolejnych $N$ linii zawiera $K$ liczb całkowitych $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$).

Wyjście

Wypisz liczbę niemalejących ciągów, modulo $10^9 + 7$.

Przykład

Wejście 1

2 2
2 4
1 5

Wyjście 1

2

Wejście 2

2 3
4 5 6
1 2 3

Wyjście 2

0