Thuật toán Aho-Corasick DP: Đếm xâu không chứa các mẫu cấm

Mô tả bài toán

Cho tập hợp gồm M xâu mẫu cấm P = {p₁, p₂, …, p_M} chỉ gồm các chữ cái tiếng Anh in thường ('a' đến 'z').

Cho số nguyên dương L.

Yêu cầu: Đếm số lượng xâu có độ dài đúng bằng L chỉ gồm các chữ cái in thường sao cho xâu đó không chứa bất kỳ xâu cấm nào trong P dưới dạng xâu con liên tiếp. Kết quả lấy dư theo modulo 10⁹ + 7.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên M, L (1 ≤ M ≤ 50, 1 ≤ L ≤ 1000).
• M dòng tiếp theo, mỗi dòng gồm một xâu p_i có độ dài từ 1 đến 20. Tổng độ dài của tất cả các xâu cấm không vượt quá 200.

Dữ liệu ra

• In ra một số nguyên duy nhất là số lượng xâu thỏa mãn theo modulo 10⁹ + 7.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• Thời gian chạy tối đa: 1500ms.
• Giới hạn bộ nhớ: 256MB.
• Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.