Expected Prefix Sums in a Random Sequence

Xiaolan really loves random numbers. The TA first chooses a real number \(0<p<1\). Then, \(n\) independent random numbers \(x_1, x_2, \dots, x_n\) are generated as follows:

• \(x_i=1\) with probability \(p\),
• \(x_i=2\) with probability \((1-p)p\),
• \(x_i=3\) with probability \((1-p)^2p\),
• and so on.

After generating the sequence \(x_1,\dots,x_n\), Xiaoi computes its prefix sums \(y_1, y_2, \dots, y_n\), where \(y_i=x_1+\cdots+x_i\). Given four inputs \(n\), \(p\), and two integers \(l\) and \(r\) satisfying \(1\le l\le r\le n\), Xiaolan wonders: what is the expected number of prefix sums \(y_i\) which lie in the interval \([l,r]\)?

The answer is the sum over all \(i=1,\dots,n\) (note that for \(i>r\) the event is impossible since \(y_i\ge i\))

[ E = \sum_{i=1}^{\min(n,r)} \Pr(l \le y_i \le r), ]

where for each valid (i) the probability is given by the negative binomial (Pascal) law:

[ \Pr(y_i = k) = \binom{k-1}{i-1} p^i (1-p)^{k-i}, \quad k\ge i. ]

Thus,

[ \Pr(l \le y_i \le r) = \sum_{k=\max(i,l)}^{r} \binom{k-1}{i-1} p^i (1-p)^{k-i}. ]

Your task is to compute the expected number with an absolute or relative error of at most (10^{-6}).

inputFormat

The input consists of a single line containing four numbers:

1. An integer \(n\) representing the number of random numbers generated.
2. A real number \(p\) (with \(0<p<1\)).
3. Two integers \(l\) and \(r\) with \(1 \le l \le r \le n\).

Values are separated by spaces.

outputFormat

Output a single number: the expected count of prefix sums \(y_i\) that fall in the interval \([l,r]\). The answer should be printed with at least 6 decimal places of precision.

sample

3 0.5 1 2

1.000000