보석 섬

보석 섬은 태평양 한가운데에 있는 작은 섬이다. 얼마 전까지 이 섬은 세상에서 가장 가난하면서도 가장 평화로운 곳으로 알려져 있었다. 지금은 가난하지도 평화롭지도 않다. 무슨 일이 있었을까?

그리 오래되지 않은 어느 맑은 날 아침, 섬 주민 모두가 눈을 뜨고 놀랐다. 저마다 손에 반짝이는 보석이 하나씩 들려 있었던 것이다. 보석은 밤사이에 마법처럼 나타났다. 모두가 갑자기 부자가 되었고, 오래 꿈꾸던 물건을 마침내 살 수 있게 되었다. 섬 이름도 그제야 어울리게 되었다.

다음 날 아침, 주민 한 명이 또 다른 광경을 보았다. 자기 보석이 두 개로 쪼개져 있었다. 그날 이후 매일 밤 같은 일이 일어난다. 섬에 있는 보석 전체 중에서 정확히 하나가 균등한 확률로 골라지고, 그 보석이 두 개로 쪼개진다.

시간이 지나자 주민이 가진 보석 개수는 제각각이 되었다. 아주 많이 가진 사람이 있는가 하면 몇 개뿐인 사람도 많다. 어떤 주민은 왜 남보다 보석이 많을까? 속임수를 썼을까, 운이 좋았을 뿐일까, 아니면 다른 이유가 있을까?

섬의 원로들이 도움을 청했다. 보석이 고르지 않게 나뉜 이유를 순전한 우연으로 설명할 수 있는지 판단해 달라는 것이다. 그렇게 설명된다면 섬의 긴장이 크게 누그러진다.

섬에는 주민이 $n$명 산다. $d$일 밤 동안 보석이 쪼개진 뒤의 분포를 알아내야 한다. 특히 궁금한 값은 보석을 가장 많이 가진 $r$명이 합쳐서 가지는 보석 개수의 기댓값이다. 정확히 말하면, $d$일 밤이 지난 뒤 주민 $n$명이 가진 보석 개수를 내림차순으로 정렬해 $a_1 \ge a_2 \ge \cdots \ge a_n$이라고 하자. $a_1 + \cdots + a_r$의 기댓값은 얼마인가?

첫째 줄에 정수 $n$, $d$, $r$이 공백으로 구분되어 주어진다. ($1 \le n, d \le 500$, $1 \le r \le n$)

$d$일 밤이 지난 뒤 보석을 가장 많이 가진 $r$명이 합쳐서 가지는 보석 개수의 기댓값을 소수점 아래 아홉째 자리까지 반올림해 출력한다. 자리가 모자라면 0을 채워 소수점 아래 아홉 자리를 항상 모두 출력한다. 기댓값이 두 후보의 정확히 가운데에 놓이면 큰 쪽으로 올린다.