Problem I. Improbable balance

Author:A. Klenin   Time limit:3 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

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 format

Input contains a string of parentheses S.

Output format

Output must contain a single floating point number — probability with absolute error of no more than 10 − 7.

Constraints

1 ≤ |S| ≤ 36

Sample tests

No. Standard input Standard output
1
())
0.0
2
(())
1.0
3
()()()
0.3333333333

0.076s 0.009s 13