문자열 나누기

문자열 $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로 나눈 나머지를 출력한다.