Có một xâu ký tự cần phải chia ra thành các đoạn con (gồm các ký tự liên tiếp của xâu) sao cho mỗi đoạn con này là một từ trong tập danh sách các từ cho trước.

Yêu cầu: Đếm số cách chia khác nhau có thể có. Hai cách chia được gọi là khác nhau nếu có ít nhất một vị trí cắt khác nhau. Vì con số này có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho 1337377.

Input:

• Dòng 1: Chứa xâu ký tự cần chia có độ dài không quá 3∙〖10〗^5 ký tự.

• Dòng 2: Chứa số nguyên dương n (1≤n≤4000) - số từ có trong danh sách

• Dòng 3...n+2: Mỗi dòng chứa một từ trong danh sách. Tất cả các từ có độ dài không vượt quá 100 và chỉ chứa các chữ cái tiếng Anh in thường.

Output:

Một số nguyên duy nhất - kết quả tìm được.

Sample Input

abcd
4
a
b
cd
ab

Sample Output

2