有 $N$ 張紙，編號由 $1$ 到 $N$。每張紙上寫有 $K$ 個整數，第 $i$ 張紙包含整數 $v_{i,1}, v_{i,2}, \dots, v_{i,K}$。

接著我們從每張紙中各選擇一個整數，組成一個序列 $a_i$，其中第 $i$ 個整數是從第 $i$ 張紙中選出的。共有 $K^N$ 種組成序列的方法。請問其中有多少個序列是非遞減的？ 若對於所有 $1 \le i \le N - 1$ 皆滿足 $a_i \le a_{i+1}$，則稱該序列為非遞減。

由於答案可能非常大，請輸出其對 $10^9 + 7$ 取模後的結果。

輸入格式

第一行包含兩個整數 $N$ 和 $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$)。接下來 $N$ 行中的第 $i$ 行包含 $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