$N$ 枚の紙があり、それぞれ $1$ から $N$ までの整数で番号が付けられています。各紙には $K$ 個の整数が書かれており、$i$ 番目の紙には $v_{i,1}, v_{i,2}, \dots, v_{i,K}$ が書かれています。

各紙から整数を 1 つずつ選び、数列 $a_i$ を作成します。ここで、$i$ 番目の整数は $i$ 番目の紙から選ばれます。このような数列の作り方は $K^N$ 通りあります。このうち、広義単調増加であるものはいくつあるでしょうか。数列が広義単調増加であるとは、すべての $1 \le i \le N - 1$ に対して $a_i \le a_{i+1}$ が成り立つことを指します。

答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力してください。

入力

入力の最初の行には、2 つの整数 $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