Chuỗi DNA Không Bệnh

Một occurrence của mẫu là một đoạn con liên tiếp bằng đúng mẫu đó. Hai occurrence có thể chồng lấn.

Đếm số xâu DNA độ dài đúng $n$ không chứa bất kỳ mẫu cấm nào dưới dạng đoạn con liên tiếp; in kết quả modulo $10^5$.

Input

• Dòng đầu chứa hai số nguyên $m$ và $n$.
• $m$ dòng tiếp theo lần lượt chứa các mẫu cấm. Nếu $m=0$ thì không có dòng nào phía sau.

Output

• In một số nguyên duy nhất: số xâu hợp lệ sau khi lấy modulo $10^5$.

Constraints

• $0\le m\le 10$.
• $1\le n\le 2\cdot 10^9$.
• Mỗi mẫu cấm có độ dài từ $1$ đến $10$ và chỉ gồm $A,C,G,T$.
• Các mẫu có thể trùng nhau; việc lặp lại một mẫu không làm thay đổi tập xâu hợp lệ.

Scoring

• Subtask $1$ ($50$ điểm): $10$ test nhỏ, phù hợp với lời giải trực tiếp theo định nghĩa.
• Subtask $2$ ($50$ điểm): $10$ test không có giới hạn bổ sung.

Example

2 2
A
CG

8