题目描述

Cuber QQ 参加了一档幸运抽奖节目，节目组准备了 n 个形状、材质完全相同的不透明小球，编号为 1,2,…,n。同时，n 名选手已经按照某个固定顺序排成第 1 名到第 n 名。Cuber QQ 是其中第 k 名选手。

节目一共进行 n 轮。在第 i 轮：

1. 第 i 名选手从箱子中等概率随机抽取一个还没有被抽走的小球，并且不放回；

2. 所有已经抽到球的选手按照自己球上的编号从大到小排名；

3. 球号最大的 $min(i,m)$ 名选手各获得一份礼物。

注意：同一名选手可能在多轮中多次获得礼物。Cuber QQ 想知道，他获得礼物次数的期望是多少。

输入格式

一行三个整数 n,m,k，分别表示选手人数、每轮最多获得礼物的人数，以及 Cuber QQ 在队伍中的排名。

输出格式

输出一个实数，表示 Cuber QQ 获得礼物次数的期望。你的答案满足绝对误差或相对误差不超过 $10^{-6}$ 即可。也就是说，设你的答案为 a，标准答案为 b，当 $\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$ 时，答案会被判为正确。

样例

5 2 5

0.400000000000

样例解释

Cuber QQ 在第 5 轮才抽球。此时共有 5 名选手抽到了球，球号最大的 2 名选手获得礼物。由于 Cuber QQ 的球号在这 5 个球中的相对排名是均匀随机的，所以他获得礼物的概率为 $\frac25=0.4$。

数据规模与约定

对于全部测试数据：$1\le m,k\le n\le 10^7$ 。

原题链接

原题链接