Beautiful Names

Time limit1sMemory limit512 MB

Summary

Count the number of orderings of N distinct strings such that all strings sharing a common prefix always form a contiguous block, modulo 1e9+7.

Level: Medium6 of 10
Topics: Trie, Combinatorics, Recursion
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3
IVO
JASNA
JOSIPA
```
Expected output
```
4
```
Example 2
Input
```
5
MARICA
MARTA
MATO
MARA
MARTINA
```
Expected output
```
24
```
Example 3
Input
```
4
A
AA
AAA
AAAA
```
Expected output
```
8
```