Есть $N$ листов бумаги, пронумерованных последовательными целыми числами от $1$ до $N$. На каждом листе написано $K$ целых чисел, то есть на $i$-м листе записаны числа $v_{i,1}, v_{i,2}, \dots, v_{i,K}$.

Затем мы выбираем по одному целому числу с каждого листа и составляем последовательность $a_i$, где $i$-е число выбрано с $i$-го листа бумаги. Существует $K^N$ способов составить такую последовательность. Сколько из них являются неубывающими? Последовательность называется неубывающей, если $a_i \le a_{i+1}$ для всех $1 \le i \le N - 1$.

Ответ может быть очень большим, поэтому выведите его по модулю $10^9 + 7$.

Входные данные

Первая строка входных данных содержит два целых числа $N$ и $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). Каждая из следующих $N$ строк содержит $K$ целых чисел $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$).

Выходные данные

Выведите количество неубывающих последовательностей по модулю $10^9 + 7$.

Примеры

Входные данные 1

2 2
2 4
1 5

Выходные данные 1

2

Входные данные 2

2 3
4 5 6
1 2 3

Выходные данные 2

0