Trong bài toán này, chúng ta sẽ làm việc với các hoán vị $n$ phần tử. Mỗi hoán vị như vậy là một dãy gồm $n$ số tự nhiên khác nhau từ $1$ đến $n$. Hợp thành của hoán vị $a_1, a_2, \dots, a_n$ với hoán vị $b_1, b_2, \dots, b_n$ là hoán vị $a_{b_1}, a_{b_2}, \dots, a_{b_n}$. Nghịch đảo trong hoán vị $p_1, p_2, \dots, p_n$ là bất kỳ cặp chỉ số $(i, j)$ nào sao cho $i < j$ và $p_i > p_j$.

Bajtek là một người hâm mộ cuồng nhiệt các hoán vị $n$ phần tử. Anh ấy yêu thích chúng đến mức có $k$ hoán vị yêu thích. Anh quyết định liệt kê trên giấy tất cả các hoán vị có thể thu được bằng cách hợp thành các hoán vị yêu thích của mình (theo bất kỳ thứ tự nào và có thể sử dụng một số hoán vị nhiều lần), đồng thời cẩn thận đảm bảo không viết lại bất kỳ hoán vị nào quá một lần.

Không có gì ngạc nhiên khi anh ấy nhanh chóng hết giấy. Bajtek nảy ra câu hỏi: nếu anh ấy liệt kê tất cả các hoán vị có thể đạt được, thì trung bình chúng có bao nhiêu nghịch đảo?

Hãy giúp anh ấy viết một chương trình tính giá trị này. Cụ thể, nhiệm vụ của bạn là đưa ra giá trị cần tìm modulo $10^9 + 7$ (xem thêm chi tiết trong phần Dữ liệu ra).

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, k \le 3000$), lần lượt biểu thị độ dài của hoán vị và số lượng hoán vị yêu thích của Bajtek.

Trong $k$ dòng tiếp theo là các hoán vị đó. Dòng thứ $i$ trong số các dòng này chứa một dãy gồm $n$ số nguyên khác nhau $a_{i,1}, a_{i,2}, \dots, a_{i,n}$ ($1 \le a_{i,j} \le n$), tương ứng với hoán vị yêu thích thứ $i$ của Bajtek.

Dữ liệu ra

Dòng duy nhất của dữ liệu ra phải chứa một số nguyên bằng số nghịch đảo trung bình trong tất cả các hoán vị mà Bajtek có thể liệt kê, được tính modulo $1\,000\,000\,007$.

Về mặt hình thức, giả sử kết quả là $\frac{p}{q}$, trong đó $q \neq 0$ và $\text{NWD}(p, q) = 1$. Khi đó, bạn cần in ra một số $p \cdot q^{-1} \pmod{1\,000\,000\,007}$, trong đó $q^{-1}$ là số duy nhất thuộc tập hợp $1, 2, \dots, 1\,000\,000\,006$ sao cho $q \cdot q^{-1} \equiv 1 \pmod{1\,000\,000\,007}$.

Có thể chứng minh rằng đối với tất cả các bộ dữ liệu kiểm thử thỏa mãn điều kiện bài toán, kết quả là một số hữu tỉ mà mẫu số ở dạng tối giản không chia hết cho $1\,000\,000\,007$.

Ví dụ

Ví dụ 1

Dữ liệu vào:

3 1
2 3 1

Dữ liệu ra:

333333337

Ví dụ 2

Dữ liệu vào:

5 2
2 1 3 4 5
2 3 4 5 1

Dữ liệu ra:

5

Ghi chú

Giải thích ví dụ: Trong bộ dữ liệu kiểm thử đầu tiên, Bajtek sẽ liệt kê hoán vị $\{1, 2, 3\}$ có 0 nghịch đảo, $\{2, 3, 1\}$ có 2 nghịch đảo, và $\{3, 1, 2\}$ cũng có 2 nghịch đảo. Số nghịch đảo trung bình là $\frac{4}{3}$. Ta có $3^{-1} \equiv 333333336 \pmod{1\,000\,000\,007}$, do đó $333333336 \cdot 4 \equiv 1333333344 \equiv 333333337 \pmod{1\,000\,000\,007}$.

Trong bộ dữ liệu kiểm thử thứ hai, Bajtek sẽ liệt kê tất cả các hoán vị 5 phần tử. Dễ dàng chứng minh rằng trung bình chúng có đúng 5 nghịch đảo.