소 표식

목축업자 태승은 평소 소에게 표식을 찍는데, 표식 기계가 고장 나서 각 소에게 괄호 모양의 표식을 찍을 수 밖에 없었습니다. 그의 농장에는 황소와 젖소 두 종류가 있습니다. 그는 각 소에 괄호 모양의 표식을 찍습니다. 소가 어느 방향을 보고 있는지에 따라 이것은 왼쪽 괄호나 오른쪽 괄호처럼 보일 수 있습니다.

태승의 N 마리의 소들은 모두 한 줄로 서 있고, 각각 임의의 방향을 보고 있으므로, 소들에게 찍힌 표식은 길이가 N인 괄호 문자열처럼 보입니다. 이 행렬을 보고, 태승은 놀라운 패턴을 발견했습니다. 그가 왼쪽에서부터 오른쪽으로 황소만 스캔하면(시퀀스에서 나타나는 순서대로), 균형 잡힌 괄호 문자열을 생성합니다. 게다가, 젖소도 마찬가지입니다! 이것이 정말로 드문 사건인지 확인하려면, 태승이 N 마리의 소에 표식을 찍는 방법이 이 속성을 유지할 수 있도록 도와주세요.

괄호 문자열이 '균형 잡힌' 것이 어떤 의미인지 정의하는 방법은 여러 가지가 있습니다. 가장 간단한 정의는 '('의 전체 수와 ')'의 수가 동일해야 하며, 문자열의 어떤 접두사에 대해서도 '('의 수가 ')'의 수보다 많아야 한다는 것입니다. 예를 들면, 다음 문자열은 모두 균형을 이룹니다.

• ()
• (())
• ()(()())

다음 문자열은 균형을 이루지 않습니다:

• )(
• ())(
• ((())))

• 줄 1: 괄호의 길이가 N인 문자열 (1 <= N <= 1000).

• Line 1: 단일한 정수, 이를 통해 태승이가 황소의 균형잡힌 괄호 부분 수열을 형성하고, 젖소도 마찬가지로 표식을 찍을 수 있는 방법의 수를 지정합니다. 응답이 매우 큰 수일 수 있으므로, 이 수를 2012로 나눈 나머지(즉, 2012를 모듈로하는 수)를 출력해 주세요. 한 종류의 품종만을 포함하는 할당도 유효합니다.