severina

문제

A word needs to be divided into smaller pieces in such a way that each piece is from some given set of words. 

Write a program that will find the number of different ways to divide the given word. 

Since that number can be really big, you have to output the remainder of it divided by 1337377. 

입력

The first line of input contains the given word with a maximum length of 300 000 characters. 

The second line contains an integer N, 1 ≤ N ≤ 4 000. 

Each of the next N lines contains one word from the set. Each word will be at most 100 characters long. There will be no two identical words and all the characters will be lowercase letters of the English alphabet. 

출력

The first and only line of output should contain the number from the task description modulo 1337377.

abcd
4
a
b
cd
ab

2

afrikapaprika
4
afr
ika
pap
r

1

ababababababababababababababababababababab
3
a
b
ab

759775