KTH Challenge 2016 Open

#### Start

2016-06-12 10:00 CEST

## KTH Challenge 2016 Open

#### End

2016-06-12 14:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -547 days 12:41:37

4:00:00

0:00:00

# Problem DDice Betting

Gunnar and his friends like games which involve rolling dice. Gunnar has a huge collection of 6-sided, 12-sided and 20-sided dice. All the games with dice started to bore him, so he came up with a new game. He rolls an $s$-sided die $n$ times and wins if at least $k$ different numbers appear in the $n$ throws. An $s$-sided die contains $s$ distinct numbers $1, \dots , s$ on its sides.

Since this is a game only for one person, Gunnar and his friends decided to make it more fun by letting other people bet on a particular game. Before you bet on a particular game, you would like to know how probable it is to throw at least $k$ different numbers in $n$ throws with an $s$-sided die. We assume that all numbers have the same probability of being thrown in each throw.

## Input

The input consists of a single line with three integers $n$, $s$, and $k$ ($1\le n\le 10\, 000, 1 \le k \le s \le 500$). $n$ is the number of throws, $k$ the number of different numbers that are needed to win and $s$ is the number of sides the die has.

## Output

Output one line with the probability that a player throws at least $k$ different numbers within $n$ throws with an $s$-sided die. Your answer should be within absolute or relative error at most $10^{-7}$.

Sample Input 1 Sample Output 1
3 3 2

0.888888889

Sample Input 2 Sample Output 2
3 3 3

0.222222222