시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 71 17 14 37.838%

문제

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