Đếm số cách tách từ bằng Trie

General
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho từ điển gồm $n$ từ phân biệt và một xâu $S$. Hãy đếm số cách tách xâu $S$ thành một dãy các từ liên tiếp đều nằm trong từ điển (một từ có thể được dùng nhiều lần). Vì kết quả có thể rất lớn, hãy in ra phần dư khi chia cho $10^9 + 7$.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$. $n$ dòng tiếp theo chứa các từ trong từ điển. Dòng cuối cùng chứa xâu $S$.

Dữ liệu ra

In ra số cách tách từ modulo $10^9 + 7$.

Ví dụ
Input Output
4
a
b
ab
ba
aba
3
Giới hạn
  • $1 \le n \le 5000$
  • $1 \le |S| \le 5000$
  • Tổng độ dài các từ trong từ điển $\le 10^5$
Draft saved