Maximum Swimming Pool Area Probability

In a rectangular sea grid of dimensions $N\times1001$ (meters), each unit square (of size $1\,\text{m}\times1\,\text{m}$) is independently safe with probability $q$ and dangerous with probability $1-q$. The bottom side of the grid corresponds to a private beach. A swimming pool is defined as a subgrid (i.e. a rectangle) that (1) is entirely safe, (2) is a contiguous $a\times b$ block of unit squares, and (3) has its bottom side flush with the bottom of the grid (i.e. it is adjacent to the beach).

For any configuration of safe/dangerous cells, let the achievable swimming pool areas be determined by selecting any contiguous block of columns and considering the number of consecutive safe cells starting from the bottom in each chosen column; the swimming pool area is the product of the number of columns and the minimum number of consecutive safe cells (from the bottom) among those columns. Among all valid choices, the one with the maximum area will be chosen. For example, when $N=5$, if the bottom rows have a pattern such that one may choose a $1\times4$ rectangle along the bottom row (area $4$) or a $3\times1$ rectangle in a certain column (area $3$), the chosen swimming pool is the one with area $4$ because it is maximum.

Assume that in each column, the number of consecutive safe cells from the bottom (i.e. the column height) is a random variable $h$ with the following distribution: for $r=0,1,2,\dots,1000$,[ P(h=r)=q^r(1-q),]and[ P(h=1001)=q^{1001}.]These random variables are independent across the $N$ columns. Hence, the maximum safe rectangle (which touches the beach) has an area equal to the maximum over all contiguous intervals of columns of ( L \times \min_{\text{in the interval}}, h_i ), where $L$ is the length (number of columns) of the interval.

Your task is: given $N$, $q$, and an integer $K$, compute the probability that the maximum swimming pool area is exactly $K$. That is, if we denote by $M$ the maximum area over all valid (bottom‐touching) subgrids, you need to compute
[ P(M = K).]
Note: All formulas must be typeset in (\LaTeX) format. You may assume that $N$ is small (for example, $N\le 5$) so that an algorithm with state‐space dynamic programming based on the classical largest rectangle in a histogram (using a stack) can be used. In this approach, one processes the columns one by one. For a new column with value $x$, the algorithm first pops from the stack until the top of the stack has a value not greater than $x$, updating the current maximum rectangle area using the formula
[ \text{area} = h \times (i - j),] where $h$ is the height popped and $j$ is the index stored with it. After processing all $N$ columns, the stack is flushed to update the final maximum area. The answer is then given by the probability (evaluated over the randomness of the $h_i$’s) that this maximum area equals exactly $K$.

inputFormat

The input consists of a single line containing three values:

• An integer $N$ ($1 \le N \le 5$) representing the number of columns of the grid.
• A floating‐point number $q$ ($0 \le q \le 1$) representing the probability that a given unit square is safe.
• An integer $K$ ($0 \le K \le 1001\cdot N$) representing the target swimming pool area.

All numbers are separated by spaces.

outputFormat

Output a single floating–point number: the probability that the maximum swimming pool area (as defined above) is exactly $K$. The answer will be accepted if it is correct within a relative or absolute error of $10^{-6}$.

sample

5 0.5 4

0.####