Cho tập \(S\) gồm \(n\) xâu \(S_1, S_2, ..., S_n\) (độ dài mỗi xâu \(|S_i| \le 100\)) và một xâu \(X\) \((|X| \le 10^5)\). Đếm số lượng cách tách \(X\) thành các xâu con liên tiếp sao cho các xâu con này đều thuộc tập \(S\).

Dữ liệu vào

• Dòng đầu chứa số nguyên dương \(n\) \((n \le 10^4)\);
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\);
• Dòng cuối cùng chứa xâu \(X\).

Dữ liệu ra

• Số cách tìm được. Lấy kết quả modulo \(10^9+7\)

Ràng buộc

• 30% số test: \(|X| \le 20, n \le 10\);
• 30% số test: \(20 \lt |X| \le 10.000, n \le 100\).

Input 1

3  
a  
b  
ab  
abab

Output 1

4

Giải thích

4 cách tách là:
a/b/a/b
ab/a/b
a/b/ab
ab/ab