Magic Machine

Time Limit: 3 Seconds
Memory Limit: 32768 KB

In order to celebrate the 8th anniversary of ZOJ, ZJU ACM coach CYJJ buys a magic machine. But now she has some difficulties with it T_T.

At first, let me show you how the magic machine works:

The input data for the machine is a sequence of *n* positive numbers. After reading all the data in, it will return a number
which is considered to be **magic**. A number is **magic** if and only if it appears in the input sequence and its value is the
*Kth* smallest one in the value set of the input. For example, if the numbers are 1 1 1 2, then the 2nd smallest is 2.

Furthermore, we have known the algorithm about how the machine calculates its answer. Let's consider each input a "query interval"
(then **original **input can be considered a interval*[1, n]*). The magic machine will just work like this:

ele process(*left*, *right*, ele seq[]) {
if(interval*[left, right]* is illegal or empty)
return a number that never appear in the input data;
else {
random choose one position i that *left <= i <= right* {
the chance of returning the number seq*[i]* is *a*;
the chance of returning the answer for process(*left*, *i - 1*, seq) is *b*;
the chance of returning the answer for process(*i + 1*, *right*, seq) is *1* - *a* - *b*;
}
}
}

CYJJ wants to know the chance to get a **magic number** for a specific input using her magic machine. Now she turns to you, can
you help her?

**Input**

The input contains multiple test cases, each test case begins with a single integer *n*(*n* <= 200) which indicates the size of the input sequence.
A negtive n indicates the end of input.
Then *n* positive integers follow to specify the input sequence. The last part of input is a line with one integer *K*(1 <= *K* <= *n*) and
two float numbers *a* and *b*(0 <= *a + b* <= 1).

**Output**

For each test case output the chance CYJJ can get a **magic number**, exact to three digits to the right of the decimal point.

**Sample Input**

1
1
1 1 0
2
1
2
2 0.3 0.5
-1

**Sample Output**

1.000
0.180

Author:

**HE, Xing**
Source:

**ZOJ 8th Anniversary Contest**
Submit
Status