Expected Top Gem Sum on Gem Island

The tiny Gem Island in the Pacific Ocean has experienced a magical phenomenon. Initially, each of the n inhabitants wakes up holding one sparkling gem. However, over the next d nights, a surreal event occurs: on each night one gem, chosen uniformly at random from all gems on the island, splits into two gems. Consequently, after d nights the total number of gems becomes n + d and the distribution of gems among the inhabitants is random.

Let the final gem counts of the inhabitants be sorted in non‐increasing order as \[ a_{(1)} \ge a_{(2)} \ge \cdots \ge a_{(n)}. \] The island elders are interested in the expected value of the sum of the gems held by the top r richest inhabitants, i.e., they want to compute \[ E\Bigl[\sum_{j=1}^{r}a_{(j)}\Bigr]. \]

It is known from the theory of Pólya’s urn (starting with one gem per person) that when d > 0 the final gem proportions follow a Dirichlet distribution with parameters all equal to 1. In this case the expected value of the j-th largest proportion is \[ E[X_{(j)}] = \frac{H_{j}^*}{n}, \quad \text{for } j=1,2,\dots,n, \] where the numbers H_j^* are given by \[ H_{j}^* = H_n - H_{j-1}, \quad H_k = \sum_{i=1}^{k}\;\frac{1}{i},\; \; H_0=0. \] Thus, when d > 0 the expected sum of gems held by the top r inhabitants is \[ E\Bigl[\sum_{j=1}^{r}a_{(j)}\Bigr] = (n+d) \cdot \frac{1}{n} \sum_{j=1}^{r} (H_n - H_{j-1}). \]

Note that when d = 0 no gem splits occur and every inhabitant keeps exactly one gem; hence the answer is simply r.

Your task is to compute the expected sum of the gems held by the top r inhabitants given n, d, and r. Print the answer as a real number, and your answer will be accepted if it has an absolute or relative error of at most 1e-6.

Input Format: Three integers n, d and r separated by spaces.

Output Format: A single real number representing the expected sum.

inputFormat

The input consists of a single line containing three space‐separated integers:

• n (the number of inhabitants),
• d (the number of nights during which a gem splits), and
• r (the number of top inhabitants to consider).

Constraints:

• n ≥ 1, d ≥ 0, and 1 ≤ r ≤ n.

outputFormat

Output a single real number: the expected sum of gems held by the top r inhabitants. The answer is accepted if its absolute or relative error does not exceed 1e-6.

sample

2 0 1

1.000000