eolymp
bolt
Try our new interface for solving problems
Problems

Brackets

Brackets

Time limit 1 second
Memory limit 64 MiB

Let’s define a correct string of brackets as follows:

  • () and [] are correct strings of brackets;

  • if A is a correct string of brackets, then (A) and [A] are also correct strings of brackets;

  • if A and B are both correct strings of brackets, then the concatenation AB is also a correct string of brackets;

In a correct string of brackets which contains at least one pair of square brackets: [ and corresponding ], each square bracket (both opening and closing) was replaced by the opening round bracket, therefore obtaining a broken string of brackets.

For example, (( and ((((())) both are broken strings of brackets. First string is obtained from the correct strings of brackets []. Second string may be obtained only from the following four correct strings of brackets: []((())), ([](())), (([]())) or ((([]))).

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.

Input data

The first line of input file contains a single even integer N (2N30000) - the length of the given broken string of brackets. The second line contains N characters '(' and ')' - the given broken string of brackets.

Output data

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 1000000009.

Examples

Input example #1
4
((()
Output example #1
2
Source BOI-2012