Migrated from Lutece 807 Caruta

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

This problem is related to Karuta, which is a card game. To make it easy to understand, direct model is given here.

You are given some strings. And there's no string that is a prefix of another.

The strings are read in a random orders. When you are able to recognize which string is being read, you interrupt the reading.

Let's take an example. Here abc, acd and bcd are given. And there are in fact $3! = 6$ orders to read these strings. One of the order may be like this:

1. You heard a for the first time, and you would know the string being read must be abc or abd, but you coundn't tell the exact one.
2. Then you heard b, you would know it is abc being read, and you interrupt the reading. The a new string was going to be read.
3. Then you heard a, since abc wouldn't be read one more time, you would know it is acd being read, and interrupt it.
4. At last, you don't even listen to any single letter and know it is bcd going to be read.

So the total letter you have to listen in this order will be $3$.

What we want to know is the expectation number, in all orders, of the letter you would here after all the strings are read.

Input

The first line of the input contains an integer $N$, indicating the number of strings.

The next $N$ lines contain a string, each line. The strings will only contain letter a - z. The total length of the strings will not exceed $10^5$.

Output

Output the expectation number of the characters you would hear after all the strings are read, rounded to $6$ digits after decimal point.

Samples

3
abc
acd
bcd

3.000000

Resources

the 12th UESTC Programming Contest Final