← 목록으로

메이플스토리 연주회

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

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

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

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

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

입력 형식

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

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

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

출력 형식

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

입력 예제 1

3
ABCA
AB
CA
ABABCA

출력 예제 1

2

입력 예제 2

3
A
AA
AAA
AAAA

출력 예제 2

7

채점 방식

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

해설