Ghép Chuỗi Từ Từ Điển

Đếm số cách nối một dãy từ trong từ điển để nhận đúng chuỗi đích, với thứ tự ký tự được giữ nguyên.

Một cách ghép là một dãy từ có phép nối đúng bằng $s$. Một từ có thể được chọn lại; hai cách khác nhau khi dãy vị trí kết thúc các từ khác nhau.

Input

• Dòng đầu chứa chuỗi đích $s$.
• Dòng thứ hai chứa số nguyên $k$.
• $k$ dòng tiếp theo chứa các từ trong từ điển, đôi một khác nhau.

Output

• In số cách biểu diễn $s$ thành phép nối của một hoặc nhiều từ trong từ điển, lấy modulo $1000000007$.

Constraints

• $1\le |s|\le 5000$.
• $1\le k\le 10^5$.
• $s$ và các từ chỉ gồm chữ cái thường $a,\dots ,z$.
• Các từ trong từ điển đôi một khác nhau.
• Tổng độ dài của $k$ từ không vượt quá $10^6$.
• Mỗi từ trong từ điển có thể được dùng nhiều lần ở các vị trí khác nhau.

Scoring

• Subtask $1$ ($50\%$ số điểm): $|s|\le 100,k\le 100$ và $\text{tổng độ daˋi từ điển}\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

aaaa
3
a
aa
aaa

7