Expected Time to Reach Zero

We are given a board with 1 row and n+1 columns numbered from 0 to n. Initially, a chess piece is placed at column m (with 0 ≤ m ≤ n). Every second the piece is moved according to the following random process:

• If the piece is not on column n, it will move one step to the left with probability prb and one step to the right with probability 1 - prb.
• If the piece is at column n, it is forced to move one step to the left.

The process stops when the piece reaches column 0. It can be shown that the expected number of seconds E[m] required to reach 0 is a rational number. In particular, when prb ≠ 1/2 one may show that

\[ E[m] = \frac{2(1-prb)^2}{(1-2prb)^2} \cdot \left(\frac{1-prb}{prb}\right)^{n-1}\cdot \Bigl(1 - \Bigl(\frac{prb}{1-prb}\Bigr)^m\Bigr) - \frac{m}{1-2prb}. \]

When prb = 1/2, the recurrence degenerates and the solution is

\(E[m] = -m^2 + 2nm\).

Your task is to compute E[m] modulo 109+7. To avoid precision issues, the probability prb is given as a decimal string (for example, 0.3 or 0.5) with at most 6 digits after the decimal point. It is recommended to convert the probability to a rational number. It is guaranteed that the answer, interpreted as a rational number, exists and is unique modulo 109+7.

inputFormat

The input consists of a single line containing three values:

• An integer n (the maximum column index, with n ≥ 1).
• An integer m (the starting column, 0 ≤ m ≤ n).
• A decimal number prb representing the probability to move left (with at most 6 digits after the decimal point).

For example:

5 2 0.3

outputFormat

Output a single integer, the expected number of seconds to reach column 0 modulo 109+7.

sample

3 1 0.5

5