Teacher Herkabe has decided to rank his students again. This time, he wants his list to also be aesthetically pleasing, so he has decided that similar names (those beginning with the same letter or sequence of letters) must be close to one another on the list. Therefore, he has devised the following rule:

For every two names on the list that begin with the same letter sequence, all names between them on the list must also begin with that letter sequence.

For example, consider the names MARTHA and MARY (characters from a beautiful story). They both begin with the sequence MAR, so names beginning with the same sequence (like MARCO and MARVIN) can appear in between (but not MAY, for example).

Notice that the lexicographically sorted ordering always satisfies this rule, but it is by no means the only valid ordering. Your task is determining how many different orderings satisfy the rule, i.e. how many options teacher Herkabe has for his ranking list.

Input Specification

The first line of input contains the positive integer ~N~ ~(3 \le N \le 3000)~, the number of names.

Each of the following ~N~ lines contains a single name: a sequence of between ~1~ and ~3000~ (inclusive) uppercase English letters. The names are distinct and given in no particular order.

In test data worth a total of ~60/140~ points, the number ~N~ will be smaller than ~10~.

Output Specification

The first and only line of output must contain the required number of possible ranking lists, modulo ~1\,000\,000\,007~.

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