2022 Fall Waterloo Local Contest, Problem B

Thomas Edison is actively working on a better version of a lightbulb. During that process, he covers entire fields with batches of lightbulbs and conducts tests on them. In his current experiment, he arranged $N$ rows with $M$ lightbulbs in each row. Each lightbulb has a chance $P$ of working, otherwise, it's faulty and won't light up. Thomas wants to find the expected value of the length of the longest horizontal sequence of lightbulbs that are working.

For example, in the setup below, where $1$ is a working lightbulb and $0$ is faulty, the length of the longest horizontal sequence of lightbulbs that are working is $3$, since there are three consecutive ones in the second row (and also in the fourth row).

1 0 1 1
0 1 1 1
0 1 0 0
1 1 1 0
1 1 0 1

Note that we're interested in horizontal sequences only.

Constraints

$1\le N,M\le 2000$

$0\le P\le 1$

Input Specification

You're given three numbers separated by spaces – positive integers $N$ and $M$, and a real number $P$.

Output Specification

Output the answer to the problem. Your answer would be considered correct if its absolute or relative error is less than ${10}^{-4}$.

Sample Input 1

2 3 0.5

Sample Output 1

1.828125000000

Sample Input 2

47 74 1

Sample Output 2

74.000000000000