Số điện thoại di động ở Việt Nam là một dãy 9 ký tự số (không tính chữ số 0 ở đầu) có dạng \(a_1a_2...a_9\), trong đó \(a_1 \neq 0\). Hai số điện thoại được coi là có tính trùng lặp nếu ta có thể sắp xếp lại trật tự các chữ số trong một số điện thoại để đạt được số điện thoại còn lại. Ví dụ hai số điện thoại 912323648 và 923124368 là có tính trùng lặp; tuy nhiên hai số điện thoại 912323648 và 912322648 thì không có tính trùng lặp.

An đang có một danh sách các số điện thoại di động. An cần chọn ra một nhóm mà trong nhóm đó có đúng \(k\) cặp số điện thoại có tính trùng lặp.

Hãy xác định xem An có bao nhiêu cách chọn một nhóm thoả mãn yêu cầu.

Input

• Dòng đầu tiên chứa hai số nguyên dương theo trình tự là \(n\) và \(k\); trong đó \(n\) là số lượng số điện thoại An đang có.
• Mỗi dòng trong \(n\) dòng tiếp theo chứa một số điện thoại. Dữ liệu đảm bảo tất cả \(n\) số điện thoại đều khác nhau, các số điện thoại đều có cấu trúc như mô tả ở trên.

Output

• Số cách chọn một nhóm thoả mãn yêu cầu của An. Kết quả đưa ra sau khi chia lấy phần dư cho \(10^9 + 7\).

Example

3 1
912345678
123456787
123456789

2

5 2
425152350
425505123
685125412
865541212
450232551

3

Scoring

• \(60\%\) test tương ứng với \(60\%\) số điểm ứng với \(1 \leq n \leq 15\); \(0 \leq k < n\)
• \(40\%\) test tương ứng với \(40\%\) số điểm ứng với \(15 < n \leq 1000\); \(0 \leq k < n\)