Background

Gatling roulette is a wellness game.

Problem Description

Unlike gambling games with pistols such as Russian roulette, the game tool in Gatling roulette is a Gatling gun.

The rules of Gatling roulette are simple: bullets are loaded into some parts of the Gatling’s magazine. The players sit at a round table, and take turns aiming the Gatling at their own head and pulling the trigger for one second. Anyone who gets shot is eliminated immediately. The one who lasts to the end is the winner.

We use a Gatling gun with the latest 2019 technology. Its features are no warm-up needed and unlimited bullets. For each person, in each round, the probability of getting shot is exactly the same, $P_0$.

There are $n$ long-necked deer in each game. Starting from long-necked deer $1$, they play in increasing order by number, going around the round table in a loop.

The game may go through multiple cycles, and ends when only the last long-necked deer remains.

Given $P_0$ and $n$, find the probability $P_k$ that long-necked deer $k$ will eventually become the only survivor.

If $P_0=0$, we consider deer $1$ to be the winner.

Input Format

Only one line with three numbers, $P_0,n,k$.

Output Format

Output a floating-point number $P_{k}$. The error should be less than $10^{-8}$. (Please keep more digits after the decimal point.)

0.5 2 1

0.33333333

0.5 2 2

0.66666667

0.5 3 1

0.23809524

0.5 3 2

0.28571429

Hint

• For $10\%$ of the testdata, $n \le 100$.
• For $30\%$ of the testdata, $n \le 500$.
• For another $20\%$ of the testdata, $k = n$.
• For $100\%$ of the testdata, $1 \le k \le n \le 10^{4}, 0 \le P_0 \le 1$.

For all testdata, the time limit is 1000 ms and the memory limit is 256 MB. $O2$ optimization is allowed.

Translated by ChatGPT 5