Tại thời điểm này, chúng ta đã biết rằng sinh viên thích ngủ. Patrik là một người giữ kỷ lục trong hạng mục này. Anh ấy chỉ thức dậy khi cần ăn hoặc muốn chơi FIFA 20. Do đó, những giấc mơ của anh ấy thường xoay quanh bóng đá. Trong giấc mơ cuối cùng của mình, anh ấy thấy mình trong vai trò của một người quản lý bóng đá của đội bóng yêu thích của mình - GNK Dinamo Zagreb.

Nhiệm vụ của anh ấy là chọn ~N~ cầu thủ sẽ bảo vệ màu xanh trong mùa giải tới, nhưng hội đồng quản trị có một số yêu cầu đặc biệt. Chúng là:

• Tất cả các cầu thủ phải có họ độc đáo về độ dài.
• Họ của một cầu thủ phải xuất hiện như một dãy con liên tục của các họ của tất cả cầu thủ có họ dài hơn.

Để làm cho công việc của mình dễ dàng hơn, Patrik chia các cầu thủ tiềm năng thành ~N~ thùng sao cho các cầu thủ trong thùng thứ ~i~ có đúng ~i~ chữ cái trong họ của họ. Trong mỗi trong số các thùng này, có chính xác ~K~ cầu thủ. Patrik muốn biết có bao nhiêu cách khác nhau (theo modulo ~10^9 + 7~) anh ấy có thể chọn các cầu thủ cho đội của mình trong khi cũng tuân thủ các yêu cầu đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ ~(1 \leq N \leq 50)~ và ~K~ ~(1 \leq K \leq 1500)~.
• Mỗi trong số ~N~ dòng tiếp theo chứa K họ không nhất thiết phải khác nhau của các cầu thủ. Các họ của các cầu thủ trong dòng thứ ~i~ đó bao gồm chính xác ~i~ chữ cái viết thường từ bảng chữ cái tiếng Anh.

Output

Trong duy nhất một dòng, bạn nên đưa ra câu trả lời từ mô tả nhiệm vụ.

Chú ý

• 22 điểm thỏa mãn ~N = 5~ và ~K = 10~.
• 33 điểm thỏa mãn ~N = 50~ và ~K = 100~.
• 55 điểm không có ràng buộc bổ sung.

Sample Input 1

3 2
a b
ab bd
abc abd

Sample Ouput 1

5

Sample Input 2

3 3
a b c
aa ab ac
aaa aab aca

Sample Ouput 2

6

Sample Input 3

3 1
a
bc
def

Sample Ouput 3

0

Giải thích

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