시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 20 7 5 27.778%

문제

세준이는 가방을 하나 가지고 있다. 이 가방 속에는 N개의 공이 들어있다. N개의 공엔 색이 칠해져 있다. 세준이는 이 가방에서 색이 서로 다른 두 개의 공을 하나씩 차례대로 고른다. 그 후에 두 번째로 고른 공을 첫 번째로 고른 공의 색으로 색 칠한다. 그 후, 공이 마르면, 두 공을 다시 가방에 집어 넣고 섞는다.

세준이는 이 공의 색이 모두 같아지려면 몇 번을 색 칠해야 하는지 궁금해졌다.

세준이가 공을 칠해야 하는 횟수의 기댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 공의 개수 N(1 ≤ N ≤ 24)이 주어진다. 둘째 줄에 공에 칠해진 N개의 색이 공백없이 주어진다. 색은 알파벳 대문자(A - Z)중 하나이다.

출력

첫째 줄에 세준이가 공을 색 칠하는 회수의 기댓값을 출력한다. 정답과의 절대/상대 오차는 10-8까지 허용한다.

예제 입력

3
ABA

예제 출력

3.0

힌트

출처