균형 잡힌 소 품종

문제

농부 John은 보통 소에게 원형 낙인을 찍지만, 낙인 도구가 고장 나는 바람에 각 소에게 괄호 모양의 낙인 ( 를 찍을 수밖에 없게 되었습니다. 농장에는 두 품종의 소, 홀스타인(Holstein)과 건지(Guernsey)가 있습니다. 소가 바라보는 방향에 따라 이 괄호 낙인은 왼쪽 괄호 ( 로 보이기도 하고 오른쪽 괄호 ) 로 보이기도 합니다.

John의 소 $N$마리가 한 줄로 서 있고 각자 임의의 방향을 바라보고 있으므로, 낙인들은 길이 $N$의 괄호 문자열처럼 보입니다. 이 줄을 바라보던 John은 놀라운 규칙을 발견합니다. 홀스타인만 왼쪽에서 오른쪽으로(줄에 나타나는 순서대로) 훑어보면 균형 잡힌 괄호 문자열이 되고, 건지만 훑어보아도 마찬가지로 균형 잡힌 괄호 문자열이 된다는 것입니다.

이것이 얼마나 드문 일인지 알아보기 위해, 이 성질이 성립하도록 $N$마리의 소 각각에 품종을 배정하는 방법의 수를 세어 John을 도와주세요.

괄호 문자열이 균형 잡혀 있다는 것은 ( 와 ) 의 개수가 같고, 문자열의 모든 접두사에서 ( 의 개수가 ) 의 개수 이상이라는 뜻입니다. 예를 들어 다음 문자열들은 균형 잡혀 있습니다.

()
(())
()(()())

반면 다음 문자열들은 균형 잡혀 있지 않습니다.

)(
())(
((())))

입력

첫째 줄에 길이 $N$ ($1 \le N \le 1000$)의 괄호 문자열이 주어집니다.

출력

홀스타인이 이루는 부분수열과 건지가 이루는 부분수열이 모두 균형 잡힌 괄호 문자열이 되도록 품종을 배정하는 방법의 수를 정수 하나로 출력합니다. 이 수는 매우 커질 수 있으므로 $2012$로 나눈 나머지를 출력하세요. 한 가지 품종만 사용하는 배정도 유효합니다.

설명

예를 들어 입력이 (()) 일 때, 유효한 품종 배정(H = 홀스타인, G = 건지)은 다음 6가지입니다.

(())      (())      (())
HHHH      GGGG      HGGH

(())      (())      (())
GHHG      HGHG      GHGH

그래서 (()) 에 대한 답은 6입니다.