23798번 - 올바른 괄호 문자열

\(\texttt{(}\) 와 \(\texttt{)}\)로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. \(A\)가 올바른 괄호 문자열이라면, \(\texttt{(}A\texttt{)}\)도 올바른 괄호 문자열이다.
3. \(A\)와 \(B\)가 올바른 괄호 문자열이라면, \(AB\)도 올바른 괄호 문자열이다.

길이가 \(n\)인 괄호 문자열 \(S=S_1...S_n\)가 주어진다. 이때, 다음 두 종류의 쿼리를 수행하는 프로그램을 작성하시오.

• \(1\) \(k\): \(S_k\)의 괄호를 반대 방향으로 바꾼다. 이 쿼리는 누적된다. (\(1 \le k \le n\))
• \(2\) \(l\) \(r\): \(S_l...S_r\)의 괄호를 임의로 바꿀 수 있다고 할 때, \(S\)가 올바른 괄호 문자열이 되는 경우의 수를 출력한다. 답이 커질 수 있으니 \(1,000,000,007\)로 나눈 나머지를 출력한다.(\(1 \le l \le r \le n\))

첫째 줄에 괄호 문자열의 길이 \(n (2 \le n \le 300,000\),  \(n\)은 짝수\( )\)이 주어진다.

둘째 줄에 괄호 문자열 \(S\)가 주어진다.

셋째 줄에 쿼리의 개수 \(q (1 \le q \le 300,000)\)가 주어진다.

넷째 줄부터 \(q\)개의 줄에는 각 쿼리가 한 줄에 하나씩 주어진다.

\(2\)번 쿼리가 들어올 때마다 정답을 한 줄에 하나씩 출력한다.