Lottery

Time limit2sMemory limit128 MB

Summary
Given N, M, K, compute the probability that two random M-subsets of 1..N share at least K numbers using the hypergeometric distribution.
Level

Easy3 of 10

Topics
Combinatorics, Math, Probability
Solved
No attempts yet

Problem

Jimin chooses M distinct numbers from 1 through N. The lottery also chooses M distinct numbers from 1 through N.

Jimin wins if at least K numbers appear in both choices. Compute the probability that Jimin wins.

Input

The first line contains three integers N, M, and K, separated by spaces.

Output

Print the probability that Jimin wins. An absolute or relative error of at most 10^{-9} is accepted.

Constraints

  • 2 <= N <= 8
  • 1 <= M <= N-1
  • 1 <= K <= M

Examples4

  1. Example 1

    Input
    3 1 1
    Expected output
    0.3333333333333333

  2. Example 2

    Input
    3 2 1
    Expected output
    1.0

  3. Example 3

    Input
    8 2 1
    Expected output
    0.4642857142857143

  4. Example 4

    Input
    8 4 2
    Expected output
    0.7571428571428571