問題文

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

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

長さ $N$ の正しい括弧列 $S$ が与えられます。$S$ の各文字を赤と青に塗り分ける方法は全部で $2^N$ 通りありますが、そのうち以下の条件を満たすものは何通りあるでしょうか？この答えを $998244353$ で割ったあまりを求めてください。

• $S$ から赤く塗られた文字のみを順番を変えずに取り出してできる文字列を $X$ 、青く塗られた文字のみを順番を変えずに取り出してできる文字列を $Y$ とする。 $X, Y$ はともに正しい括弧列である。

制約

入力

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

$N$
$S$

出力

条件を満たす塗り分け方の個数を $998244353$ で割ったあまりを出力せよ。

4
(())

6

4
()()

4

12
(()())()(())

216

50
((((((((((((((((((((((((()))))))))))))))))))))))))

927528656