Ball Trajectory Probability on a Modified Galton Board

A triangular wooden board is set up with nails arranged in rows. The board has n rows of nails. In the intact board, row 1 has 1 nail, row 2 has 2 nails, …, and row n has n nails. There are also n+1 slots at the bottom (numbered 0 to n from left to right) such that when a ball is dropped from the top nail and each nail deflects the ball (left or right with probability \(\frac{1}{2}\)), the probability that the ball lands in slot i is given by

[ p_i = \frac{C(n,i)}{2^n} = \frac{n!}{2^n, i!,(n-i)!} ]

In the modified board, some of the nails (except those in the bottom row, which are never removed) have been removed. The ball is released from the top with its center aligned with the top nail. The behavior is as follows:

• If the ball arrives at a nail and that nail is intact, then it is deflected: with probability \(\frac{1}{2}\) it goes to the left child nail and with probability \(\frac{1}{2}\) it goes to the right child nail in the next row.
• If the ball arrives at a nail that has been removed, then no deflection occurs and the ball falls vertically without changing its horizontal alignment; in our discrete model, we assume it will continue to the nail in the next row that is directly below. To remove ambiguity (since the geometric vertical projection lies exactly between two nails), we define the rule that when a nail is missing, the ball proceeds deterministically to the left child nail of the position it would have reached if the nail were present.

The board is arranged so that if the ball goes through all the rows, upon reaching the bottom row (row n, which is always intact), the ball is deflected one final time. That is, from a nail in the bottom row at index j (0-indexed within that row) the ball goes left with probability \(\frac{1}{2}\) to land in slot j and right with probability \(\frac{1}{2}\) to land in slot j+1.

Your task is to calculate the probability \(p_m\) that the ball lands in slot m given the removal of some nails.

Input details: The board is described as follows. The rows are numbered from 0 to n-1 (where row 0 corresponds to the top row, and row n-1 is the bottom row which is always intact). In row r, there are r+1 nails numbered from 0 to r. Only nails in rows 0 to n-2 (i.e. all but the bottom row) may be removed.

inputFormat

The first line contains two integers n and m (with 1 ≤ n ≤ 1000, and 0 ≤ m ≤ n), where n is the number of rows and m is the target slot index.

The second line contains an integer k indicating the number of removed nails.

Each of the following k lines contains two integers r and i (0 ≤ r ≤ n-2 and 0 ≤ i ≤ r), meaning that the nail in row r at position i is removed.

outputFormat

Output a single line containing the probability \(p_m\) that the ball lands in slot m. The answer should be printed as a floating-point number. It is recommended to output at least 6 digits after the decimal point.

sample

3 1
0

0.375000