Problem Statement 
 A new ride is opened in an amusement park. It consists of N landings numbered from 0 to N1. Some of the landings are connected with pipes. All of the landings are at different heights, so the pipes are all inclined and can only be traversed downwards.
A ridetaker begins his ride at some landing. The pipes are long enough that he cannot see where they lead before entering them. Therefore, at each landing, any descending pipe adjacent to it has an equal probability of being used by a ridetaker who reached this landing.
A ride is finished when a ridetaker reaches a landing which has no adjacent descending pipes. There are two types of such landings: exits and crocodile ponds. If the ridetaker reaches the exit landing, his ride is over and he safely returns home. If one reaches the crocodile pond, his trip is also over, but he never returns home.
You're given a String[] landings describing the ride. Element i of landings describes the ith landing. If the landing is an exit, the ith character of landings[i] will be 'E' and the rest of the characters will be '0's (zeroes). If it is a crocodile pond, the ith character will be 'P' and the rest will be '0's. If the landing has at least one adjacent descending pipe, the jth character of landings[i] will be '1' (one) if a pipe descends from the ith landing to the jth, and '0' (zero) otherwise.
A ridetaker began his ride at a randomly chosen landing, used a total of K pipes throughout his descent and safely returned home afterwards. Each of the landings has the same probability of being chosen as the initial landing of the ride. Compute the probability that he started the ride at landing startLanding. 

Definition 
 Class:  ParkAmusement  Method:  getProbability  Parameters:  String[], int, int  Returns:  double  Method signature:  double getProbability(String[] landings, int startLanding, int K)  (be sure your method is public) 




Notes 
  Your return value must have an absolute or relative error less than 1e9. 

Constraints 
  landings will contain exactly N elements, where N is between 2 and 50, inclusive. 
  Each element of landings will contain exactly N characters. 
  Each character in landings will be '0' (zero), '1' (one), 'E', or 'P'. 
  If the ith element of landings contains an 'E', it will contain only one 'E' as its ith character, and all other characters in that element will be '0'. 
  If the ith element of landings contains a 'P', it will contain only one 'P' as its ith character, and all other characters in that element will be '0'. 
  If the ith element of landings doesn't contain an 'E' or a 'P', it will contain at least one '1' character. The ith character of such element will always be '0'. 
  K will be between 1 and N1, inclusive. 
  startLanding will be between 0 and N1, inclusive. 
  There will be no cycles in landings, i.e. it's never possible to return to the same landing after descending through several pipes. 
  There will be at least one landing from which it is possible to reach an exit using exactly K pipes. 

Examples 
0)  
 {"E000",
"1000",
"1000",
"1000"}  1  1 
 Returns: 0.3333333333333333  The ride contains 4 landings, one of which is an exit. Each of the other landings has a single pipe descending to the exit landing. Therefore, each of them could be the starting landing with equal probability of 1/3.



1)  
 {"E000",
"1000",
"1001",
"000P"}  1  1 
 Returns: 0.6666666666666666  This time, there is an exit landing and a crocodile pond. Of the other two landings, the first has a descending pipe only to the exit, while the second is connected both to the exit and to the pond. So, the probability of reaching an exit starting from landing 2 is lower and the chances of ground 1 being the start of the journey increase.



2)  
 {"01000100",
"00111000",
"00001010",
"000E0000",
"0000E000",
"00000P00",
"000000P0",
"01000000"}  1  2 
 Returns: 0.14285714285714288  Analyzing the graph above, we can see that landings 0, 1 and 7 could be the starting landings. One can reach an exit from landing 0 using 2 pipes with probability 2/6, from landing 1 with probability 1/6 and from landing 7 with probability 2/3. Therefore, the probability that the ridetaker began from landing 1 is equal to (1/6)/(2/3+2/6+1/6)=1/7.



3)  
 {"0100",
"0010",
"0001",
"000E"}  0  2 
 Returns: 0.0  Obviously, the only way to get to the exit landing using 2 pipes is from ground 1. Therefore there is no chance that landing 0 was the initial ground.



4)  
  Returns: 0.0  Note that some sections of the ride might be disconnected.


