This page is still under construction.

Parts of this page are still being built. What you see may change.

Chocolate

Time limit1sMemory limit128 MB

Summary
For C equally likely colors, after N draws where matching pairs are eaten, find the probability that exactly M colors remain on the table.
Level

Medium6 of 10

Topics
Dynamic programming, Combinatorics, Probability, Math
Solved
No attempts yet

Problem

You have a large package of chocolates that come in CC different colors, and every color is equally likely to be drawn. You repeatedly take one chocolate at a time and place it on the table.

Whenever two chocolates of the same color are on the table, you immediately eat both of them and remove them from the table. Because of this rule, every color that is on the table appears at most once, so the number of chocolates on the table equals the number of distinct colors currently present.

Given the number of colors CC, a number of draws NN, and a target count MM, compute the probability that exactly MM chocolates remain on the table after NN chocolates have been drawn.

Input

The input contains several test cases, one per line. Each test case is a line with three non-negative integers CC, NN, and MM (C≤100C \le 100 and N,M≤1,000,000N, M \le 1{,}000{,}000).

The input is terminated by a line containing a single zero, which is not a test case and must not be processed.

Output

For each test case, print on its own line the probability that exactly MM chocolates are on the table after NN draws, rounded to exactly three decimal places.

Examples3

  1. Example 1

    Input
    5 100 2
    
    0
    
    Expected output
    0.625
    
  2. Example 2

    Input
    4 0 0
    0
    
    Expected output
    1.000
    
  3. Example 3

    Input
    1 3 1
    2 1 1
    5 100 2
    0
    
    Expected output
    1.000
    1.000
    0.625