P7758 [COCI 2012/2013 #3] HERKABE

Herkabe 老师决定再次对他的学生进行排名。

这一次，Herkabe 老师希望他的排行榜在审美上也是令人愉快的，所以他决定有相同前缀的名字必须在名单上彼此相邻。因此，他制定了一个规定：**对于名单上每两个有相同前缀的名字，在排行榜上他们之间的所有名字也应当有这一个前缀**。 现在，给定 $n$ 个学生的名字，求 Herkabe 老师能制作出多少个不同的排行榜以满足上述规则。由于结果可能很大，你只需要输出这个答案对 $10^9+7$ 取模的结果。

输入共 $n+1$ 行。 第一行一个整数 $n$，表示学生的个数。 随后 $n$ 行，每行一个字符串，表示每个学生的名字。

输出仅一行，表示 Herkabe 老师能制作出不同的排行榜的个数模 $10^9+7$ 的值。

**【数据范围】** 本题一共 $7$ 个测试点，各个测试点的数据范围如下表所示： | 测试点编号 | $n\leqslant$ | | :-----------: | :-----------: | | $1\sim 3$ | $10$ | | $4\sim 7$ | $3000$ | 对于所有数据，字符串的长度在 $[1,3000]$ 之间，仅包含大写英文字母且保证互不相同。 **【题目来源】** 本题来源自 **_[COCI 2012-2013](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T5 HERKABE_**，按照原题数据配置，满分 $140$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。