题目描述

绿宝石之岛是在太平洋中央的一个小岛。之前，该岛还被认为是地球上最贫穷却最安宁的地方之一。但如今，该岛既不贫穷又不和平。发生了什么？

不久前的一天早上，绿宝石之岛的所有居民在一阵惊讶中醒来。那天早上，他们每人的手上多出了一颗闪闪发光的绿宝石。绿宝石是一夜之间神奇地出现的。大家突然变得非常富有，终于可以买得起他们只能在梦中见到的东西，并且岛名有了意义，大家非常高兴。但第二天早上，一个居民醒来时发现，他的绿宝石被神奇地分成了两半！接下来的每天晚上，同样的事情不断地发生。每晚恰好只有一颗绿宝石会分裂，每颗绿宝石都有相等的概率被分成两半。

不久，绿宝石之岛的居民们拥有的绿宝石数量变得不同。一些人有很多绿宝石，但大部分人的绿宝石很少。为什么一些居民的绿宝石数量比别人多得多？是他们作弊了，还是只是很幸运，还是有一些其它的神秘力量？

绿宝石之岛的长老们决定向你求助。他们希望你来判断这种绿宝石数量不均匀分布的现象是否纯粹是由于概率学导致的。如果是这样，岛上的紧张局势会收敛很多。

这座岛有 $n$ 个居民。你需要判断 $d$ 个夜晚后绿宝石分布的期望情况。具体地说，你想知道绿宝石持有数量最多的 $r$ 个人的期望绿宝石总数。形式化的说，设 $d$ 晚后居民绿宝石数量按不增顺序为 $a_1 \ge a_2 \ge ... \ge a_n$，则 $a_1 + ... + a_r$ 的期望值是多少？

输入格式

输入为一行三个整数 $n,d,r (1 \le n,d \le 500, 1 \le r \le n)$，其意义由题面给出。

输出格式

输出持有绿宝石数量最大的 $r$ 个居民的期望绿宝石数量，绝对误差或相对误差不超过 $10^{-6}$.

2 3 1

3.5

3 3 2

4.9

5 10 3

12.2567433

数据范围与提示

$1 \le n,d \le 500, 1 \le r \le n$

在不侵犯原题版权的情况下，本题面中文翻译基于知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议发布，注明出处时需指向本题链接。