Tổ Hợp Từ

Cho xâu có độ dài $n$ và từ điển gồm $k$ từ. Đếm số cách tạo thành xâu đã cho bằng cách nối các từ trong từ điển.

In ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

Dòng đầu tiên chứa xâu cần tạo (gồm các ký tự a-z).

Dòng thứ hai chứa số nguyên $k$: số từ trong từ điển.

• $k$ dòng tiếp theo, mỗi dòng chứa một từ trong từ điển.

Dữ liệu ra

In ra số cách tạo xâu, modulo ${10}^9+7$.

Ràng buộc

• $1\le n\le 5000$
• $1\le k\le {10}^5$
• Tổng độ dài các từ trong từ điển $\le {10}^6$

Ví dụ