Đúng lúc An hào hứng làm bài tập tin học nhất thì bàn phím lại bị hỏng: chỉ gõ được các ký tự chữ cái. Nhiệm vụ của An là soạn thảo một văn bản chỉ sử dụng \(\mathbf{n}\) từ trong một danh sách cho trước. An quyết định vẫn làm bài tập trên máy của mình, sau đó copy sang máy của một bạn khác trong lớp và chèn thêm dấu cách vào giữa các từ, giữa hai từ sẽ chèn đúng một dấu cách. Như vậy ít ảnh hưởng đến thời gian sử dụng máy của bạn nhất.

Ví dụ: với n = 5 và danh sách các từ cho trước là an, anh, han, tin, hoc; An soạn sẵn dòng anhanhoctin, sau đó mang sang máy của bạn và chèn thêm dấu cách thành anh an hoc tin.

Tuy nhiên khi bắt tay vào chèn dấu cách, An mới nhận thấy rằng vấn đề cũng không đơn giản vì có thể có nhiều cách, thậm chí có thể không có cách chèn nếu gõ văn bản sai.Ví dụ: với dòng anhanhoctin ta có một cách đặt dấu cách khác thỏa mãn là: an han hoc tin.

Yêu cầu: Cho \(\mathbf{n}\), danh sách các từ được sử dụng (mỗi từ có thể được sử dụng trong văn bản nhiều lần hoặc không dùng lần nào) và văn bản không có dấu cách. Hãy xác định số cách chèn kí tự trắng (dấu cách) để được một văn bản chỉ gồm các từ có trong \(\mathbf{n}\) từ đã cho.

Dữ liệu vào:

+ Dòng đầu tiên chứa số nguyên \(n\ (1\ < \ n\ \leq \ 100)\).

+ \(n\) dòng sau: mỗi dòng chứa một từ được sử dụng (mỗi từ không quá 20 ký tự, các từ khác nhau từng đôi một).

+ Dòng cuối cùng chứa văn bản An đã gõ chứa không quá 100 kí tự.

Kết quả:

+ Một số nguyên xác định số cách chèn dấu cách.

Ví dụ:

(Giải thích: Hai cách đặt dấu cách là: anh an hoc tin; an han hoc tin)