시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23 3 3 20.000%

문제

상근이는 긴 단어를 작은 단어로 나누려고 한다. 이 때, 작은 단어는 모두 입력으로 주어지는 집합 S에 포함되는 단어이어야 한다.

단어를 나누는 방법의 수를 구하는 프로그램을 작성하시오.

경우의 수가 매우 커질 수 있기 때문에 1337377로 나눈 나머지를 출력한다.

입력

첫째 줄에 긴 단어가 주어진다. 이 단어는 최대 300,000글자로 이루어져 있다.

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

다음 N개 줄에는 집합에 포함되어 있는 단어가 한 줄에 하나씩 주어진다. 단어는 최대 100글자로 이루어져 있고, 알파벳 소문자로만 이루어져 있다. 두 단어가 서로 같은 경우는 없다.

출력

첫째 줄에 문제의 설명에 나와있는 것 처럼 긴 단어를 작은 단어로 나누는 경우의 수를 출력한다.

예제 입력

abcd
4
a
b
cd
ab

예제 출력

2

힌트