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.
InputThe 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.
OutputThe first and only line of output should contain the number from the task description modulo 1337377.
Input
Output
abcd
4
a
b
cd
ab Output
2Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.