Có $N$ tờ giấy, được đánh số bằng các số nguyên liên tiếp từ $1$ đến $N$. Mỗi tờ giấy có $K$ số nguyên được viết trên đó, tờ giấy thứ $i$ chứa các số $v_{i,1}, v_{i,2}, \dots, v_{i,K}$.

Sau đó, chúng ta chọn một số nguyên từ mỗi tờ giấy và tạo thành dãy $a_i$, trong đó số nguyên thứ $i$ được chọn từ tờ giấy thứ $i$. Có $K^N$ cách để tạo ra một dãy như vậy. Có bao nhiêu cách để dãy thu được là dãy không giảm? Một dãy được gọi là không giảm nếu $a_i \le a_{i+1}$ với mọi $1 \le i \le N - 1$.

Kết quả có thể rất lớn, vì vậy hãy in ra kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $N$ và $K$ ($1 \le N \le 100$, $1 \le K \le 10^4$). Dòng thứ $i$ trong số $N$ dòng tiếp theo chứa $K$ số nguyên $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$).

Dữ liệu ra

In ra số lượng các dãy không giảm, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

2 2
2 4
1 5

Dữ liệu ra 1

2

Dữ liệu vào 2

2 3
4 5 6
1 2 3

Dữ liệu ra 2

0