A random binary number X contains n independent random binary digits (bits) denoted by b1, b2, b3, ... , bn, where b1 is the most significant bit and bn is the least significant bit. That is, the value of X is b12n-1 + b22n-2 + b32n-3 + ... + bn20. For each i, the random bit bi is 1 with probability pi percents ( 0 <= pi <= 100) and bi is 0 with probability (100 - pi) percents. Given the integer n ( 1 <= n <= 200), the integers p1, p2, p3, ... , pn, and the integers Q ( 2 <= Q<= 99) and R ( 0 <= R < Q), your program should output the probability of the event that X mod Q is equal to R, where mod is the modulus operation. In other words, your program should output the probability Pr{X modQ = R}. The output probability must be rounded to 5 digits after the decimal point.
For example, consider a test case with (n, p1, p2, p3, p4, Q, R) = (4, 0, 90, 100, 80, 5, 3). Your program should output 0.08000, since
Pr{X mod 5 = 3} = Pr{X = 3} + Pr{X = 8} + Pr{X = 13}
= Pr{(b1b2b3b4) = (0011)} +Pr{(b1b2b3b4) = (1000)} + Pr{(b1b2b3b4) = (1101)}
= (100 - 0)% . (100 - 90)% . 100% . 80%
+ 0% . (100 - 90)% . (100 - 100)% . (100 - 80)%
+ 0% . 90% . (100 - 100)% . 80%
= 0.08000
Note: The above example is for explanation. The straightforward algorithm in the example may not meet our time constraint when input integers are much larger. You should develop another more efficient algorithm.
Technical Specification
The ranges of input integers are: 1<= n<= 200, 0 <= pi<=100 for each i, 2 <= Q <= 99, and 0 <= R < Q.
The first line of the input file contains an integer indicating the number of test cases to follow. Then the input (n, p1, p2, p3, ... , pn, Q, R) of each test case is given in a separated line. All integers are separated by one space.
For each test case, your program should output the probability of the event that X mod Q is equal to R in a separate line. The probability must be rounded to 5 digits after the decimal point.