Let’s define a correct string of brackets as follows: \begin{itemize} \item \textbf{()} and \textbf{\[\]} are correct strings of brackets; \item if \textbf{A} is a correct string of brackets, then \textbf{(A)} and \textbf{\[A\]} are also correct strings of brackets; \item if \textbf{A} and \textbf{B} are both correct strings of brackets, then the concatenation \textbf{AB} is also a correct string of brackets; \end{itemize} In a correct string of brackets which contains at least one pair of square brackets: \textbf{\[} and corresponding \textbf{\]}, each square bracket (both opening and closing) was replaced by the opening round bracket, therefore obtaining a broken string of brackets. For example, \textbf{((} and \textbf{((((()))} both are broken strings of brackets. First string is obtained from the correct strings of brackets \textbf{\[\]}. Second string may be obtained only from the following four correct strings of brackets: \textbf{\[\]((()))}, \textbf{(\[\](()))}, \textbf{((\[\]()))} or \textbf{(((\[\])))}. Your task is for a given broken string of brackets calculate the number of possible correct strings of brackets from which the given broken string may have been obtained. \InputFile The first line of input file contains a single even integer \textbf{N} (\textbf{2} ≤ \textbf{N} ≤ \textbf{30000}) - the length of the given broken string of brackets. The second line contains \textbf{N} characters '\textbf{(}' and '\textbf{)}' - the given broken string of brackets. \OutputFile The single line of the output file should contain one integer - the required number of correct strings of brackets. Because the number of correct strings of brackets can be large, you should output the answer modulo \textbf{1000000009}.