34833번 - Bracket Sequence Endgame

문제

각 문자가(, )로만 이루어진 문자열을 괄호 문자열이라고 한다. 이때, 올바른 괄호 문자열의 정의는 다음과 같다.

• ()은 올바른 괄호 문자열이다.
• $A$가 올바른 괄호 문자열일 때, ($A$)는 올바른 괄호 문자열이다.
• $A,ドル $B$가 각각 올바른 괄호 문자열일 때, $AB$는 올바른 괄호 문자열이다.

예를 들어 ()()와 (())는 올바른 괄호 문자열이고, )(와 (()는 올바른 괄호 문자열이 아니다.

괄호 문자열 $S$가 주어진다. 당신은 이 괄호 문자열에 다음 연산을 원하는 만큼 시행할 수 있다.

1. 현재 문자열을 $T$라고 하자. 당신은 올바른 괄호 문자열인 $T[l,r]$을 선택한다. 이는 $T$의 $l$번째부터 $r$번째의 문자들로 이루어진 부분 문자열을 의미한다. (1ドル \leq l \leq r \leq N$)
2. $l \leq i \leq r$인 모든 $i$에 대해 $T_i =$(이라면 )로 바꾸고, $T_i =$)이라면 (로 바꾼다.

당신은 시작 괄호 문자열 $S$로부터 연산을 원하는 만큼 진행하여 만들 수 있는 서로 다른 괄호 문자열의 개수가 궁금해졌다. 두 괄호 문자열이 다른 과정을 통해 같은 괄호 문자열이 되었을 때도 하나의 괄호 문자열로 인정됨에 주의하라.

입력

첫째 줄에 괄호 문자열의 길이 $N$이 주어진다. (1ドル \leq N \leq 5,000円$)

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

출력

연산을 시행하여 만들 수 있는 서로 다른 괄호 문자열의 개수를 998ドル,244円,353円$으로 나눈 나머지를 출력하라.

제한

노트