Problem Description

After successfully adhering to local customs, you just made it in time for the ship's departure. However, you didn't expect so many people to be heading to Lübeck! Since you don't want to be late for the award ceremony (and you still need some time to store all the stolen art in your hotel), you want to speed up the boarding process.

There is a row of $n$ seats on the ship, and $n$ passengers have booked all the seats. Each passenger has a ticket indicating their designated seat and one of $g$ boarding groups.

During boarding, passengers from one group are called at a time. Passengers within each group board in a random order, meaning all possible boarding sequences are equally likely. Each passenger can board either in front of the first seat or behind the last seat, and then move to their designated seat before another passenger boards.

You determine that the process is most time-consuming when a passenger has to pass by already seated passengers (the luggage containing all those ties is quite a hindrance in the aisle). Fortunately, you found a staff uniform in a nearby locker, so you can decide the order of boarding groups and inform each passenger beforehand whether to board from the front or the back of all seats.

Write a program that, using the ticket information, calculates the expected minimum number of times a passenger has to pass by already seated passengers during the boarding process if you determine the boarding order of the groups and assign passengers to the front and back.

Notes

Given a boarding order of groups and assigning passengers to the front and back, the expected number of times a passenger has to pass by already seated passengers is defined as:
$$1 \cdot p_1 + 2 \cdot p_2 + 3 \cdot p_3 + \ldots$$
where $p_k$ is the probability that a passenger has to pass by exactly $k$ already seated passengers during boarding. In other words, this is the average number of times a passenger has to pass by already seated passengers across all possible boarding sequences within each group.

Input Format

The input consists of a string of $n$ characters $s_1 \dots s_n$, where $s_i$ is one of the first $g$ uppercase English letters, indicating the boarding group of the passenger in the $i$-th seat (the first seat being seat number 1).

Output Format

Output a real number representing the expected minimum number of times a passenger has to pass by already seated passengers if you determine the boarding order of the groups and assign passengers to the front and back.

Your output is considered correct if the absolute error is no more than $0.001$.

Sample Input and Output

Sample Input #1

AACCAA

Sample Output #1

1

Sample Input #2

HEHEHEHIHILOL

Sample Output #2

7.5

Sample Input #3

ONMLKJIHGFEDCBAABCDEFGHIJKLMNO

Sample Output #3

0

Notes

For all data, $1 \le g \le 15$ and $1 \le n \le 10^5$.

见题面 Input 部分

见题面 Output 部分