Problem Background

Herkabe the teacher has decided to rank his students again.

Problem Description

This time, Herkabe wants his ranking list to be aesthetically pleasing, so he has decided that names with the same prefix must be adjacent to each other on the list. Therefore, he has established a rule: for every two names on the list that share a prefix, all names between them must also share this prefix.

Given the names of $n$ students, calculate how many different ranking lists Herkabe can create that satisfy the above rule. Since the result may be very large, you only need to output the result modulo $10^9+7$.

Input Format

The input consists of $n+1$ lines.

The first line contains an integer $n$, representing the number of students.
The following $n$ lines each contain a string, representing the name of each student.

Output Format

Output a single line, representing the number of different ranking lists Herkabe can create, modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
IVO
JASNA
JOSIPA

Sample Output #1

4

Sample Input #2

5
MARICA
MARTA
MATO
MARA
MARTINA

Sample Output #2

24

Sample Input #3

4
A
AA
AAA
AAAA

Sample Output #3

8

Notes

[Data Range]

There are a total of 7 test cases, and the data range for each test case is as follows:

For all data, the length of the strings is between $[1,3000]$, consisting only of uppercase English letters and guaranteed to be unique.

[Problem Source]

This problem is from COCI 2012-2013 CONTEST 3 T5 HERKABE, configured according to the original problem data, with a full score of $140$ points.

Provided by Eason_AC for translation and arrangement.

见题面 Input 部分

见题面 Output 部分