Expected Repaints for Balls

Time limit2sMemory limit128 MB

Summary

Given N colored balls, compute the expected number of random repaint operations needed until all balls share one color.

Level: Hard8 of 10
Topics: Probability, Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

Sejun has a bag containing N colored balls. One operation works as follows. First, he chooses one ball from the bag, then chooses a different ball from the bag. He repaints the second ball so that it has the same color as the first ball. After the paint dries, he puts both balls back into the bag and mixes them.

Find the expected number of repaint operations needed until all balls have the same color.

Input

The first line contains the number of balls N. (1 ≤ N ≤ 24)

The second line contains a string of length N describing the colors of the balls. The string has no spaces, and each character is one uppercase English letter from A to Z.

Output

Print the expected number of repaint operations needed until all balls have the same color.

Your answer is accepted if its absolute or relative error is at most 10^-8.

Examples6

Example 1
Input
```
3
ABA
```
Expected output
```
3.0
```
Example 2
Input
```
2
AB
```
Expected output
```
1.0
```
Example 3
Input
```
1
Q
```
Expected output
```
0.0
```
Example 4
Input
```
7
AAAAAAA
```
Expected output
```
0.0
```
Example 5
Input
```
3
KLM
```
Expected output
```
4.0
```
Example 6
Input
```
5
AAABB
```
Expected output
```
11.666666666666668
```