Lightbulbs

Interview

Time limit1sMemory limit256 MB

Summary

Given an N by M grid where each bulb works with probability P, find the expected length of the longest horizontal run of working bulbs.

Level: Medium5 of 10
Topics: Dynamic programming, Probability
Solved: No attempts yet

Problem

Thomas Edison is working on a better version of a lightbulb. In his current experiment, he covers entire fields with batches of lightbulbs and tests them. He arranged $N$ rows with $M$ lightbulbs in each row. Each lightbulb works with probability $P$ . Otherwise, it is faulty and does not light up. Thomas wants the expected length of the longest horizontal run of working lightbulbs.

For example, in the grid below, 1 is a working lightbulb and 0 is a faulty one. The longest horizontal run of working lightbulbs has length 3. The second row has three consecutive ones, and so does the fourth row.

Only horizontal runs count.

Input

Three numbers are given on one line, separated by spaces: positive integers $N$ and $M$ , and a real number $P$ .

Output

Print the answer to the problem. Your answer is accepted if its absolute or relative error is less than $10^{-4}$ .

Constraints

$1 \le N, M \le 2000$
$0 \le P \le 1$

Examples2

Example 1
Input
```
2 3 0.5
```
Expected output
```
1.828125000000
```
Example 2
Input
```
47 74 1
```
Expected output
```
74.000000000000
```