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\).

Constraint

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

Example

Note

Các cách có thể là ab\(+\)ab\(+\)c và abab\(+\)c.