Beautiful Names

A teacher wants to arrange the students' names in one line. An order is beautiful if it satisfies the following rule.

For any string prefix, all names that start with that prefix must occupy one contiguous interval in the whole order. Equivalently, between two names that start with the same prefix, every name must also start with that prefix.

Given all student names, count how many beautiful orders are possible.

The first line contains the number of names N. (3 <= N <= 3000)

Each of the next N lines contains one name. Every name has length less than 3000, consists only of uppercase English letters, and all names are distinct.

Print the number of beautiful orders modulo 1,000,000,007.