문자열 나누기

시간 제한2초메모리 제한512 MB

요약

문자열 t를 주어진 N개의 문자열 조각으로 나누는 방법의 수를 1,000,000,007로 나눈 나머지로 구한다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트라이, 문자열 매칭, 문자열
정답자: 아직 제출이 없습니다

문제

문자열 $t$ 와 서로 다른 문자열 $N$ 개로 이루어진 집합 $S$ 가 주어진다. $t$ 를 여러 조각으로 나누되, 각 조각이 $S$ 의 원소가 되도록 해야 한다.

예를 들어 $t$ = abab, $S$ = {a, ab, b}이면 조건을 만족하는 분할 방법은 다음 4가지이다.

a, b, a, b
a, b, ab
ab, a, b
ab, ab

$t$ 를 나누는 방법의 수를 구하시오. 답이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

N
s1
.
.
.
sN
t

첫째 줄에 $S$ 의 원소 개수 $N$ ( $1 \le N \le 100{,}000$ )이 주어진다. 다음 $N$ 개 줄에 서로 다른 문자열 $N$ 개가 한 줄에 하나씩 주어진다. $i$ 번째 문자열 $s_i$ 는 $S$ 의 $i$ 번째 원소이다. $s_i$ 는 알파벳 소문자로만 이루어지며 길이는 1 이상 100,000 이하이다. 모든 $s_i$ ( $1 \le i \le N$ )의 길이의 합은 200,000 이하이다. 마지막 줄에 나눌 문자열 $t$ 가 주어진다. $t$ 는 알파벳 소문자로만 이루어지며 길이는 1 이상 100,000 이하이다.

출력

$t$ 를 나누는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제4

예제 1
입력
```
3
a
b
ab
abab
```
예상 출력
```
4
```
예제 2
입력
```
3
a
b
c
xyz
```
예상 출력
```
0
```

예제 3

입력

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc

예상 출력

예제 4

입력

10
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

예상 출력

461695029