17365번 - 별다줄

먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문장을 만들 수 있었다. 그러나 문장이 너무 길어지자 사람들은 문장에서 각 단어의 첫 글자만 따서 "liril"과 같이 한 단어로 줄여 쓰기 시작했다. 하지만 문래빗어에 단어가 점점 늘어나자 첫 글자만 남겨서는 도저히 원래 문장을 알 수 없게 되었고, 사람들은 각 단어의 앞부분에서 한 글자 이상의 부분 문자열을 따서 이어붙이도록 규칙을 바꾸었다. 예를 들어 "lion is ryan is lion"이라는 문장이 있다면 "lion is ryan is lion"과 같이 따 와서 "liisryanilio"로 줄여 쓰는 것이다. 이렇게 문장을 줄여 쓴 것으로 추정되는 정체불명의 단어들은 지금도 고고학자들의 큰 관심사 중 하나라고 한다.

고고학자 종영이는 최근 문래빗어 사전을 하나 발견했다. 이 사전에는 수많은 단어가 적혀 있는데, 그중에는 똑같은 단어들도 여럿 있을 수 있다. 이들은 실제로는 다른 단어인데, 발음을 표현할 문자가 부족해서 이렇게 된 것이다. 예를 들어 사전에 "aa"라는 단어가 두 개 있다면 "aa aa"는 2 × 2 = 4가지의 다른 문장으로 해석될 수 있다.

종영이는 이 사전을 토대로 유적에서 발견된 문래빗어 단어를 해석해 보기로 했다. 하지만 종영이는 아직 어떤 문장이 더 자연스러운 문장인지, 어떤 단어에서 몇 글자를 뽑는 게 가장 흔한 용례인지 모르기 때문에 단어를 해석하려면 모든 가능성을 전부 나열해 볼 수밖에 없다. 만약 어떤 두 방법에서 사용된 문장이 다르거나, 같은 문장을 사용했더라도 따 온 글자 수가 다른 단어가 존재한다면 둘은 다른 방법이다. 예를 들어 앞의 예시에서는 제시된 방법 외에도 "lion is is ryan is lion"과 같이 따 오는 방법이 존재한다. 다른 예시로 사전에 "aa" 하나만 있을 때 "aaa"를 해석하려고 한다면 "aa aa aa", "aa aa", "aa aa" 세 가지의 가능성이 있다.

종영이가 몇 가지의 가능성을 검토해 봐야 하는지 미리 구해 보자.

첫 줄에 종영이가 발견한 사전에 적혀 있는 단어의 수 N(1 ≤ N ≤ 10⁶)이 주어진다.

다음 N개의 줄에 걸쳐 단어들이 한 줄에 하나씩 주어진다. 단어들은 모두 알파벳 소문자로 이루어져 있고, 단어 하나의 길이는 1글자 이상 300글자 이하이며 모든 단어의 길이의 총합은 10⁶글자 이하이다.

다음 줄에 종영이가 해석하려는 단어가 주어진다. 이 단어 역시 알파벳 소문자로만 이루어져 있으며, 길이는 1글자 이상 200,000글자 이하이다.

주어진 단어를 만들 수 있는 모든 방법의 수를 10⁹+7로 나눈 나머지를 출력한다.