AT_arc194_d [ARC194D] Reverse Brackets

以下のいずれかの条件を満たす文字列を**正しい括弧列**と定義します。 - 空文字列 - ある正しい括弧列 $ 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 $ で割ったあまりを求めてください。

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

答えを出力せよ。

### Sample Explanation 1 例えば、以下のように操作をすることで、 $ S $ を `()(())` にすることができます。 - $ S $ の連続部分列として、 $ S $ の $ 1 $ 文字目から $ 6 $ 文字目を選ぶ。これは正しい括弧列である。 $ S $ が `()(())` となる。 他に作ることのできる $ S $ は `(())()` のみです。よって答えは $ 2 $ です。 ### Constraints - $ 1 \le N \le 5000 $ - $ |S|=N $ - $ S $ は正しい括弧列