25928번 - Lightbulbs 스페셜 저지다국어

문제

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.

입력

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

출력

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

제한

• 1ドル ≤ N, M ≤ 2000$
• 0ドル ≤ P ≤ 1$

힌트