시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 15 11 42.308%

문제

올바른 괄호 문자열을 다음과 같이 정의한다.

  • ()와 []는 올바른 괄호 문자열이다.
  • A가 올바른 괄호 문자열이라면, (A)와 [A]도 올바른 괄호 문자열이다.
  • A와 B가 올바른 괄호 문자열이라면, 두 문자열을 이어 붙인 AB도 올바른 괄호문자열이다.

적어도 한 쌍의 대괄호([와 그것에 대응하는 ])를 포함하고 있는 올바른 괄호 문자열이 있을 때, 모든 대괄호를 (로 바꾼 문자열을 부서진 괄호 문자열이라 한다.

예를 들어, ((와 ((((()))는 부서진 괄호 문자열이다. 첫 번째 문자열에서 올바른 괄호 문자열인 []를 얻을 수 있다. 두번째 문자열은 다음과 같은 4가지 올바른 괄호 문자열을 얻을 수 있다. []((())), ([](())), (([]())), ((([]))). 

부서진 괄호 문자열이 주어졌을 때, 여기서 얻을 수 있는 올바른 괄호 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 부서진 괄호 문자열의 길이 N(2≤N≤30000)이 주어진다. 둘째 줄에는 (와 )로 이루어진 길이가 N인 부서진 괄호 문자열이 주어진다.

출력

첫째 줄에 입력으로 주어진 부서진 괄호 문자열에서 얻을 수 있는 올바른 괄호 문자열의 개수를 1000000009로 나눈 나머지를 출력한다.

예제 입력

8
((((((((

예제 출력

14

힌트

예제의 경우에 얻을 수 있는 올바른 괄호 문자열은 다음과 같다.

[][][][], [[]][][], [[]][[]], [][][[]], [[[]]][], [[][]][], [][[][]], [][[[]]], [[[[]]]], [[][[]]], [[[]][]], [[][][]], [[[][]]], [][[]][]

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 1번