题目背景

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

题目描述

这一次，Herkabe 老师希望他的排行榜在审美上也是令人愉快的，所以他决定有相同前缀的名字必须在名单上彼此相邻。因此，他制定了一个规定：对于名单上每两个有相同前缀的名字，在排行榜上他们之间的所有名字也应当有这一个前缀。

现在，给定 $n$ 个学生的名字，求 Herkabe 老师能制作出多少个不同的排行榜以满足上述规则。由于结果可能很大，你只需要输出这个答案对 $10^9+7$ 取模的结果。

输入格式

输入共 $n+1$ 行。

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

输出格式

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

3
IVO
JASNA
JOSIPA

4

5
MARICA
MARTA
MATO
MARA
MARTINA

24

4
A
AA
AAA
AAAA

8

提示

【数据范围】

本题一共 $7$ 个测试点，各个测试点的数据范围如下表所示：

对于所有数据，字符串的长度在 $[1,3000]$ 之间，仅包含大写英文字母且保证互不相同。

【题目来源】

本题来源自 COCI 2012-2013 CONTEST 3 T5 HERKABE，按照原题数据配置，满分 $140$ 分。

由 Eason_AC 翻译整理提供。