A pattern is specified, consisting of parentheses and question marks. You need to determine how many ways you can replace question marks with parentheses so that you get a correct bracket expression.
Input: Enter a string that contains the given pattern with a maximum length of 80 characters.
Output: print the desired number of ways. The initial data will be such that this number does not exceed \( 2 \cdot 10^9\).
Examples
| # |
Input |
Output |
| 1 |
????(? |
2 |