올바른 괄호 문자열
시간 제한2초메모리 제한512 MB
괄호 문자열에서 한 글자를 뒤집는 갱신과, 구간 [l, r]의 괄호를 임의로 바꿔 전체를 올바른 괄호 문자열로 만드는 경우의 수를 묻는 질의를 처리한다.
문제
(와 )로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중에서 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다.
- 빈 문자열은 올바른 괄호 문자열이다.
- (A)가 올바른 괄호 문자열이라면,
(A)도 올바른 괄호 문자열이다. - (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)번 쿼리가 들어올 때마다 정답을 한 줄에 하나씩 출력한다.