In the year of 2010, "Watashi" and "Kimi" become the admins of ZOJ. They are twins, but "Kimi" always does the right things while "Watashi" always does the wrong things.
The online contest "ZOJ Weekly" is scheduled in tomorrow. There will be N problems in this contest, and "Watashi" and "Kimi" are busy checking the the data for all the problems. After "Kimi" checks the data of a problem, the data will always be right, but After "Watashi" checks the data of a problem, the data will always be wrong!
In each turn when "Watashi" or "Kimi" checks, he will first choose a problem to check. Either of them will never choose the problems which he can make sure is most recently checked by himself (not by the other one). He will then randomly choose a problem in the candidate problems, and checks the data for that problem. So when either of them is sure that all the problems are lately checked by himself, he will do nothing.
Given the order in which they check the problems, you are to print the probability that all the data are right after all the checks made by them.
Initially, all the problems have been checked by "Kimi" so all of them are right at first. And both of them know when the other one checks the data, but they can't see which problem the other one is checking.
Input
There are multiple test cases. There are two parts for each case. The first part is one line with an integer N (1 <= N <= 16), the number of problems for the contest. The second part consists with some lines. A line will be either "Watashi" or "Kimi", which means a check made by "Watashi" or a check made by "Kimi". This part ends with a line with "End". There will be at most 100 lines for the second part.
Output
For each case, print a real number in one line, the probability that all the data are right after all the checks made by them. Keep two digits after the decimal point.
Sample Input
2
Watashi
End
3
Watashi
Kimi
End
Sample Output
0.00
0.33
