단어 나누기
시간 제한1초메모리 제한128 MB
최대 길이 300,000인 긴 단어를 최대 4000개의 짧은 단어 사전 안의 조각들로 왼쪽부터 분할하는 방법 수를 1337377로 나눈 나머지로 구합니다.
문제
긴 단어 하나와 단어 집합 S가 주어진다. 긴 단어를 왼쪽부터 차례로 여러 작은 단어로 나누려고 한다. 각 작은 단어는 반드시 S에 포함되어 있어야 한다.
긴 단어를 조건에 맞게 나누는 방법의 수를 구하시오. 경우의 수가 매우 커질 수 있으므로 1337377로 나눈 나머지를 출력한다.
입력
첫째 줄에 긴 단어가 주어진다. 단어의 길이는 최대 300,000이다.
둘째 줄에 집합 S에 포함된 단어의 개수 N이 주어진다. (1 ≤ N ≤ 4,000)
다음 N개 줄에는 집합 S의 단어가 한 줄에 하나씩 주어진다. 각 단어의 길이는 최대 100이고, 알파벳 소문자로만 이루어져 있다. 같은 단어는 두 번 주어지지 않는다.
출력
긴 단어를 집합 S의 단어들로 나누는 방법의 수를 1337377로 나눈 나머지를 첫째 줄에 출력한다.