cho.sh

Gem Island

At each of d steps a uniformly random gem splits in two; find the expected total held by the r largest holders after d splits.

Hard8ProbabilityDynamic programmingCombinatoricsMathNo attempts yetTime limit3sMemory limit1024 MB

Problem

Gem Island is a tiny island in the middle of the Pacific Ocean. Until recently it was known as one of the poorest and most peaceful places on Earth. Today it is neither poor nor peaceful. What happened?

One sunny morning, not too long ago, all inhabitants of Gem Island woke up to a surprise. Each of them was holding one sparkling gem. The gems had appeared overnight by magic. Everybody was suddenly rich, everybody could finally afford the things they had dreamed of, and the name of the island made much more sense.

The next morning one of the inhabitants woke up to another surprise. Her gem had split into two gems. The same thing happens on every night that follows: exactly one of the gems on the island, picked uniformly at random among all gems there, splits into two.

After a while the inhabitants held widely varying numbers of gems. A few had a lot and many had only a few. How come some inhabitants had more gems than others? Did they cheat, were they just lucky, or was something else at work?

The island elders have asked for your help. They want you to determine whether pure chance explains the uneven distribution of gems. If it does, tensions on the island drop a great deal.

The island has nn inhabitants. You are to determine the gem distribution after dd nights of gem splitting. The value of interest is the expected number of gems held together by the rr people with the largest numbers of gems. Stated precisely, suppose that after dd nights the numbers of gems held by the nn inhabitants are sorted in non-increasing order as a1≥a2≥⋯≥ana_1 \ge a_2 \ge \cdots \ge a_n. What is the expected value of a1+⋯+ara_1 + \cdots + a_r?

Input

The first line contains three integers nn, dd and rr separated by spaces (1≤n,d≤5001 \le n, d \le 500, 1≤r≤n1 \le r \le n).

Output

Print the expected number of gems held by the top rr inhabitants after dd nights, rounded to exactly nine digits after the decimal point. Pad with zeros so that all nine digits are always printed. If the expected value lies exactly halfway between two candidates, round it up.