Author:  A. Klenin  Time limit:  3 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
For a string of parentheses '(' and ')', let us define shortening as follows. Pick a random pair of characters '(' and ')' such that '(' is to the left of ')' and delete them. Selection probability is distributed uniformly across all possible pairs. Repeat shortening until no suitable pair left.
Given a string of parentheses, your program must calculate the probability of the above process to finish with an empty string.
Input contains a string of parentheses S.
Output must contain a single floating point number — probability with absolute error of no more than 10^{−7}.
1 ≤ S ≤ 36
No.  Standard input  Standard output 

1 


2 


3 

