Скобки
Определим правильную строку скобок следующим образом:
() и [] считаются правильными строками скобок;
если A — правильная строка скобок, то (A) и [A] также являются правильными строками скобок;
если A и B обе являются правильными строками скобок, то их конкатенация AB также будет правильной строкой скобок;
В правильной строке скобок, содержащей хотя бы одну пару квадратных скобок: [ и соответствующую ], каждая квадратная скобка (как открывающая, так и закрывающая) была заменена на открывающую круглую скобку, в результате чего получилась неправильная строка скобок.
Например, (( и ((((())) обе являются неправильными строками скобок. Первая строка получена из правильной строки скобок []. Вторая строка может быть получена только из следующих четырех правильных строк скобок: []((())), ([](())), (([]())) или ((([]))).
Ваша задача — для данной неправильной строки скобок вычислить количество возможных правильных строк скобок, из которых могла быть получена данная неправильная строка.
Входные данные
Первая строка входного файла содержит одно четное целое число N (2 ≤ N ≤ 30000) — длина данной неправильной строки скобок. Вторая строка содержит N символов '(' и ')' — данная неправильная строка скобок.
Выходные данные
Единственная строка выходного файла должна содержать одно целое число — требуемое количество правильных строк скобок. Поскольку количество правильных строк скобок может быть большим, вы должны вывести ответ по модулю 1000000009.