Farmer John은 보통 원형 낙인을 찍지만 도구가 고장 나 괄호 ( 모양으로 대신한다. Holstein과 Guernsey 두 품종이 있다. 각 소의 괄호 낙인은 바라보는 방향에 따라 왼쪽 또는 오른쪽 괄호로 보인다.

소 $N$마리가 임의 방향으로 줄 서 있어 길이 $N$의 괄호 문자열로 보인다. FJ는 왼쪽에서 오른쪽으로 Holstein만 등장 순서대로 읽으면 균형 잡힌 괄호 문자열이고 Guernsey도 같다는 것을 발견한다! 드문 일인지 알아보려고 $N$마리의 품종을 배정해 이 성질을 만족하는 경우 수를 구하여라.

균형의 정의는 여러 가지이다. 가장 간단한 것은 (와 )의 총수가 같고 모든 접두사에서 (가 )보다 적지 않은 것이다. 예를 들어 다음은 모두 균형 잡혔다.

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

다음은 그렇지 않다.

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

입력

• 1행: 길이 $N$ $(1 \le N \le 1000)$의 괄호 문자열.

출력

• 1행: Holstein과 Guernsey가 각각 균형 잡힌 괄호 부분 수열이 되도록 품종을 배정하는 경우 수인 정수 하나. 클 수 있으므로 2012로 나눈 나머지, 즉 모듈로 2012를 출력한다. 한 품종만 쓰는 배정도 유효하다.

예제

입력 1

(())

출력 1

6

참고

다음 배정은 가능하다.

(())
HHHH

(())
GGGG

(())
HGGH

(())
GHHG

(())
HGHG

(())
GHGH

문제 작성자: Brian Dean, 2012