괄호

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

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

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

예를 들어 ((와 ((((()))는 부서진 괄호 문자열이다. ((에서는 올바른 괄호 문자열 [] 하나를 복원할 수 있다. ((((()))에서는 다음 네 가지 올바른 괄호 문자열을 복원할 수 있다: []((())), ([](())), (([]())), ((([]))).

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

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

부서진 괄호 문자열로부터 복원할 수 있는 올바른 괄호 문자열의 개수를 1,000,000,009로 나눈 나머지를 첫째 줄에 출력한다.