Per được cho một xâu ~s~ có độ dài ~n~ và một từ điển gồm ~k~ từ.

Hỏi có bao nhiêu cách ghép các từ trong từ điển lại với nhau để tạo thành đúng xâu ~s~? Mỗi từ có thể được dùng nhiều lần.

Dữ liệu vào

• Dòng đầu tiên chứa xâu ~s~ gồm ~n~ ký tự thuộc 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ừ gồm các ký tự a–z. Các từ đôi một khác nhau.

Kết quả

In ra số cách ghép, lấy phần dư khi chia cho ~10^9 + 7~.

Ví dụ

Đầu vào:

ababc
4
ab
abab
c
cb

Đầu ra:

2

Giải thích: Hai cách ghép là ab + ab + c và abab + c.

Giới hạn

• ~1 \le n \le 5000~
• ~1 \le k \le 10^5~
• Tổng độ dài các từ trong từ điển không vượt quá ~10^6~

Gọi ~f_i~ là số cách ghép được ~i~ ký tự đầu của ~s~, với ~f_0 = 1~. Khi đó ~f_i = \sum f_{i-L}~ với mọi từ điển có độ dài ~L~ khớp với đoạn ~s[i-L+1..i]~. Hãy đưa từ điển vào một cấu trúc tra cứu (cây tiền tố, hoặc bảng băm theo từng độ dài) để tìm nhanh các từ khớp.