Word Division

Time limit1sMemory limit128 MB

Summary

Count the number of ways to split a long word (up to length 300,000) into consecutive substrings all belonging to a dictionary of up to 4000 short words, modulo 1337377.

Level: Medium6 of 10
Topics: Dynamic programming, String matching, Trie, String
Solved: No attempts yet

Problem

You are given one long word and a set S of shorter words. Split the long word from left to right into several smaller words, where every smaller word must belong to S.

Compute the number of valid splits. Because the answer can be very large, output it modulo 1337377.

Input

The first line contains the long word. Its length is at most 300,000.

The second line contains N, the number of words in S. (1 ≤ N ≤ 4,000)

Each of the next N lines contains one word in S. Each word has length at most 100 and consists only of lowercase English letters. No two words are the same.

Output

Print one line containing the number of ways to split the long word into words from S, modulo 1337377.

Examples3

Example 1
Input
```
abcd
4
a
b
cd
ab
```
Expected output
```
2
```
Example 2
Input
```
afrikapaprika
4
afr
ika
pap
r
```
Expected output
```
1
```

Example 3

Input

ababababababababababababababababababababab
3
a
b
ab

Expected output