Ghép Chuỗi Bằng Từ Điển

Một cách ghép xâu là một dãy từ trong từ điển mà khi nối theo đúng thứ tự sẽ thu được toàn bộ xâu đích. Mỗi ký tự phải thuộc đúng một từ và không được bỏ qua ký tự nào.

Đếm số cách chia toàn bộ xâu đích thành một dãy từ trong từ điển, giữ nguyên thứ tự ký tự. Hai cách khác nhau khi tập vị trí cắt của chúng khác nhau.

Input

• Dòng đầu chứa xâu đích $s$.
• Dòng thứ hai chứa số nguyên $k$, số từ trong từ điển.
• $k$ dòng tiếp theo chứa các từ của từ điển.

Output

• In số cách ghép $s$ từ các từ trong từ điển, lấy phần dư theo $1000000007$.

Constraints

• $1\le |s|\le 5000$.
• $1\le k\le 10^5$.
• $s$ và mọi từ chỉ gồm các chữ cái thường $a$ đến $z$.
• Các từ trong từ điển đôi một khác nhau.
• Tổng độ dài $k$ từ không quá $10^6$.

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

ba
3
b
a
ba

2