Ghép từ

Trong thế giới mã hóa và nén dữ liệu, một bài toán kinh điển là phân tích một xâu đã cho thành các từ có trong từ điển. Bài toán này có ứng dụng thực tế trong nhiều lĩnh vực như xử lý ngôn ngữ tự nhiên (tokenization), nén dữ liệu (dictionary compression), và phân tích cú pháp (parsing).

Giả sử bạn là một nhà phân tích ngôn ngữ tại công ty AI-Tech, đang làm việc với một hệ thống xử lý văn bản tiên tiến. Bạn được cung cấp:

• Một xâu mục tiêu \(S\) có độ dài \(n\), chứa các ký tự từ 'a' đến 'z'
• Một từ điển chứa \(k\) từ khác nhau, mỗi từ cũng chỉ chứa các ký tự từ 'a' đến 'z'

Nhiệm vụ: Hãy đếm số cách khác nhau để tạo ra xâu \(S\) bằng cách ghép các từ trong từ điển (mỗi từ có thể được sử dụng nhiều lần và các từ có thể ghép theo bất kỳ thứ tự nào, nhưng phải tạo ra chính xác xâu \(S\)).

Input

Dữ liệu vào có định dạng như sau:

• Dòng đầu tiên chứa xâu \(S\) có độ dài \(n\) \((1 \le n \le 5000)\).
• Dòng thứ hai chứa số nguyên \(k\) \((1 \le k \le 10^5)\) - số lượng từ trong từ điển.
• \(k\) dòng tiếp theo, mỗi dòng chứa một từ trong từ điển. Các từ là duy nhất (không trùng nhau) và tổng độ dài của tất cả các từ không vượt quá \(10^6\).

Output

In ra một số nguyên duy nhất là số cách tạo xâu \(S\) từ các từ trong từ điển. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo \(10^9 + 7\).

Example

ababc
4
ab
abab
c
cb

2

Scoring

• Subtask 1 (20 điểm): \(n \le 20\), \(k \le 100\), tổng độ dài các từ \(\le 1000\)
• Subtask 2 (30 điểm): \(n \le 100\), \(k \le 1000\), tổng độ dài các từ \(\le 10000\)
• Subtask 3 (25 điểm): \(n \le 1000\), \(k \le 10000\), tổng độ dài các từ \(\le 100000\)
• Subtask 4 (25 điểm): Không có ràng buộc thêm (giới hạn tối đa)