Bạn được cho một xâu độ dài \(n\) và một từ điển chứa \(k\) từ. Bạn có thể tạo xâu bằng các từ theo nhiêu cách?

Input

• Dòng đầu vào đầu tiên có một xâu chứa \(n\) kí tự giữa a - z
• Dòng thứ hai có một số nguyên \(k\): số từ trong từ điển
• Cuối cùng là \(k\) dòng mô tả các từ. Mỗi từ là duy nhất và bao gồm các ký tự a - z

Output

• In số cách chia lấy dư cho \(10^9 + 7\)

Constraints

• \(1 \leq n \leq 5000\)
• \(1 \leq k \leq 10^5\)
• Tổng độ dài của các từ tối đa là \(10^6\)

Example

ababc
4
ab
abab
c
cb

2