Herkabe 老师决定再次给他的学生们排名。这一次，他希望他的名单在美学上也是令人愉悦的，因此他决定相似的名字（那些以相同字母或字母序列开头的名字）在名单上必须靠得很近。为此，他制定了以下规则：

对于名单中以相同字母序列开头的任意两个名字，它们之间在名单上的所有名字也必须以该字母序列开头。

例如，考虑名字 MARTHA 和 MARY（一个美丽故事中的角色）。它们都以序列 MAR 开头，因此以相同序列开头的名字（如 MARCO 和 MARVIN）可以出现在它们之间（但例如 MAY 则不行）。

请注意，按字典序排序的顺序总是满足这一规则，但这绝不是唯一有效的顺序。你的任务是确定有多少种不同的顺序满足该规则，即 Herkabe 老师的排名名单有多少种不同的选择。

输入格式

第一行包含一个正整数 $N$ ($3 \le N \le 3000$)，表示名字的数量。

接下来的 $N$ 行，每行包含一个名字：一个长度在 $1$ 到 $3000$（含）之间的由大写英文字母组成的序列。名字是互不相同的，且以无序的方式给出。

输出格式

输出的第一行也是唯一的一行，必须包含满足要求的可能排名名单的数量，模 $1\,000\,000\,007$。

子任务

在价值 60 分的测试数据中，数量 $N$ 将小于 $10$。

样例

输入样例 1

3
IVO
JASNA
JOSIPA

输出样例 1

4

输入样例 2

5
MARICA
MARTA
MATO
MARA
MARTINA

输出样例 2

24

输入样例 3

4
A
AA
AAA
AAAA

输出样例 3

8