\(3^{rd}\) round, December \(15^{th}\), 2012

Teacher Herkabe has decided to rank his students again. This time, he wants his list to also be
aesthetically pleasant, 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.

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

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.

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

생성자가 기록되지 않았습니다.

출처 COCI 2012/2013 Contest 3