Tách từ

View as PDF

Submit solution


Points: 0.33 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Croatian OI 2006
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một từ cần được tách thành các đoạn con sao cho mỗi đoạn con thuộc một tập các từ cho trước.

Viết chương trình xác định số cách tách một từ cho trước.

Do kết quả có thể có giá trị lớn, chỉ cần in ra phần dư của kết quả cho ~1337377~.

Input

  • Dòng đầu tiên chứa một từ với tối đa ~300000~ ký tự.
  • Dòng thứ hai chứa số nguyên ~N~, ~1\leq N \leq 4000~.
  • Mỗi dòng trong số ~N~ dòng tiếp theo chứa một từ trong tập các từ. Mỗi từ có độ dài không quá ~100~ ký tự. Không có hai từ nào giống nhau. Tất cả các ký tự đều là chữ cái Latin in thường.

Output

  • In ra một số nguyên duy nhất là phần dư của số cách tách từ khi chia cho ~1337377~.

Sample Input 1

abcd
4
a
b
cd
ab

Sample Output 1

2

Sample Input 2

afrikapaprika
4
afr
ika
pap
r

Sample Output 2

1

Sample Input 3

ababababababababababababababababababababab
3
a
b
ab

Sample Output 3

759775

Comments

Please read the guidelines before commenting.



  • -1
    thangdz   commented on 11, Jan, 2022, 21:35

    very interesting