시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB187704841.026%

## 문제

You are given a string t and a set S of N different strings. You need to separate t such that each part is included in S.

For example, the following 4 separation methods satisfy the condition when t = abab and S = {a, ab, b}.

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

Your task is to count the number of ways to separate t. Because the result can be large, you should output the remainder divided by 1,000,000,007.

## 입력

The input consists of a single test case formatted as follows.

N
s1
.
.
.
sN
t

The first line consists of an integer N (1 ≤ N ≤ 100,000) which is the number of the elements of S. The following N lines consist of N distinct strings separated by line breaks. The i-th string si represents the i-th element of S. si consists of lowercase letters and the length is between 1 and 100,000, inclusive. The summation of length of si (1 ≤ iN) is at most 200,000. The next line consists of a string t which consists of lowercase letters and represents the string to be separated and the length is between 1 and 100,000, inclusive.

## 출력

Calculate the number of ways to separate and print the remainder divided by 1,000,000,007.

## 예제 입력 1

3
a
b
ab
abab


## 예제 출력 1

4


## 예제 입력 2

3
a
b
c
xyz


## 예제 출력 2

0


## 예제 입력 3

7
abc
ab
bc
a
b
c
aa
aaabcbccababbc


## 예제 출력 3

160


## 예제 입력 4

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


## 예제 출력 4

461695029