Hiện nay, khi công nghệ thông tin phát triển, con người thường trao đổi với nhau bằng điện thoại, fax hay email. Hãy quay ngược thời gian lại 100 năm, khi đó con người không có điện thoại hay fax, lại càng chẳng có email, người ta phải liện lạc với nhau bằng mật mã MORSE. Đây là loại mật mã mà các kí tự chỉ được mã hóa bằng 2 kí hiệu “.” (tích) và “-“ (tè). Để chuyển đi một văn bản, người ta mã hóa từng chữ cái trong văn bản đó thành những dãy kí tự tích tè. Trên thế giới đã quy định một quy tắc mã hóa chuẩn như sau:

Hạn chế của cách mã hóa này là một dãy mã hóa có thể có nhiều cách giải mã. Ví dụ dãy -.-..-- có thể được hiểu là CAT hay NXT đều đúng. Rõ ràng là trong trường hợp bình thường, chúng ta sẽ phải hiểu là CAT vì NXT không có nghĩa. Tuy vậy một dãy mã hóa vẫn có thể có nhiều cách giải mã có nghĩa.

Yêu cầu: Bạn có trong tay một dãy đã mã hóa và một danh sách các từ có nghĩa, bạn hãy tính xem có bao nhiêu cách giải mã có nghĩa. (Một cách giải mã có nghĩa là một cách chia đoạn MORSE ban đầu thành các đoạn con liên tiếp sao cho mỗi đoạn được giải mã thành một từ có nghĩa)

Dữ liệu: 

- Dòng thứ nhất ghi xâu đã mã hóa gồm không quá 10000 kí tự tích tè;

- Dòng thứ hai ghi số n là số các từ có nghĩa (n ≤ 1000);

- Trong n dòng tiếp theo, mỗi dòng ghi một từ có nghĩa. Các từ là các xâu không rỗng gồm không quá 10 kí tự trong số các kí tự ‘A’ .. ‘Z’.

Kết quả: Ghi số P là phần dư số cách giải mã có nghĩa chia cho 10000007.