Chúng ta ai cũng biết rằng các bạn học sinh rất thích ngủ. Và Patrix là một kỷ lục gia trong lĩnh vực này. Cậu ta chỉ thức dậy khi đói hoặc khi cậu ta muốn chơi FIFA 20. Vì vậy, các giấc mơ của cậu ta thường liên quan đến bóng đá. Trong giấc mơ gần nhất, cậu ta trở thành người quản lí cho đội bóng yêu thích của cậu ta - GNK Dinamo Zagreb.

Công việc của cậu ta là chọn ra ~N~ cầu thủ để phục vụ cho đội bóng trong mùa giải tiếp theo. Tuy nhiên, hội đồng quản trị có một số yêu cầu đặc biệt như sau:

• Tên của tất cả cầu thủ phải có độ dài khác nhau đôi một.
• Tên của một cầu thủ phải là một chuỗi con liên tiếp của tên của tất cả các cầu thủ có tên dài hơn cầu thủ đó.

Để công việc được thực hiện dễ dàng hơn, Patrik chia những ứng cử viên vào ~N~ nhóm sao cho cầu thủ ở nhóm thứ ~i~ có chính xác ~i~ ký tự trong tên. Mỗi nhóm này có chính xác ~K~ cầu thủ. Patrik muốn biết có tất cả bao nhiêu cách phân biệt (modulo ~10^9+7~) để cậu ta chọn cầu thủ cho đội hình mới mà vẫn thoả mãn những yêu cầu trên của hội đồng.

Input

Dòng đầu tiên chưa hai số nguyên ~N~ ~(1 \le N \le 50)~ và ~K~ ~(1 \le K \le 1500)~.

~N~ dòng tiếp theo, mỗi dòng chứa ~K~ tên của các cầu thủ trong nhóm. Các tên trong ~K~ tên này có thể trùng nhau. Tên của các cầu thủ trong dòng thứ ~i~ sẽ chứa chính xác ~i~ chữ cái in thường trong bảng chữ cái Tiếng Anh.

Output

In ra một dòng duy nhất là đáp án của bài toán.

Sample Input 1

3 2
a b
ab bd
abc abd

Sample Output 1

5

Sample Input 2

3 3
a b c
aa ab ac
aaa aab aca

Sample Output 2

6

Sample Input 3

3 1
a
bc
def

Sample Output 3

0

Subtask

• ~4~ test đầu có ~N = 5~ và ~K = 10~.
• ~7~ test test tiếp theo có ~N = 50~ và ~K = 100~.
• ~11~ test còn lại không có điều kiện gì thêm.

Note

Giải thích ví dụ đầu tiên: Patrix có thể chọn các đội hình sau: ~(a, ab, abc)~, ~(a, ab, abd)~, ~(b, ab, abc)~, ~(b, ab, abd)~ và ~(b, bd, abd)~.