eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Brackets

Brackets

Лимит времени 1 секунда
Лимит использования памяти 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.

Входные данные

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.

Выходные данные

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.

Пример

Входные данные #1
4
((()
Выходные данные #1
2
Источник BOI-2012