🎭 BẢN GIAO HƯỞNG GHÉP XÂU: SỰ TRỖI DẬY CỦA UIAOJ

Ngày UIAOJ chính thức lên sóng, ban tổ chức muốn ghép các mẩu thông điệp thành một tín hiệu đặc biệt. Tín hiệu được tạo bằng cách chọn một số mẩu rồi ghép chúng theo một thứ tự bất kỳ.

Trong tín hiệu cần có từ khóa uiaoj xuất hiện ít nhất k lần. Các lần xuất hiện được tính là không đè lên nhau.

Trước khi ghép, bạn được phép chèn tối đa một ký tự thường từ a đến z vào một trong các xâu được chọn. Có thể không chèn ký tự nào. Vị trí chèn có thể là trước ký tự đầu tiên, giữa hai ký tự bất kì hoặc sau ký tự cuối cùng.

Hãy đếm số cách chọn các xâu, sắp xếp chúng và thực hiện thao tác chèn sao cho tín hiệu cuối cùng có ít nhất k lần xuất hiện không đè lên nhau của uiaoj.

Hai xâu có nội dung giống nhau nhưng khác chỉ số vẫn được xem là hai xâu khác nhau. Các cách chọn chỉ số, thứ tự ghép hoặc thao tác chèn khác nhau được tính riêng, kể cả khi chúng tạo ra cùng một tín hiệu.

Input

• Dòng đầu gồm hai số nguyên n và k.
• n dòng tiếp theo, mỗi dòng chứa một xâu gồm các chữ cái thường tiếng Anh.

Output

In ra số cách thỏa mãn, lấy dư cho 1 000 000 007.

Ràng buộc

• 1 ≤ n ≤ 16
• 1 ≤ k ≤ 20
• Tổng độ dài các xâu không vượt quá 100

Ví dụ 1

Input

1 1
uiaoj

Output

55

Giải thích: Không chèn ký tự nào có 1 cách. Chèn vào đầu hoặc cuối xâu có 52 cách. Ngoài ra, chèn u ngay sau ký tự đầu tiên hoặc chèn j ngay trước ký tự cuối cùng cũng tạo được từ khóa uiaoj. Tổng cộng có 1 + 52 + 2 = 55 cách.

Ví dụ 2

Input

2 2
uiaoj
uiaoj

Output

218

Giải thích: Có 2 thứ tự ghép hai xâu. Với mỗi thứ tự, có 1 cách không chèn và 54 cách chèn ký tự vẫn giữ được ít nhất hai lần xuất hiện của uiaoj. Kết quả là 2 × (1 + 54) = 110—sau khi tính cả các cách chèn ở mỗi xâu theo vị trí và chỉ số riêng, tổng số cách là 218.