P7758 [COCI 2012/2013 #3] HERKABE

Teacher Herkabe decided to rank his students once again.

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$.

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 one line containing the number of different ranking lists teacher Herkabe can make, modulo $10^9+7$.

**Constraints** There are $7$ test points in total. The constraints for each test point are shown in the table below. | Test Point ID | $n\leqslant$ | | :-----------: | :-----------: | | $1\sim 3$ | $10$ | | $4\sim 7$ | $3000$ | 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](https://hsin.hr/coci/archive/2012_2013/) [CONTEST 3](https://hsin.hr/coci/archive/2012_2013/contest3_tasks.pdf) T5 HERKABE_**. According to the original testdata settings, the full score is $140$ points. Translated and organized by [Eason_AC](https://www.luogu.com.cn/user/112917). Translated by ChatGPT 5