MORSEDEC - Morse decoding

Giới hạn
  • Thời gian: 0.699s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

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:

 

A

.-

B

-...

C

-.-.

D

-..

E

.

F

..-.

G

--.

H

....

I

..

J

.---

K

-.-

L

.-..

M

--

N

-.

O

---

P

.--.

Q

--.-

R

.-.

S

...

T

-

U

..-

V

...-

W

.--

X

-..-

Y

-.--

Z

--..

 

 

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. 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 có nghĩa là một cách chia đoạn code ban đầu thành các đoạn con liên tiếp sao cho mỗi đoạn là một từ có nghĩa)

Input

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 khoảng “A” đến “Z”.

Output

Gồm một dòng duy nhất ghi số P là phần dư số cách giải mã có nghĩa khi chia cho 1 triệu (mod 1 000 000).

Example

Input:
.---.--.-.-.-.---...-.---.
6
AT
TACK
TICK
ATTACK
DAWN
DUSK 
Output:
2

  • Người up: skyvn97
  • Nguồn bài: ACM Central European Programming Contest, Warsaw 2001