### Problem Statement

We have a bag that contains N balls of different colors. In each turn we pick two balls from the bag, one after another, and paint the second one with the first one's color. After the paint dries, we put both balls back into the bag and shuffle its contents.

You are given a String colors describing the initial colors. More precisely, each character in colors corresponds to a single ball. Balls represented by equal characters have the same color.

Return the expected number of turns until all the balls have the same color.

### Definition

 Class: ColorfulBalls Method: expectedStepCount Parameters: String Returns: double Method signature: double expectedStepCount(String colors) (be sure your method is public)

### Notes

-The returned value must be accurate to within a relative or absolute value of 1E-9.

### Constraints

-colors will contain between 1 and 24 characters, inclusive.
-Each character in colors will be an uppercase letter ('A'-'Z').

### Examples

0)

 `"AB"`
`Returns: 1.0`
 In the first turn we will paint one ball with the other's color, and we are done.
1)

 `"Q"`
`Returns: 0.0`
 If there is just a single ball, all balls already have the same color, and thus the correct answer is zero.
2)

 `"AAAAAAA"`
`Returns: 0.0`
 All balls already have the same color.
3)

 `"ZCZ"`
`Returns: 3.0`
4)

 `"KLM"`
`Returns: 4.0`
 After the first turn we are sure to get a situation that's similar to the one in the previous example.
5)

 `"AAABB"`
`Returns: 11.666666666666668`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8782

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12016&pm=8782

misof

#### Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming, Math