메이플스토리 연주회

메이플스토리에는 여러 종류의 몬스터들이 있다. 그리고 이번 여름을 맞이하여 몬스터들이 모여 연주회를 하기로 하였다. 이를 위해 여러 종류의 몬스터 중 $N$개 종류의 몬스터들이 선별되었는데 $i$번째 몬스터의 울음소리는 알파벳 대문자로 구성된 문자열 $S_i$로 표현된다.

에반은 선별된 몬스터들과 함께 연주를 진행하려 한다. 연주는 각 몬스터가 임의의 순서대로 울음소리를 내는 것이다. 에반이 연주하려는 완성된 노래는 알파벳 대문자로 구성된 문자열 $P$로 표현이 된다. 노래를 만들어가던 에반은 문득 자신이 선별한 몬스터들이 이 곡을 연주할 수 있는 모든 경우의 수가 몇 가지가 될지 궁금해졌다.

예를 들어 선별한 몬스터가 리본돼지, 주황버섯, 슬라임으로 구성되어 있고, 리본돼지의 울음소리는 ABCA, 주황버섯의 울음소리는 AB, 슬라임의 울음소리는 CA라 한다면, ABABCA는 (주황버섯 - 주황버섯 - 슬라임) 혹은 (주황버섯 - 리본돼지)로 두 가지 표현이 가능하다.

이 때 주의할 점은 각 몬스터의 각 울음 소리의 문자들은 섞이지 않는다. 예를 들면 리본돼지(ABCA)가 울고, 주황버섯(AB)이 울면, ABCAAB이지, ABCABA 처럼 하나의 울음소리가 쪼개져 다른 울음소리와 섞일 수는 없다.

에반이 원하는 노래의 정보가 주어졌을 때, 선별한 몬스터들의 울음소리를 잘 조합해서 주어진 노래를 연주할 수 있는 모든 경우의 수를 구하자.

입력 형식

첫 줄에는 몬스터들의 종류 수를 나타내는 정수 $N$이 입력으로 주어진다. ($1 \le N \le 100\,000$)

$i+1$번째 줄에는 $i$번째 몬스터의 울음소리인 알파벳 대문자로 구성된 문자열 $S_i$가 입력으로 주어진다. ($1 \le i \le N$; $1 \le S_i\textrm{의 길이} \le 200\,000$; $N \le \textrm{모든 }S_i\textrm{ 길이의 합} \le 200\,000$)

$N+2$번째 줄에는 연주하려는 곡의 정보인 알파벳 대문자로 구성된 문자열 $P$가 입력으로 주어진다. ($1 \le P\textrm{의 길이} \le 200\,000$)

출력 형식

첫 번째 줄에 선별한 몬스터들의 울음소리를 잘 조합해서 주어진 노래를 연주할 수 있는 경우의 수를 $1\,000\,000\,007$($=10^9+7$)로 나눈 나머지를 출력하라.

예제 1

3
ABCA
AB
CA
ABABCA

2

예제 2

3
A
AA
AAA
AAAA

7

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설