33936번 - 두 괄호 문자열

문제

서기 3025년, 동현이는 3025 IUPC에 참가하였다. 마지막 문제부터 시작해서 역순으로 문제를 풀기로 결심한 동현이는 대회가 시작하자마자 가장 먼저 마지막 문제를 읽었다. 문제의 내용은 다음과 같았다.

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

1. 빈 문자열은 올바른 괄호 문자열이다.
2. A가 올바른 괄호 문자열이면, A를 괄호로 둘러싼 (A)도 올바른 괄호 문자열이다.
3. A와 B가 올바른 괄호 문자열이면, 두 문자열을 이어 붙인 AB도 올바른 괄호 문자열이다.
4. 모든 올바른 괄호 문자열은 위의 세 가지 규칙을 이용해서 만들 수 있다.

길이가 $N$인 올바른 괄호 문자열 $a,ドル $b$가 주어진다. 당신은 다음과 같은 시행을 원하는 만큼 할 수 있다.

• 문자열 $a$의 부분문자열 "()"를 선택한다. 선택한 부분문자열을 ")("로 바꿔도 여전히 $a$가 올바른 괄호 문자열이라면, ")("로 바꾼다.

$a$를 $b$와 같게 만들기 위해 필요한 최소 시행 횟수를 출력하여라. 만약 $a$를 $b$와 같게 만드는 것이 불가능하다면 대신 -1을 출력하여라.

문제를 읽은 동현이는 누구보다 빠르게 코드를 제출했지만 틀렸습니다 결과를 받았다. "맞는데 왜 틀려"를 반복해서 외치던 동현이는 충격적인 사실을 알아냈다. 문자열 $a,ドル $b$가 입력 데이터로 주어져야 하는데 출제자의 실수로 인하여 문자열 $b$만 입력 데이터로 주어진 것이다. 이래서는 문자열 $a$를 모르기 때문에 문제를 풀 수가 없다.

화가 난 동현이는 길이가 $N$인 가능한 모든 올바른 괄호 문자열들을 $a$에 대입하여 나오는 출력값들을 모조리 더한 값을 구하는 프로그램을 제출하기로 했다. 값이 매우 커지거나 작아질 수 있으므로, 구하고자 하는 값을 $f(b)$라고 할 때 $ f(b) \bmod 10^9 + 7 $를 출력하기로 했다. 동현이가 제출하려는 프로그램을 여러분도 작성해 보자.

$\bmod$ 연산의 의미를 잘 모른다면 하단의 노트 문단을 참고하자.

입력

첫 번째 줄에 문자열의 길이 $N$이 주어진다.

두 번째 줄에 길이가 $N$인 문자열 $b$가 주어진다. $b$는 올바른 괄호 문자열이다.

출력

동현이가 구하고자 하는 값을 $f(b)$라고 할 때 $ f(b) \bmod 10^9 + 7 $를 첫 번째 줄에 출력한다.

제한

• $ 2 \le N \le 2,000円 $

노트

정수 $a$와 0ドル$이 아닌 정수 $b$에 대해, $a = bq + r$와 0ドル \le r < |b|$를 만족하는 정수 $q,ドル $r$이 유일하게 존재하며, 이때 $r$를 $a$를 $b$로 나누었을 때 나머지라 한다.

$a \bmod b$는 $a$를 $b$로 나누었을 때 나머지를 의미한다.