Description

This time, teacher Herkabe wants his ranking list to be pleasing to the eye as well, so he decided that names with the same prefix must be adjacent on the list. Therefore, he made the following rule: for any two names on the list that share a common prefix, all names between them in the ranking should also have this prefix.

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

Input Format

The input has $n+1$ lines.

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

Output Format

Output one line containing the number of different ranking lists teacher Herkabe can make, modulo $10^9+7$.

3
IVO
JASNA
JOSIPA

4

5
MARICA
MARTA
MATO
MARA
MARTINA

24

4
A
AA
AAA
AAAA

8

Hint

Constraints

There are $7$ test points in total. The constraints for each test point are shown in the table below.

For all testdata, each string has length in $[1,3000]$, contains only uppercase English letters, and all names are guaranteed to be distinct.

Source

This problem is from COCI 2012-2013 CONTEST 3 T5 HERKABE. According to the original testdata settings, the full score is $140$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5