D - Reverse Brackets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

以下のいずれかの条件を満たす文字列を正しい括弧列と定義します。

  • 空文字列
  • ある正しい括弧列 A が存在して、(, A, ) をこの順に連結した文字列
  • ある空でない正しい括弧列 A, B が存在して、A, B をこの順に連結した文字列

長さ N の正しい括弧列 S が与えられます。あなたは以下の操作を何度でも行うことができます。

  • S の連続部分文字列のうち、正しい括弧列であるものを 1 個選び、反転させる。

ここで S の l 文字目から r 文字目までからなる連続部分文字列を反転させるとは、以下を行うことを指します。

  • l \le i \le r を満たす整数 i に対して同時に S_i を S_{l+r-i} が ( なら ) に、) なら ( に置き換える。(ここでの反転は、通常の反転の定義とは異なる点に注意してください。)

操作終了時にあり得る S の個数を 998244353 で割ったあまりを求めてください。

制約

  • 1 \le N \le 5000
  • |S|=N
  • S は正しい括弧列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを出力せよ。

入力例 1

6
(())()

出力例 1

2

例えば、以下のように操作をすることで、S を ()(()) にすることができます。

  • S の連続部分列として、S の 1 文字目から 6 文字目を選ぶ。これは正しい括弧列である。S が ()(()) となる。

他に作ることのできる S は (())() のみです。よって答えは 2 です。

入力例 2

2
()

出力例 2

1

Score : 700 points

Problem Statement

A string is defined to be a valid parenthesis sequence if and only if it satisfies one of the following conditions:

  • It is an empty string.
  • There exists a valid parenthesis sequence A such that the string is obtained by concatenating (, A, and ) in this order.
  • There exist non-empty valid parenthesis sequences A and B such that the string is obtained by concatenating A and B in this order.

You are given a valid parenthesis sequence S of length N. You can perform the following operation any number of times:

  • Choose a contiguous substring of S that is a valid parenthesis sequence, and reverse it.

Here, reversing the substring of S from the l-th character to the r-th character means the following:

  • For every integer i satisfying l \leq i \leq r, simultaneously replace S_i with ) if S_{l+r-i} is (, and with ( if S_{l+r-i} is ).(Note that reversing here is different from the usual definition of reversing.)

Find the number, modulo 998244353, of distinct strings S that you can have at the end of the process.

Constraints

  • 1 \leq N \leq 5000
  • |S| = N
  • S is a valid parenthesis sequence.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

6
(())()

Sample Output 1

2

For example, you can transform S into ()(()) by doing the following:

  • Choose the substring from the 1st to the 6th character of S. This is a valid parenthesis sequence. S becomes ()(()).

The only other string that can be formed is (())(). Thus, the answer is 2.

Sample Input 2

2
()

Sample Output 2

1