Tennis Tournament

All submissions for this problem are available.
Caroline is a huge tennis fan. She loves watching tennis and especially rooting for players of Strangeland, her native country.
Generally, tennis tournaments are played using the Olympic system. Let's consider such a tournament with N = 2^{K} players. This tournament is held in K rounds. In each round, every player plays exactly one match against some other player. The loser of each match is eliminated, and the winner advances to the next round. After the K^{th} round, there's only one noneliminated player who is declared the champion of the tournament.
An example of such a tournament for N = 8 can be seen in the picture below.
We'll number the players from 1 to N from top to bottom in the tournament draw for a given N. In the first round players 1 and 2, 3 and 4, ..., N1 and N play a match against each other. In the second round the winners of the match between players 1 and 2 and the match between players 3 and 4 play together, the winners of the match between players 5 and 6 and the match between players 7 and 8 play together, ..., the winners of the match between players N3 and N2 and the match between players N1 and N play together. The matches are played in the same way till the K^{th} (final) round.
A big tennis tournament is going to start soon. M Strangelandian players are taking part in this tournament, and their positions in the tournament draw are known in advance. Caroline wants to know the probability that a Strangelandian player will be the champion of this tournament. She collected the information from the previous ten years of tennis history and knows that a Strangelandian player wins a match over a nonStrangelandian player with probability P percents. All nonStrangelandian players look the same to Caroline, so she considers the chance of winning a match between two nonStrangelandian players to be 50 percents for both players. The same applies to all Strangelandian players. For Caroline, all of them are equally strong, and she thinks that both of them can win a Strangelandian derby with 50percent probability.
Help Caroline write a program which calculates the probability that a Strangelandian player will win the tournament.
Input
The first line of the input contains a single integer T, the number of test cases (no more than 20). Each test case is described by exactly two lines. The first of these lines contains three spaceseparated integers N, M and P (2 ≤ N ≤ 2^{30}, N = 2^{K} for some integer K, 1 ≤ M ≤ 10000, M ≤ N, 0 ≤ P ≤ 100)  the total number of players in the tournament, the number of competing Strangelandian players and the probability that a Strangelandian player beats a nonStrangelandian player in percents, respectively. The second of these lines contains M spaceseparated distinct integers A_{i} (1 ≤ A_{i} ≤ N), the 1based positions of Strangelandian players in the tournament draw.
Output
For each test case output exactly one line containing the required probability in percents. Your answer will be considered correct if its absolute error doesn't exceed 10^{6}.
Example
Input: 4 2 1 42 1 4 2 66 1 2 4 2 66 1 3 8 3 71 3 5 2 Output: 42.00000000000000 66.00000000000000 73.18080000000000 75.47784648840000
Author:  gennady.korotkevich 
Tester:  gamabunta 
Tags  cook27, dynamicprogramming, gennady.korotkevich, probability 
Date Added:  13102012 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 