This page is still under construction.

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

Fortune From Folly

Time limit1sMemory limit1024 MB

Summary
Given n, k, and success probability p, find the expected number of independent Bernoulli trials until the last n trials contain k successes.
Level

Medium6 of 10

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

Problem

Your friend Ómar's favourite video game is Striker-Count. But he has now grown tired of actually playing the game and is more interested in the lootboxes found in the game. Inside each lootbox there is an item of some level of rarity. Ómar is only interested in acquiring the rarest items in the game. When he starts the game, he chooses two numbers nn and kk, such that k≤nk \le n. He then opens lootboxes in the game until kk of the last nn lootboxes included an item of the highest rarity.

This activity amuses Ómar, but does not interest you in the slightest. You are more interested in the numbers: you know that each lootbox Ómar opens has probability pp of containing an item of highest rarity, independently for each lootbox. You want to find the expected number of lootboxes Ómar will open before concluding his process.

Input

The only line of the input contains the two integers nn and kk (1≤k≤n≤61 \le k \le n \le 6), and the real number pp (0<p≤10 < p \le 1 and pp has at most four decimals after the decimal point), with meanings as described above.

Output

Output the expected number of lootboxes Ómar must open, with a relative error of at most 10−610^{-6}. It is guaranteed that the input is such that this expected number does not exceed 10910^9.

Examples2

  1. Example 1

    Input
    3 2 0.0026
    
    Expected output
    74445.39143490087
    
  2. Example 2

    Input
    6 1 0.0026
    
    Expected output
    384.61538461538464