B. Simulation
time limit per test
1.5 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Rami and Oussama frequently talk about simulations, and how on many occasions, order arises from disorder during many simualtions.

To test this observation, Oussama conceived the following simulation:

Initially, he will have an array $$$A$$$ of size $$$n$$$ filled with zeros. Then, he will do $$$m$$$ times these two steps:

$$$\quad$$$1. Select a number $$$k$$$ uniformly in $$$\{1,\dots n\}$$$

$$$\quad$$$2. Increment $$$A_k$$$ by $$$1$$$

Upon investigating the simulation, he noted that sometimes, there is atleast one element which grows too much. So he wanted to know how likely such an event occurs by doing the following:

$$$\quad$$$1. He chose the size of the array $$$n,$$$ and a threshold $$$K$$$.

$$$\quad$$$2. He applied $$$m$$$ steps of the simulation on this array, and memorized the content of the array at the final state.

$$$\quad$$$3. Finally, He masked the content of the array, and invited Rami to guess the probability that there exists at least one element of $$$A$$$ greater or equal to the chosen threshold $$$K.$$$

As the question is a little bit hard, Oussama asked you to help Rami about it.

Input

One line containing $$$3$$$ integers: $$$n,m,K$$$ where:

- $$$1 \leq n \leq 300:$$$ the size of the array $$$A$$$.

- $$$0 \leq m \leq 300:$$$ the number of steps of the simulation.

- $$$0\leq K \leq m:$$$ the threshold.

Output

print a real number $$$0\leq p\leq 1$$$ the probability that at least one of the elements of $$$A$$$ is greather than or equal to $$$K$$$ after $$$m$$$ steps of the simulation.

Examples
Input
2 10 6
Output
0.753906
Input
300 300 5
Output
0.671265
Input
10 3 2
Output
0.28
Note

For the first test case, we have a simulation with an array of size $$$2,$$$ and $$$10$$$ iterations. The threshold is $$$K\ge 6,$$$ the only case when $$$\max(A_1,A_2) \lt 6$$$ is when $$$A_1=A_2=5.$$$ There are $$${10 \choose 5}$$$ possible scenarios where $$$A_1=A_2=5$$$ out of the $$$2^{10}$$$ possible scenarios. Thus the probability that $$$A_1\ge 6$$$ or $$$A_2 \ge 6$$$ is : $$$$$$ p=1-\frac{1}{2^{10}}\times{10 \choose 5}=1-\frac{10!}{(5!)^22^{10}} =\frac{193}{256} \approx 0.75390625 $$$$$$ Where $$${a \choose b}=\frac{a!}{b!(a-b)!}$$$ is the binomial coefficient.