Word Division

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.

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.

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