有 $N$ 张纸，编号从 $1$ 到 $N$。每张纸上写有 $K$ 个整数，第 $i$ 张纸上的整数为 $v_{i,1}, v_{i,2}, \dots, v_{i,K}$。

我们需要从每张纸上各选出一个整数，组成一个序列 $a_1, a_2, \dots, a_N$，其中第 $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