단어 나누기

긴 단어 하나와 단어 집합 S가 주어진다. 긴 단어를 왼쪽부터 차례로 여러 작은 단어로 나누려고 한다. 각 작은 단어는 반드시 S에 포함되어 있어야 한다.

긴 단어를 조건에 맞게 나누는 방법의 수를 구하시오. 경우의 수가 매우 커질 수 있으므로 1337377로 나눈 나머지를 출력한다.

첫째 줄에 긴 단어가 주어진다. 단어의 길이는 최대 300,000이다.

둘째 줄에 집합 S에 포함된 단어의 개수 N이 주어진다. (1 ≤ N ≤ 4,000)

다음 N개 줄에는 집합 S의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 최대 100이고, 알파벳 소문자로만 이루어져 있다. 같은 단어는 두 번 주어지지 않는다.

긴 단어를 집합 S의 단어들로 나누는 방법의 수를 1337377로 나눈 나머지를 첫째 줄에 출력한다.