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